[Python] 프로그래머스. 2021 카카오 인턴 - 거리두기 확인하기 (Level 2)

https://programmers.co.kr/learn/courses/30/lessons/81302

코딩테스트 연습 - 거리두기 확인하기

간단한 그래프 문제. 5 * 5 배열 조건이라서 연산량이 그렇게 많지는 않다.

dfs / bfs 방식 무엇으로든 풀 수 있어 보인다. 나는 bfs로 풀었다.

 

 

	from collections import deque
	def solution(places):
	dirs = [(0,1), (0,-1), (1,0), (-1,0)]
	# 맨해튼 거리 체크 메소드
	def get_distance(p1, p2):
	return abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])
	def check(p1):
	y, x = p1[0], p1[1]
	# 해당 place 변수 호출을 위해 nonlocal 선언
	nonlocal place
	# 확인할 좌석을 queue / 이미 확인한 좌석을 visited에 저장.
	queue, visited = deque(), set()
	queue.append((y, x))
	while queue:
	# 확인할 좌석 선택
	ty, tx = queue.popleft()
	visited.add((ty, tx))
	for dy, dx in dirs:
	ny, nx = ty + dy, tx + dx
	# 현재 위치에서 거리가 2 이하이고, 아직 확인하지 않은 좌석일 경우
	if 0 <= ny < len(place) and 0 <= nx < len(place[0]) \
	and get_distance((y, x), (ny, nx)) <= 2 and (ny, nx) not in visited:
	# 해당 좌석 확인했음을 체크
	visited.add((ny, nx))
	# 비어 있을 경우, 확인할 좌석 queue에 저장.
	if place[ny][nx] == "O":
	queue.append((ny, nx))
	# 사람이 있는 경우 == 거리두기 위배. False 반환
	elif place[ny][nx] == "P":
	return False
	return True
	answer = []
	for place in places:
	# 사람들의 현재 위치 기록.
	position = set()
	for y in range(len(place)):
	for x in range(len(place[0])):
	if place[y][x] == "P":
	position.add((y, x))
	# 사람들의 거리두기 여부 체크
	for p in position:
	if check(p) is False:
	answer.append(0)
	break
	else:
	answer.append(1)
	return answer

view raw [프로그래머스] 거리두기 확인하기.py hosted with ❤ by GitHub