문제

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개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

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

내 코드 ( 처음, 실패작 )

# 문제 주소 : https://www.acmicpc.net/problem/2178

import sys

N, M = map(int, sys.stdin.readline().split())
MAP = [ sys.stdin.readline().rstrip() for _ in range(N) ]
distance = {(0,0):1}
queue = set([(0,0)])
visit = set()
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

while queue:
    L = queue.pop()

    if L not in visit:
        visit.add(L)
        for i in range(4):
            x = dx[i] + L[0]
            y = dy[i] + L[1]
            if x < 0 or x >= N or y < 0 or y >= M:
                continue
            
            if MAP[x][y] == "1":
                queue.add((x, y))
                distance[(x,y)] = min(distance[L]+1, distance.get((x,y), 9999999999999))

print( distance[(N-1,M-1)] )

: 솔직히 뭐가 문제인지 잘 모르겠다.. 구지 잘못이라고 한다면 DFS로 푼 것인가..? 그래서 결국 다른 사람들걸 참고했다..

다른 사람 코드

# 문제 주소 : https://www.acmicpc.net/problem/2178

import sys
from collections import deque

N, M = map(int, sys.stdin.readline().split())
MAP = [ list(map(int, sys.stdin.readline().rstrip())) for _ in range(N) ]

def bfs(x, y):
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    
    queue = deque([(x,y)])
    while queue:
        x, y = queue.popleft()

        for i in range(4):
            nextX = dx[i] + x
            nextY = dy[i] + y
            
            if nextX < 0 or nextX >= N or nextY < 0 or nextY >= M:
                continue
            
            if MAP[nextX][nextY] == 1:
                MAP[nextX][nextY] = MAP[x][y] + 1
                queue.append((nextX, nextY))
            
    return MAP[N-1][M-1]

print( bfs(0, 0) )

: visit 를 판별하는 방법을 미로의 값을 바꾸면서 1인지 아닌지 판별.. ㄷㄷ 천재다..