(파이썬) 백준 2178번 "미로 탐색"

---

# 답

from collections import deque

N, M = map(int, input().split())
board = [input() for _ in range(N)]
chk = [[False] * M for _ in range(N)]

dy = (0, 1, 0, -1)
dx = (-1, 0, 1, 0)

def is_valid_coord(y, x):
    return 0 <= y < N and 0 <= x < M

def bfs(sy, sx):
    q = deque()
    q.append((sy, sx, 1))
    chk[sy][sx] = True

    while len(q):
        y, x, d = q.popleft()
        if y == N - 1 and x == M - 1:
            return d
        for k in range(4):
            ny = y + dy[k]
            nx = x + dx[k]
            if is_valid_coord(ny, nx) and board[y][x] =='1' and not chk[ny][nx]:
                chk[ny][nx] = True
                q.append((ny, nx, d + 1))

print(bfs(0, 0))

 

 

 

 

---

# 분석 1

왜 x가 아닌 y를 먼저 표기하는가?

 

답 코드를 보면 좌표를 표기할 때 y를 먼저 표기한 뒤 x를 표기하고 있습니다.

일반적으로는 x를 먼저 쓴 후, y를 쓰는 것이 관례인데 왜 바꿔서 표기했을까요?

결론부터 말하자면, 이중 리스트에 접근하는 방법 때문입니다.

 

아래의 리스트를 좌표로 나타내면

[[1, 2, 3], [4, 5, 6], [7, 8, 9]]

아래와 같은 격자판이 있다고 가정해봅시다.

숫자 1의 좌표가 원점(0, 0)이라고 한다면, 숫자 8의 좌표는 어떻게 말할 수 있을까요?

일반적으로는 (1, 2)라고 말할 것입니다. 보통은 x 좌표를 먼저 부른 후 y 좌표를 부르기 때문입니다.

 

이제 위 격자판을 리스트로 구현해보겠습니다.

board = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]

자 이제 다시 묻겠습니다. 숫자 8에 접근하려면 뭐라고 써야할까요? board[1][2]가 맞나요?

그렇습니다. 숫자 8은 board[1][2]가 아닌 board[2][1]에 있습니다.

제일 바깥쪽 리스트는 y값(행)을 기준으로, 안쪽 리스트는 x값(열)을 기준으로 요소가 분리되어 있기 때문에 y값으로 먼저 접근한 후 x값에 접근해야합니다.

 

이러한 이중 리스트의 접근 방법에 맞춰서 다른 모든 좌표들도 y값을 먼저 표기한 후 x값을 표기하는 것으로 규칙을 정해 구현하면 헷갈리지 않을 수 있습니다.

 

 

 

 

---

# 분석 2

BFS로 최단 거리 구하기

 

 

최단 거리를 구하는 문제는 DFS보단 BFS로 풀 것을 권장합니다. 그 이유는 BFS로 탐색한 노드는 언제나 최단 거리를 보장하기 때문인데요. 그렇다면 실제 코드에서 BFS를 이용해서 어떻게 최단 거리를 구현할 수 있을까요?

 

바로, 큐에 노드 정보를 append할 때 인덱스 값 하나를 같이 끼워 넣어주면 됩니다.

맨 첫 노드에는 인덱스 값 1을 넣어주고 시작합니다. (노드를 1개 방문했으므로)

 

그리고 새로운 노드를 append 하게 되면 그 이전 노드의 인덱스 값에 1을 증가시켜줍니다.

이는 그 이전 노드에 비해 거리가 1 증가했다는 의미가 됩니다.

 

이를 반복하다가 탐색이 종료됐을 때, 이 때의 노드가 가지고 있는 인덱스 값이 최단 거리가 됩니다.