백준 2178번 - 미로 탐색 (파이썬/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개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

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

답안

from collections import deque
def bfs(r,c):
    Q = deque()        # 큐
    visited = [[0]*M for _ in range(N)]
    Q.append((r,c))    # 큐에 시작점의 좌표를 튜플로 넣어준다

    while Q:
        vr, vc = Q.popleft()    # Q의 0번째 인덱스의 빼서 r과 c로 구분해준다.
        visited[r][c] = 1       # 해당 좌표를 방문처리

        for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:    # 델타를 이용해, 다음 이동 칸을 고려
            newR = vr+dr
            newC = vc+dc

            if 0<=newR<N and 0<=newC<M and not visited[newR][newC] and arr[newR][newC]=='1':
                Q.append((newR,newC))    # 다음 이동 칸이 범위 내이고, 방문한적이 없고, arr배열에서 1이라면
                visited[newR][newC] = visited[vr][vc] + 1    # 다음 칸에 이전 값의 +1 한 값을 넣어준다.
    print(visited[N-1][M-1])    # 오른쪽 아래 좌표 값 출력



N, M = map(int, input().split())
arr = [input() for _ in range(N)]
bfs(0,0)    # 시작점

후기

최단거리 라는 단어를 보자마자 bfs를 떠올렸다.

출발점인 [1,1]좌표를 기준으로 방문하지 않고, 지나갈 수 있는 길(해당 좌표의 값이 1인 경우)일 경우에 해당 좌표에 그 전값에 1을 더한 값을 넣어줌으로, 최단거리를 구할 수 있는 문제였다.