백준 - 미로 탐색 2178 (Python)

[Silver I] 미로 탐색 - 2178
https://www.acmicpc.net/problem/2178

 

문제설명

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

 

출력

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

 

 

예제입력 / 예제출력

 

문제이해 및 코드설명

N * M 의 크기의 배열이 주어지고 시작값이 1*1에서 시작한다면 N*M(가장 끝 배열) 까지 걸리는 최소 칸수를 구하는 문제이다. 이동가능 한 거리는 1이라고 주어 지며, 서로 인접한 곳만 갈수 있다는 조건이 있다(대각선 x).

그래프의 상하좌우를 탐색하며 진행하는 문제이기 때문에 bfs를 사용해서 문제를 해결해 보았다.

일반적인 bfs문제처럼 deque 자료구조를사용하였고, dx,dy를 통해 상하좌우를 탐색할수 있도록 사전에 설정해주었다.

무조건시작점이 1*1 이므로 graph에 0*0 지점을 기점으로 상하좌우를 보며 1인 경우 이동시키면서 값을 1씩 추가해주는 방식을 사용했다. N*M은 graph에서는 n-1 * m-1이므로 마지막에 위치에필요한 값을 출력해주었다.  

 

 

코드

import sys
from collections import deque

input = sys.stdin.readline

n, m = map(int, input().split())
graph = []

for _ in range(n):
    graph.append(list(map(int, input().rstrip()))) # readline의 경우 맨 뒤에 '\n'까지 입력받으므로 제거해줘야 함

# 상하좌우
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 0 <= nx < n and 0 <= ny < m and graph[nx][ny] == 1:
                queue.append((nx, ny))
                graph[nx][ny] = graph[x][y] + 1
    
    return graph[n-1][m-1]

print(bfs(0,0))