2178 미로 탐색

💡문제 분석 요약

• N, M이 주어졌을 때 N행 M열에 대해 미로를 탈출한다.
• 미로를 탈출하는 최소 거리를 구한다.

💡알고리즘 설계

• 최소의 칸수를 구하는 것이므로 BFS를 시도하면 될 것 같다.
• ⚠️주의) 이동 거리가 모두 1로 동일하다면 그냥 BFS 쓰면 되는데, 그게 아니라면 다익스트라를 사용해야한다 !!!!!

💡코드

import sys
from collections import deque
input = sys.stdin.readline

n, m, = map(int, input().split())
maze = [[0] * m for _ in range(n)]
for i in range(n): # 미로 초기화
    tmp = input().rstrip()
    for j in range(m):
        maze[i][j] = int(tmp[j])

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

# 이동거리가 1로 고정되지 않은 경우, 다익스트라를 써야함!!!!
def BFS(x, y):
    queue = deque() # 덱 선언
    queue.append((x,y)) # 초기값 append
    while queue:
        x, y = queue.popleft() # 현재 위치 꺼내줌
        for i in range(4): # 상하좌우 탐색
            nx = x + dx[i]
            ny = y + dy[i]

            # 범위 내에서 이동하는 상황 & maze 벽이 아닌 경우(값이 0이 아닌 경우)
            if 0 <= nx < n and 0 <= ny < m and maze[nx][ny] == 1:
                maze[nx][ny] = maze[x][y] + 1 # 마치 시간을 누적해가듯, 지나간 경로 횟수를 현재 위치에 누적
                queue.append((nx, ny)) # 새로운 nx, ny를 append해줌
    return maze[n-1][m-1] # 도착 위치는 (N-1, M-1)로 고정이므로 이 값을 return


print(BFS(0,0)) # 0,0에서 출발

💡시간복잡도

• 결국 모든 정점을 방문하므로 O(N*M)이 될것이다.

💡 틀린 이유

• 어제 숨바꼭질에서 time을 계속 누적하듯 하는 것 까진 맞았는데, 그 뒤가 아쉬웠다.
• visited를 언제 선언하고 안선언하는지 헷갈렸다.
• DFS든 BFS든 오류지점 선언과, 탈출조건을 잘 찾아서 써줘야하는데 그게 아쉬웠다.

💡 틀린 부분 수정 or 다른 풀이

• visited 선언 없이, graph에 값을 누적해갔다.

💡 느낀점 or 기억할정보

• 이동거리, time같은 정보로 최단시간/거리를 구할 때, graph를 덮어씌워가며 누적하는 방법을 잊지말자.