본문 바로가기

백준 문제 풀이 및 피드백

2023.01.15 미로탐색 백준

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

 

2178번: 미로 탐색

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

www.acmicpc.net

 

import sys
from collections import deque

input = sys.stdin.readline

def bfs():
    pos = [0,0]
    discoverd = deque([pos])
    while discoverd:
        if pos == [N-1,M-1]:
            break 
        pos = discoverd.popleft()
        maze[pos[0]][pos[1]] = 0
        dx_pos = [[pos[0],pos[1]-1],[pos[0],pos[1]+1],[pos[0]-1,pos[1]],[pos[0]+1,pos[1]]] 
        # 상하좌우 아래 for문에 때려 박을 수도 있지만 한개코드가 길어보여서 그냥 만듬
        for i in dx_pos:
            if 0 <= i[0] < N and 0<=i[1]<M and i not in discoverd and maze[i[0]][i[1]]:
                discoverd.append(i)
                least_dis[i[0]][i[1]] = least_dis[pos[0]][pos[1]] + 1
    return least_dis[N-1][M-1]

N, M = map(int,input().split())

maze = [list(map(int,input().strip())) for _ in range(N)]
least_dis = [[0]*M for _ in range(N)]
print(bfs()+1)

bfs를 사용해서 최단거리를 구해줬다. 어떤 곳으로 가든 가중치가 똑같고 상태가 변하지 않아서 bfs를 사용했다. 

중간에 bfs의 최단거리를 어디서 더해줘야하는지 고민하다가 도움을 받아서 least_dis라는 리스트를 하나 더 만들어서 각 좌표의 최소이동 거리를 구했다. 마지막에 +1을 한 이유는 0,0일 때도 거리가 1로 시작하기 때문에 1을 더해줬다.