(Python/🥈1)백준 알고리즘 2178번: 미로탐색

문제출처: https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

풀이:

 

import sys
from collections import deque
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')



N, M = map(int,input().split(" "))
map = [list(map(int,input())) for i in range(N)]

visited = [ [-1] * (M) for i in range(N)] # 밟은거 확인
move = [(1,0),( -1,0),(0,-1),(0,1)] #상,하,좌,우

visited[0][0] = 1
Q = deque([(0,0)])

while Q:
    x,y = Q.popleft()
    if x == N-1 and y == M-1:
        print(visited[x][y])
    for (a,b) in move:
        dx , dy = x + a, y + b
        if N > dx >= 0 and M > dy >= 0 and visited[dx][dy] == -1 and map[dx][dy] == 1:
            Q.append((dx,dy))
            visited[dx][dy] = visited[x][y] + 1

 

 

map = 1과 0 으로 된 지도 그대로 가져옴
visited = 일단 다 -1 로 만들어놓음 밟으면서 거리 값 최신화 시키기 위해서
move = 상하좌우 좌표 저장
visited[0][0] = 첫 시작점 밟았으니깐 1로 최신화

 

bfs 탐색을 해야하므로 첫 Q 에 시작좌표임 (0,0) 을 넣어준다

 

for (a,b) in move:
    dx , dy = x + a, y + b
    if N > dx >= 0 and M > dy >= 0 and visited[dx][dy] == -1 and map[dx][dy] == 1:
        Q.append((dx,dy))
        visited[dx][dy] = visited[x][y] + 1

Q 에서 (x,y) 를 뽑아주고

move를 for 문으로 돌리면 만약 (0,0) 을 기준으로 하면 (-1,0),(0,1)(1,0)(0,-1) 이렇게 4방향을 가져온다.

 

그것과 현재 좌표 (0,0) 과 더하면 다음 좌표임 (dx,dy) 를 가져온다.

 

(dx,dy) 는 0보다 커야하고 x좌표의 길이보다는 작아야한다, y 좌표도 마찬가지다

그리고 방문 하려는 지점이 방문안된상태(-1) 이여야하면서, 밟을 수 있는 땅(1) 인 상태면

 

다음 좌표인 dx,dy 를 Q 에 넣어준다

그리고 거리값을 그 전 지점에서 +1 을 해주면 총 거리가 나온다.

 

x와 y가  (N-1, M-1) 가 같으면 종료후 리턴