TIL no.8-Python BFS: Breadth First Search

BFS(Breadth-First search)

일단 너비 우선 탐색이라고 불리는 BFS는 말 그대로 너비를 우선해서 그래프를 탐색하는 기법인다. 시작점인 루트 노드와 같은 거리에 있는 노드를 우선으로 방문한다고 보면 된다.

위의 그림과 같이 숫자 0 노드를 lv.1이라 가정했을 때 그 밑으로 내려가면서 레벨별로 탐색하는 방법을 BFS라고 할 수 있다.

자료구조 큐(queue)

이런 탐색 과정에는 자료 구조 큐(queue)가 사용된다. 자료구조 큐의 기본적인 특징 "먼저 들어간 것이 먼저 나온다."를 꼭 기억해야 한다. 파이썬의 라이브러리 collections의 deque를 사용하면 시간을 절약할 수 있으며, 또한 파이썬 데이터 타입 중 set 을 사용하면 아주 쉽게 구현할 수 있다.

동작과정

1. 탐색 시작 노드를 큐에 삽입하고 방문처리
2. 큐에서 노드를 꺼내고 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리
3. 더 이상 2의 과정을 수행할 수 없을 때까지 반복

미로의 최단거리 통로(BFS 활용)

-7*7 격자판 미로를 탈출하는 최단경로의 경로수를 출력하는 프로그램을 작성하세요. 경로수는
출발점에서 도착점까지 가는데 이동한 횟수를 의미한다. 출발점은 격자의 (1, 1) 좌표이고, 탈
출 도착점은 (7, 7)좌표이다. 격자판의 1은 벽이고, 0은 도로이다.
격자판의 움직임은 상하좌우로만 움직인다. 미로가 다음과 같다면
출발 0 0 0 0 0 0
0 1 1 1 1 1 0
0 0 0 1 0 0 0
1 1 0 1 0 1 1
1 1 0 1 0 0 0
1 0 0 0 1 0 0
1 0 1 0 0 0 도착
위와 같은 경로가 최단 경로이며 경로수는 12이다.

▣ 입력설명
7*7 격자판의 정보가 주어집니다.

▣ 출력설명
첫 번째 줄에 최단으로 움직인 칸의 수를 출력한다. 도착할 수 없으면 -1를 출력한다.

▣ 입력예제 1
0 0 0 0 0 0 0
0 1 1 1 1 1 0
0 0 0 1 0 0 0
1 1 0 1 0 1 1
1 1 0 1 0 0 0
1 0 0 0 1 0 0
1 0 1 0 0 0 0

▣ 출력예제 1
12

from collections import deque

dx=[-1, 0, 1, 0]
dy=[0, 1, 0, -1]
a=[list(map(int, input().split())) for _ in range(7)]
dis=[[0]*7 for _ in range(7)]
Q=deque()
Q.append((0, 0))
a[0][0]=1
while Q:
    tmp=Q.popleft()
    for i in range(4):
        x=tmp[0]+dx[i]
        y=tmp[1]+dy[i]
        if 0<=x<=6 and 0<=y<=6 and a[x][y]==0:
            a[x][y]=1
            dis[x][y]=dis[tmp[0]][tmp[1]]+1
            Q.append((x, y))
if dis[6][6]==0:
    print(-1)
else:
    print(dis[6][6])

#왔던 길을 되돌아가지 않기 위해 1로 변경해야 하며, dis의 값에 항상 +1을 해줘야 한다.