[백준] 2178 - 미로탐색 (py)

문제

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)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

코드

import sys
from collections import deque

n, m = map(int, sys.stdin.readline().split())
miro = []
for _ in range(n):
    miro.extend(list(sys.stdin.readline().rstrip()))

# 이중반복문 시간 오래 걸릴 것 같으니까 배열 하나로 만들어서 해보자 extend 사용
# 한 줄에 m개니까 index/m 하면 될듯 현재 index를 i라고 하면 왼쪽은 i-1 오른쪽 i+1 아래쪽 i + m 위쪽 i-m 이겠지요 .. 이제 딕셔너리!
dic = {}

for i in range(n * m):
    dic[i] = []
    ways = []
    if i % m != m-1 and 0 <= i + 1 < n * m and miro[i + 1] == '1':
        ways.append(i + 1)
    if 0 <= i - m< n * m and miro[i - m] == '1':
        ways.append(i - m)
    if i % m != 0 and 0 <= i - 1 < n * m and miro[i - 1] == '1':
        ways.append(i - 1)
    if 0 <= i + m < n * m and miro[i + m] == '1':
        ways.append(i + m)
    dic[i] = ways


# 이제 bfs 쓰면 될 듯
def bfs(s):
    queue = deque()
    visited = set()
    cnt = {s:1}
    queue.append(s)
    while(queue):
        node = queue.popleft()
        if node not in visited:
            visited.add(node)
            queue.extend(dic[node])
            for v in dic[node]:
                if v not in visited:
                    cnt[v] = cnt[node] + 1
        if node == m * n - 1:
            return visited,cnt

print((bfs(0)[1][m*n-1]))

풀이 및 개선점

BFS로 푸는 것까지는 좋았는데, 딕셔너리를 굳이 만든 느낌이다. 딕셔너리를 만들지 말고 처음부터 int list로 저장한 다음에 bfs를 진행해도 된다.

큐는 그대로 써 주되, visited에 저장하는 과정에서 for문으로 ...?
그래프 자체를 좀 많이 연습해야 할 것 같다.