넓이우선탐색(bfs) 동작과정

"시작점 (0, 0) 도착점 (1, 2)일 때, 2차원 배열 (3X3)에서 시작점으로부터 도착점까지의 최단거리를 찾아라"는 문제를 푸는 과정입니다.

 

우선 2차원 배열과 queue를 선언합니다.

초기 상태

 

이동방향 초기 설정(사용자가 설정) # 이 예시는 북,동,남,서 순 탐색

 

본인이 설정해 둔 move에 맞게, 값을 더해가며 현재 위치에서 북, 동, 남, 서 순으로 순회하며 다음 갈 위치를 계산합니다.

아래 그림은 현재 위치(시작 위치)에서 북, 동쪽을 탐색하는 과정입니다.

이런식으로 북, 동, 남, 서를 위치마다 한번씩 다 탐색하게 됩니다. (아래 그림)

nx,ny가 MAP의 범위를 초과했거나, 이미 방문했던 노드인 경우에는 생략합니다.

 

위 그림처럼 (0,0)위치에서 다 순회한 이후에는 다시 현재 queue의 맨 앞 원소를 pop하여 (0,1)에서 북, 동, 서, 남 을 순회합니다.

아래쪽 그림처럼 (0,0)의 북,동,서,남 ==> (0,1)의 북,동,서,남 ==> (1,0)의 북,동,서,남 ==> (0,2)의 북,동,서,남 ==> ... => 도착지점을 만날때까지 계속해서 탐색합니다.

 

여기까지 bfs의 탐색 동작과정입니다. 최단거리는 위 동작과정에 한가지 동작만 추가해주면 됩니다.

bfs에서  시작점으로부터 nx,ny까지의 최단거리는 x,y까지의 최단거리 + 1의 거리입니다. 항상 현재 위치(x,y) 에서 1칸씩 nx,ny를 탐색하기 때문입니다. 따라서, queue에 현재 위치에서의 최단거리 정보를 같이 저장해주면, 간단하게 구할 수 있습니다. 

 

 

아래 사진에서 보면, 이전까지는 queue에 (x,y)만을 저장했다면, 이제는 최단거리 정보를 위해 queue에 (x,y,현재위치(x,y)까지의 최단거리)를 저장합니다. 따라서, (0,0)에서부터 (2,1)까지의 최단거리가 3이 됩니다.

 

이를 코드로 나타내면

from collections import deque

N = 3 # MAP 크기

MAP = [[0 for _ in range(N)] for _ in range(N)]
visited = [[0 for _  in range(N)] for _ in range(N)]

start_row, start_column = 0,0 # 시작 행,열 인덱스
target_row, target_column = 1, 2 # 도착 행, 열 인덱스

move = {(-1,0),(0,1),(1,0),(0,-1)} #북동남서
cnt = 0

q = deque()
q.append((start_row, start_column, cnt))
visited[start_row][start_column] = 1

while q:
    cur_row, cur_column, cnt = q.popleft()
    if cur_row == target_row and cur_column == target_column:
         break
    for next_r, next_c in move:
        next_row = cur_row + next_r
        next_column = cur_column + next_c

        if 0<=next_row<N and 0<=next_column<N \
            and visited[next_row][next_column] != 1:
                q.append((next_row, next_column, cnt + 1))
                visited[next_row][next_column] = 1

print(cnt)