[이코테 python] Ch.5.2 BFS (+ 미로 탈출 문제)

5.2.1  BFS (Breadth-First-Search) 알고리즘

 

 

너비 우선 탐색 : 가까운 노드부터 차례대로 탐색하는 알고리즘

 

 

 

BFS 는 가장 가까운 노드부터 방문한 후, 다시 돌아가 다른 경로를 탐색하는 알고리즘을 말한다.

 

따라서, BFS 는 큐 자료구조 (선입선출) 를 이용하여 구현할 수 있다.

 

 

 

 

 

 

BFS 동작 과정은 다음과 같다.

 

 

1) 큐에 탐색 시작 노드를 삽입하고, 방문값을 true 로 바꾼다.

 

2) 큐에서 방문하지 않은 인접노드를 모두 큐에 넣고, 방문값을 true 로 바꾼다.

 

4) 더 이상 방문할 노드가 없을 때까지 1, 2 번의 과정을 반복한다.

 

 

 

 

---

 

 

5.2.2  BFS 알고리즘 특징

 

 

 

BFS 알고리즘은 큐 자료구조를 이용하여 구현된다.

 

 

 

하지만, 실제 알고리즘을 구현할 때, 

 

큐보다 deque 라이브러리를 이용하는 것이 더 좋다.

 

 

 

다음은 deque 라이브러리를 이용하여 BFS 를 구현한 코드이다.

 

 

 

 

from collections import deque

# 노드 연결 정보 2차원 리스트로 표현
graph = [
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2,6,8],
    [1,7]
]

# 노드 방문 정보 1차원 리스트로 표현
visited= [False]*9

# deque 로 BFS 구현
def bfs(graph, start, visited):
    queue = deque([start])
    visited[start] = True

    # 모든 노드를 방문할 때까지 반복
    while queue:
        v = queue.popleft()
        print(v, end=' ')

        # 방문하지 않은 노드 큐에 삽입
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i]= True

bfs(graph, 1, visited)

 

 

 

from collections import deque

 

 

: deque 라이브러리로 BFS를 구현한다.

 

 

 

graph

 

 

: 인덱스가 0인 노드는 비워두고 사용하지 않는다.

 

 

 

visited = [False]*9

 

 

: 인덱스가 0인 노드를 사용하지 않았으므로, 9개의 1차원 리스트를 생성한다.

 

 

 

queue.popleft()

 

 

: 큐에서는 pop 을 할 때, popleft() 함수 사용

 

 

 

 

데이터의 개수가 N 개 일 때, 시간 복잡도는 O(N) 이다.
단, 일반적인 경우 수행 시간이 DFS 보다 좋은 편이다.

 

 

 

 

---

 

 

5.2.3  DFS 알고리즘 예시 - 음료수 얼려 먹기

 

 

 

풀이시간 : 30분 / 제한시간 : 1초 / 메모리 제한 : 128MB

 

 

문제 )
동빈이는 N x M 크기의 직사각형 형태의 미로에 갇혀있다. 미로에는 여러 마리의 괴물이 있어 이를 피해 탈출해야 한다. 동빈이의 위치는 (1,1)이고 미로의 출구는 (N,M) 의 위치에 존재하며 한번에 한 칸씩 이동할 수 있다. 이때 괴물이 있는 부분은 0으로, 괴물이 없는 부분은 1로 표시되어 있다. 미로는 반드시 탈출할 수 있는 형태로 제시된다. 이때 동빈이가 탈출하기 위해 움직여야 하는 최소 칸의 개수를 구하시오. 칸을 셀 때는 시작 칸과 마지막 칸을 모두 포함해서 계산한다.

 

입력 조건 )
첫째 줄에 두 정수 N, M(4 <= N,M <= 200) 이 주어진다. 다음 N개의 줄에는 각각 M개의 정수 (0 혹은 1) 로 미로의 정보가 주어진다. 각각의 수들은 공백 없이 붙어서 입력으로 제시된다. 또한 시작 칸과 마지막 칸은 항상 1이다.

 

출력 조건 )
첫째 줄에 최소 이동 칸의 개수를 출력한다.

 

 

 

 

1) 문제 해결 아이디어

 

 

2차원 배열의 탐색 문제는 그래프 형태를 떠올리면 쉽게 풀 수 있다.

 

 

 

이 문제의 경우, BFS 를 이용하면 간단하게 문제를 해결할 수 있다.

 

 

1) (1,1) 지점부터 BFS 를 이용하여 모든 노드를 큐에 넣는다.

 

2) 노드를 방문하면, 이전 노드까지의 거리에 +1 을 한다.

 

 

 

 

 

 

2) 문제 해결 코드 ( Python )

 

 

from collections import deque

# N x M 개수 입력
n, m = map(int, input().split())


# N x M 2차원 리스트 입력
graph = []
for i in range(n):
    # 띄어쓰기 없이 입력
    graph.append(list(map(int, input())))


# 상, 하, 좌, 우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]


# BFS 로 노드 방문
def bfs(x, y):
    queue = deque()
    queue.append((x, y))

    while queue:
        x, y = queue.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            # 그래프를 벗어나는 경우
            if nx < 0 or ny < 0 or nx >= n or ny >= m:
                continue

            # 갈 수 없는 길인 경우
            if graph[nx][ny] == 0:
                continue

            # 방문하지 않은 노드인 경우
            if graph[nx][ny] == 1:
                graph[nx][ny] = graph[x][y] + 1
                queue.append((nx, ny))

    return graph[n-1][m-1]

print(bfs(0,0))

 

 

 

 

 

 

 

 

 

 

 

나동빈 '이것이 코딩 테스트다 with 파이썬' 책을 기반으로 작성하였습니다.

https://www.youtube.com/watch?v=m-9pAwq1o3w&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC