[백준] 2178번 미로 탐색 [Python] - BFS

 

 

NxM 크기의 미로에서 $($1,1$)$ 에서 $($N,M$)$로 가는데 지나야하는 최소 칸 수를 구하는 문제

1은 이동 가능, 0은 이동 불가 칸을 의미

 

문제

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

 

bfs를 사용했습니다.

import sys

def main():
    N, M = map(int, sys.stdin.readline().split())	# 미로 크기
    d = ((-1, 0), (1, 0), (0, -1), (0, 1))	# 이동 방향

    maze = []				# 미로
    for _ in range(N):
        maze.append(list(sys.stdin.readline().rstrip()))

    def bfs():
        q, c = [(0, 0)], 1	# q: 이동한 구간 리스트, c: 이동 횟수 >>> 초기화 : (0,0)에서 시작, 1
        maze[0][0] = '0'	# 지나온 길은 '0'으로 표시 >>> 출발점 '0'으로 표시

        while q:
            c += 1
            tmp = []
            for y, x in q:
                for dy, dx in d:
                    ny, nx = y + dy, x + dx	# 상하좌우로 이동

                    # 미로 내에 있는 '1'인 구간에 대해서
                    if 0 <= ny < N and 0 <= nx < M and maze[ny][nx] == '1':
                        # 도착점에 도달한 경우 이동 횟수 반환
                        if ny == N - 1 and nx == M - 1:
                            return c
                        tmp.append((ny, nx)) # 방문 구간 추가
                        maze[ny][nx] = '0'	# 방문 기록
            q = tmp
    print(bfs())	# 최소 이동 횟수 출력

if __name__ == "__main__":
    main()

 

 

예제 입력 1 

4 6
101111
101010
101011
111011

예제 출력 1 

15

예제 입력 2 

4 6
110110
110110
111111
111101

예제 출력 2 

9

예제 입력 3 

2 25
1011101110111011101110111
1110111011101110111011101

예제 출력 3 

38

예제 입력 4 

7 7
1011111
1110001
1000001
1000001
1000001
1000001
1111111

예제 출력 4 

13