미로 탐색(백준 2178번)

💡 **Check Point !

( 해당사항 ✓체크 )

1. 막힘 없이 수월하게 풀린 문제인가?

2. 1시간이내로 풀렸던 문제인가?

3. 1시간 이상 or 며칠을 두고 풀어봤더니 풀린 문제인가?

4. 시간을 써도 도무지 풀 수 없는 문제인가?

5. 솔루션을 찾아봤는가? ✓

---

난이도 체감

1. 최상

2. 상✓

3. 중

4. 하

---

이해도

1. 완벽히 이해✓

2. 다소 헷갈리는 부분들이 있음

3. 이해 못함

문제

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

def BFS(my_map,x,y,visited,N,M):
    visited[x][y]=True
    dx=[-1,1,0,0]
    dy=[0,0,-1,1]
    queue=deque()
    queue.append((x,y))
    while queue:
        v=queue.popleft()
        for i in range(4):
            mx=v[0]+dx[i]
            my=v[1]+dy[i]
            if 0<=mx<=N-1 and 0<=my<=M-1 and not visited[mx][my] and my_map[mx][my]:
                visited[mx][my]=True
                queue.append((mx,my))
                my_map[mx][my]=my_map[v[0]][v[1]]+1
    return my_map[N-1][M-1]

N,M=map(int,sys.stdin.readline().strip().split())
my_map=[]
visited=[[False]*M for _ in range(N)]
for _ in range(N):
    m=list(sys.stdin.readline().strip())
    m=list(map(int,m))
    my_map.append(m)
print(BFS(my_map,0,0,visited,N,M))

• 위 문제를 보았을 때, BFS를 사용하여 문제를 풀어야 한다는 것은 알아챘다. 하지만, 기존 문제들과 다르게, graph를 구성하여 푸는 것이 아니라 Map이 있고, 그 Map을 이동하는 형태로 문제를 풀어야 했다.
• 그 방법은 dx, dy를 미리 정의해두고, Map을 벗어나지 않는 범위에서 경로를 찾는 것이다.
• 위 방법은 구현 문제에서 자주 사용되는 방식이므로 기억해두자.