[Baekjoon, Python] 2178번 : 미로 탐색

도입

백준 단계별 풀기 DFS와 BFS 다섯 번째 문제이다.

백준 2178번 문제, 입력, 출력

---

백준 2178번 입출력 예제 1, 2, 3, 4

---

DFS와 BFS

DFS

- Root Node 혹은 다른 임의의 Node에서 이어진 Branch를 완벽하게 탐색하고 다른 이어진 Branch로 넘어가는 방법.

한 방향으로 계속 가서 끝을 마주하면 다른 방향으로 설정해서 마찬가지로 진행.

- Stack 또는 Recursive함수로 구현.

- 시간 복잡도 : 인접 리스트는 $O(V+E)$ 인접 행렬은 $O(V^2)$ // 접점(V), 간선(E)

BFS

- Root Node 혹은 다른 임의의 Node에서 이어진 Branch들의 바로 하나 건너 있는 Node들을 먼저 탐색.

- Queue로 구현

- 시간 복잡도 :  인접 리스트는 $O(V+E)$ 인접 행렬은 $O(V^2)$ // 접점(V), 간선(E)

---

풀이

1. DFS 보다 BFS를 사용한다. 최소거리, 최단거리 등의 문제는 BFS로 해결하는 대표적인 문제라고 볼 수 있다.

 

2. 해당위치에서 상하좌우를 확인하고 값이 1이라면, 그 위치(matrix[nx][ny])에 현재 위치(matrxi[x][y])값에 1을 증가시킨 값을 넣어준다. 그리고 queue에 nx,ny의 좌표를 넣어준다.

---

코드

from sys import stdin

dx=[-1,0,1,0] # 좌 우 위 아래
dy=[0,1,0,-1] # 좌 우 위 아래

var_N,var_M = map(int, stdin.readline().split())
matrix = [list(stdin.readline()) for _ in range(var_N)]

queue = [[0, 0]]
matrix[0][0] = 1

def bfs(queue):
    while queue:
        x, y = queue[0][0], queue[0][1]
        del queue[0]
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < var_N and 0 <= ny < var_M and matrix[nx][ny] == "1":
                queue.append([nx, ny])
                matrix[nx][ny] = matrix[x][y] + 1

bfs(queue)

print(matrix[var_N - 1][var_M - 1])

---

마무리

최소 경로의 문제는 BFS가 유리하다라는 것을 체감할 수 있는 문제였다.