미로찾기 bfs로 풀어야 한다

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

1. dfs

from collections import deque
from copy import deepcopy

N,M=map(int,input().split())

L=[]
cheakedL=[[0 for i in range(M)] for j in range(N)]
for i in range(N):
    L.append(list(map(int,list(input()))))

cheakedL[0][0]=1
dr=[1,-1,0,0]
dc=[0,0,1,-1]
ans=10000
stack=deque([[0,0,cheakedL,1]])

while(stack):
    temp=stack.pop()
    r=temp[0]
    c=temp[1]
    num=temp[3]


    if r==N-1 and c==M-1:
        if num<ans:
            ans=num
            continue

    if num >= ans:
        continue

    for k in range(4):
        tempR=r+dr[k]
        tempC=c+dc[k]
        if 0<=tempR<N and 0<=tempC<M and L[tempR][tempC]==1 and temp[2][tempR][tempC]==0:
            copiedC = deepcopy(temp[2])
            copiedC[tempR][tempC]=1
            stack.append([tempR,tempC,copiedC,num+1])

print(ans)

dfs로 문제를 푼다면 끝까지 가고 난 후 처음으로 돌아와서 새로운 경로로 갈때는 새로운 cheakedL을 만들어야 한다. 따라서 stack에 [행위치,열위치,cheakedL,현재까지 횟수] 를 모두 저장해야 한다. 즉 stack에 새로운 개체를 추가해야 할 때 마다 list를 copy해야 한다. 따라서 bfs를 이용해야 한다.

 

2. bfs

import queue

N,M=map(int,input().split())

L=[]
cheakedL=[[0 for i in range(M)] for j in range(N)]
for i in range(N):
    L.append(list(map(int,list(input()))))

cheakedL[0][0]=1
dr=[1,-1,0,0]
dc=[0,0,1,-1]
q=queue.Queue()
q.put([0,0])

while(q):
    temp=q.get()
    r=temp[0]
    c=temp[1]
    if r==N-1 and c==M-1:
        break

    for k in range(4):
        tempR=r+dr[k]
        tempC=c+dc[k]
        if 0<=tempR<N and 0<=tempC<M and L[tempR][tempC]==1 and cheakedL[tempR][tempC]==0:
            cheakedL[tempR][tempC]=cheakedL[r][c]+1
            q.put([tempR,tempC])

print(cheakedL[N-1][M-1])

bfs를 이용한다면 해당 노드가 cheakedL에 체크되는 즉시 최단거리를 보장받게 된다. 왜냐하면 bfs이기 때문에 짧은 거리부터 탐색이 되기 때문이다. 따라서 cheakedL의 요소에 아예 해당 거리를 입력받는 방식으로 문제를 해결할 수 있다.