[BFS/DFS] 거리두기 확인하기 (python) - 카카오

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

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

 

 

BFS로 풀이

이 문제는 두 가지 부분을 기본 BFS에서 추가?주의해주면 된다.

 

우선 계속 탐색해나갈 조건일 때, 큐에 넣어야 한다.

(즉, 거리가 2미만이고 'O'일 경우에만 큐에 넣어야 한다.)

거리 체크를 위해 큐에 거리 정보도 함께 넣어주었다.

 

그리고 BFS가 시작하는 노드('P')마다 각각 BFS를 실행해주어야 한다.

 

 

기본 BFS에서 다음이 복잡한 경우로 볼 수 있다.

4번 문제 조건 만족시 큐에 넣기 : 거리가 2미만이고 'O'일 경우에만 큐에 삽입

1번 시작노드 : BFS 함수를 매 'P'노드들마다 실행시켜 각각 탐색해주어야 한다.

 

# 1. 시작노드
q = deque([start])

# 2. q
while q:
	now = q.popleft()

	# 3. 이 노드에서 연결된 다른 노드들
	for 다음 노드 in 연결된 노드들:

		 # 4. 조건 만족시 큐에 넣기
		if 문제 조건:
			q.append(now)

 

from collections import deque

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]

def bfs(array, start_x, start_ay):
    visited = [[False]*5 for _ in range(5)]
    flag = True
    q = deque()
    q.append((0, (start_x, start_ay)))

    while q:
        dist, (x, y) = q.popleft()
        visited[x][y] = True

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < 5 and 0 <= ny < 5:
                if not visited[nx][ny]:  # O을 또 방문할 경우 제외하기
                    if array[nx][ny] == 'O' and dist < 2:
                        q.append((dist+1, (nx, ny)))
                        visited[nx][ny] = True
                    if array[nx][ny] == 'P' and dist < 2:
                        flag = False
                        return flag
    return flag


def solution(places):
    answer = []

    for i in range(5):
        array = places[i]
        flag = 1

        for i in range(5):
            for j in range(5):
                if array[i][j] == 'P':
                    if not bfs(array, i, j):
                        flag = 0
                        break
            if not flag:  # 이중 for 문이므로 여기서 break!
                break

        answer.append(flag)

    return answer