BFS

너비 우선 탐색

백준 알고리즘을 푸는 중에 BFS를 적용해야 하는 문제가 있어 BFS에 대한 간단한 설명과 queue를 이용한 BFS 알고리즘을 푸는 방법에 대해서 애기해보겠습니다.

제목에서 보는 바와 같이 탐색 알고리즘으로서 그래프상의 모든 노드를 탐색하는 알고리즘입니다.

간단히 그림을 통해서 queue와 함께 어떤식을로 탐색하는지 애기해보겠습니다.

그래프에는 다음과 같이 총 $V1$부터 $V9$까지의 9개의 노드가 있습니다. 9개의 노드를 모두 탐색하는 방법은 다음과 같습니다.

먼저 queue를 하나 선언합니다

queue = list()

그리고 가장 먼저 start node(root)를 queue에 넣습니다(append).

queue.append(V1)

queue = [V1]

그리고 가장 첫번째 있는 V1노드를 pop해주면서, V1의 자식 노드를 append 해줍니다. pop해준 V1 노드는 search를 했다는 뜻입니다.

queue.pop(0)
queue.append(V2, V5)

queue = [V2, V5]

가장 첫번째 있는 V2노드를 pop해주면서, V2의 자식 노드를 append 해줍니다. pop해준 V2 노드는 search를 했다는 뜻입니다.

queue.pop(0)
queue.append(V3, V4)

queue = [V5, V3, V4]

가장 첫번째 있는 V5노드를 pop해주면서, V5의 자식 노드를 append 해줍니다. 여기서는 V5의 자식 노드 V4는 한번 queue에 들어갔으므로 따라서 append해줄 자식노드는 없다. pop해준 V5 노드는 search를 했다는 뜻입니다.

queue.pop(0)

queue = [V3, V4]

가장 첫번째 있는 V3노드를 pop해주면서, V3의 자식 노드를 append 해줍니다. pop해준 V3 노드는 search를 했다는 뜻입니다.

queue.pop(0)
queue.append(V7)

queue = [V4, V7]

가장 첫번째 있는 V4노드를 pop해주면서, V4의 자식 노드를 append 해줍니다. pop해준 V4 노드는 search를 했다는 뜻입니다.

queue.pop(0)
queue.append(V6)

queue = [V7, V6]

가장 첫번째 있는 V7노드를 pop해주면서, V7의 자식 노드를 append 해줍니다. pop해준 V7 노드는 search를 했다는 뜻입니다.

queue.pop(0)
queue.append(V8, V9)

queue = [V6, V8, V9]

가장 첫번째 있는 V6노드를 pop해주면서, V6의 자식 노드를 append 해줍니다. 여기서는 V6의 자식 노드 V9는 한번 queue에 들어갔으므로 따라서 append해줄 자식노드는 없다. pop해준 V6 노드는 search를 했다는 뜻입니다.

queue.pop(0)

queue = [V8, V9]

가장 첫번째 있는 V8노드를 pop해줍니다. 여기서는 V8의 자식 노드는 없습니다. pop해준 V8 노드는 search를 했다는 뜻입니다.

queue.pop(0)

queue = [V9]

가장 첫번째 있는 V9노드를 pop해줍니다. 여기서는 V9의 자식 노드는 없습니다. pop해준 V9 노드는 search를 했다는 뜻입니다.

queue.pop(0)

queue = []

queue가 모두 비게 되면 모든 노드를 search했다는 뜻이 되므로 알고리즘을 종료합니다.

BFS를 적용한 백준 알고리즘 미로 탐색 문제

문제

N×M크기의 배열로 표현되는 미로가 있다.

1	0	1	1	1	1
1	0	1	0	1	0
1	0	1	0	1	1
1	1	1	0	1	1

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

입력
첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력
첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

예제 입력 1

4 6
101111
101010
101011
111011

예제 출력 1
15

풀이 코드

입력 받는코드

row, num = map(int, input().split())
ls = list()
ls.append([0 for _ in range(num+2)])

for _ in range(row):

    inner_ls = list()
    nums = input()
    inner_ls.append(0)

    for number in nums:
        inner_ls.append(int(number))
        
    inner_ls.append(0)
    ls.append(inner_ls)

ls.append([0 for _ in range(num+2)])

solution function 코드

def solution(ls, row, num):
    start = (1,1)
    goal = (row,num)

    dx = [1, -1, 0, 0] # 동서남북
    dy = [0, 0, -1, 1] # 동서남북

    queue = list()
    queue.append(start)

    while queue:
        cur_x, cur_y = queue.pop(0)
        cur_value = ls[cur_x][cur_y]
        for idx in range(4):
            mov_x = cur_x + dx[idx]
            mov_y = cur_y + dy[idx]

            if ls[mov_x][mov_y] != 0:
                mov_value = ls[mov_x][mov_y]

            else:
                continue

            if mov_value == 1 or cur_value + 1 < mov_value:
                ls[mov_x][mov_y] = cur_value + 1
                queue.append((mov_x, mov_y))

    return ls[goal[0]][goal[1]]