[BaekJoon] 2178 미로탐색 (Silver 1) - Python

문제

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

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

 

입력예시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

---

코드

from collections import deque # bfs함수 작성을 위한 deque import

N, M = map(int, input().split()) # 미로의 크기 입력
grid = [list(input()) for _ in range(N)] # 미로 모양 입력
visited = [[False for _ in range(M)] for _ in range(N)] # 미로의 방문 여부 입력

move_x = [1, -1, 0, 0] # 좌표 이동을 위한 리스트 선언
move_y = [0, 0, 1, -1] # 좌표 이동을 위한 리스트 선언

def bfs(): # bfs함수 작성

    q = deque() # deque생성
    q.append([0, 0, 1]) # 맨 첫 위치인 0, 0과 그때의 칸 수인 1 입력

    while True: # while문 시작
        x, y, cnt = q.popleft() # q에 입력된 값 pop
        visited[x][y] = True # 해당 좌표의 방문 여부 True로 변경
        if x == N - 1 and y == M - 1: # 만약 미로의 끝까지 갔다면
            print(cnt) # 해당 좌표에서의 cnt출력하고
            break # while문 탈출
        for i in range(4): # 4번 반복하여
            dx = x + move_x[i] # dx 계산
            dy = y + move_y[i] # dy 계산
            if 0 <= dx < N and 0 <= dy < M and visited[dx][dy] == False and grid[dx][dy] == '1': # 만약 dx, dy가 미로 안에 존재하고 grid[dx][dy]를 방문한 적 없으며 grid[dx][dy]의 값이 '1'이라면
                q.append([dx, dy, cnt + 1]) # q에 [dx, dy, cnt + 1]을 추가한다
                visited[dx][dy] = True # dx, dy의 방문 여부를 True로 변경한다

bfs() # bfs함수 호출

---

실행 화면

---

채점 결과