[이것이 코딩 테스트다 with Python] DFS/BFS - 미로 탈출 (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

 

---

알고리즘

1. BFS 함수 정의 

- 초기 큐에 x,y를 넣음

- 큐에서 x,y를 뽑고 4 방향으로 확인

    - 주어진 영역을 벗어난 경우 무시

    - 0(이동할수 없는 칸)인 경우 무시

    - 해당 위치를 처음 방문한다면 전 위치에서 + 1 하고, 큐에 넣음

- 가장 오른쪽 아래까지의 최단 거리 반환

2. (0,0)에서부터의 BFS 출력

 

 

 

 

내 소스 코드

from collections import deque

n,m = map(int,input().split())

graph=[]
for i in range(n):
    graph.append(list(map(int,input())))

dx = [-1,1,0,0]
dy = [0,0,-1,1]

def bfs(x,y):
    queue = deque()
    queue.append((x,y))

    while queue:
        x, y = queue.popleft()

        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx < 0 or nx > n - 1 or ny < 0 or ny > m - 1:
                continue
            if graph[nx][ny] == 0:
                continue
            if graph[nx][ny] == 1:
                graph[nx][ny] = graph[x][y] + 1
                queue.append((nx, ny))

    return graph[n-1][m-1]

print(bfs(0,0))

 

결과