[백준] Silver1-2178 미로탐색

https://www.acmicpc.net/problem/2178

문제

N×M크기의 배열로 표현되는 미로가 있다.

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

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

풀이

from collections import deque

height, width = map(int, input().split())

graph = [[] for _ in range(height)]

for hei in range(height):
    tmp = input()
    int_list = [int(x) for x in tmp]
    graph[hei] = int_list

queue = deque()

# 상 하 좌 우
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]

def bfs():
    # 시작은 항상 0,0 이라고 가정
    queue.append([0, 0])

    while queue:
        # 현재 지점의 x, y 좌표 계산
        now_coordinate = queue.popleft()
        now_X = now_coordinate[0]
        now_Y = now_coordinate[1]

        # 상 하 좌 우 탐색
        for i in range(4):
            moved_X = now_X + dx[i]
            moved_Y = now_Y + dy[i]

            # 좌표값이 범위를 넘어간 경우 스킵
            if moved_X < 0 or moved_X >= width or moved_Y < 0 or moved_Y >= height:
                continue

            # 벽을 만난 경우 스킵
            elif graph[moved_Y][moved_X] == 0:
                continue

            # 아직 가보지 않은 길인 경우에만 탐색, 다른 방향을 통해 가본 길이더라도 현재의 길이 더 짧은 경우의 수라면 값을 변경해준다. 
            elif graph[moved_Y][moved_X] == 1 or graph[moved_Y][moved_X] > graph[now_Y][now_X] + 1:
                # 움직인 칸수를 변경해준다.
                graph[moved_Y][moved_X] = graph[now_Y][now_X] + 1
                queue.append([moved_X, moved_Y])
                if moved_Y + 1 == height and moved_X + 1== width:
                    return graph[height - 1][width - 1]

print(bfs())

처음 문제를 풀 땐, 중복된 길이면 무조건 가지 않는 것으로 설정했는데, 가본 길이더라도, 나중에 가는 길이 더 짧은 경우의 수가 있을 수 있다고 생각하여 조건을 추가, 시간이 4ms 더 걸리긴 했는데, 이러한 검증 과정이 필요할지 더 고민해 봐야겠다.