[백준|파이썬] 2178: 미로 탐색 (실버1)

문제

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

2178번: 미로 탐색

 

 

🐍파이썬

import sys
from collections import deque

N, M = map(int, sys.stdin.readline().split())
miro = []
for _ in range(N):
    miro.append(list(map(int, sys.stdin.readline().rstrip())))

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

def bfs(x, y):
    queue = deque()
    queue.append((x, y))
    while queue:
        x, y = queue.popleft()	#큐에 들어있는 가장 처음 노드를 꺼낸다.
        for i in range(4):	#상하좌우에 대해 아래의 코드를 반복한다.
            nx = dx[i] + x	#현재 좌표 x, y에 상하좌우를 더하여 상하좌우가 방문할 수 있는 경로인지 확인
            ny = dy[i] + y
            if nx >= N or ny >= M or nx < 0 or ny < 0:	#배열의 범위를 벗어난 경우 방문할 수 없는 경로이므로 건너뛰기
                continue
            if miro[nx][ny] == 0:	#벽으로 가로막힌 경우 방문할 수 없으므로 건너뛰기
                continue
            if miro[nx][ny] == 1:	#옳은 경로를 찾음
                miro[nx][ny] = miro[x][y] + 1	#지나온 경로 갯수(이동횟수)를 카운팅
                queue.append((nx, ny))	#옳은 경로를 큐에 삽입하여 다음 반복에서 이후 경로를 확인하도록 한다.
    return miro[N-1][M-1]	#목적지에 도달하면 카운팅 결과인 최종 이동횟수를 리턴

print(bfs(0, 0))

아이디어가 전혀 생각 안 나서 여러 블로그를 참고하여 문제를 풀었다.

문제가 손에 익을 정도로 여러번 반복해서 풀어봐야겠다.

 

알아둘 점: 최단거리 / 최단경로 문제는 BFS로 푼다.

이유: https://nulls.co.kr/graph/141

[그래프] 27. BFS로 찾은 경로가 최단 경로인 이유

 

 

추가

N, M: 4 6
miro: 101111 101010 101011 111011

while문을 돌 때마다 miro의 값 변화

[[1, 0, 1, 1, 1, 1],
[2, 0, 1, 0, 1, 0],
[1, 0, 1, 0, 1, 1],
[1, 1, 1, 0, 1, 1]]

[[3, 0, 1, 1, 1, 1],
[2, 0, 1, 0, 1, 0],
[3, 0, 1, 0, 1, 1],
[1, 1, 1, 0, 1, 1]]

[[3, 0, 1, 1, 1, 1],
[2, 0, 1, 0, 1, 0],
[3, 0, 1, 0, 1, 1],
[1, 1, 1, 0, 1, 1]]

[[3, 0, 1, 1, 1, 1],
[2, 0, 1, 0, 1, 0],
[3, 0, 1, 0, 1, 1],
[4, 1, 1, 0, 1, 1]]

[[3, 0, 1, 1, 1, 1],
[2, 0, 1, 0, 1, 0],
[3, 0, 1, 0, 1, 1],
[4, 5, 1, 0, 1, 1]]

[[3, 0, 1, 1, 1, 1],
[2, 0, 1, 0, 1, 0],
[3, 0, 1, 0, 1, 1],
[4, 5, 6, 0, 1, 1]]

[[3, 0, 1, 1, 1, 1],
[2, 0, 1, 0, 1, 0],
[3, 0, 7, 0, 1, 1],
[4, 5, 6, 0, 1, 1]]

[[3, 0, 1, 1, 1, 1],
[2, 0, 8, 0, 1, 0],
[3, 0, 7, 0, 1, 1],
[4, 5, 6, 0, 1, 1]]

[[3, 0, 9, 1, 1, 1],
[2, 0, 8, 0, 1, 0],
[3, 0, 7, 0, 1, 1],
[4, 5, 6, 0, 1, 1]]

[[3, 0, 9, 10, 1, 1],
[2, 0, 8, 0, 1, 0],
[3, 0, 7, 0, 1, 1],
[4, 5, 6, 0, 1, 1]]

[[3, 0, 9, 10, 11, 1],
[2, 0, 8, 0, 1, 0],
[3, 0, 7, 0, 1, 1],
[4, 5, 6, 0, 1, 1]]

[[3, 0, 9, 10, 11, 12],
[2, 0, 8, 0, 12, 0],
[3, 0, 7, 0, 1, 1],
[4, 5, 6, 0, 1, 1]]

[[3, 0, 9, 10, 11, 12],
[2, 0, 8, 0, 12, 0],
[3, 0, 7, 0, 13, 1],
[4, 5, 6, 0, 1, 1]]

[[3, 0, 9, 10, 11, 12],
[2, 0, 8, 0, 12, 0],
[3, 0, 7, 0, 13, 1],
[4, 5, 6, 0, 1, 1]]

[[3, 0, 9, 10, 11, 12],
[2, 0, 8, 0, 12, 0],
[3, 0, 7, 0, 13, 14],
[4, 5, 6, 0, 14, 1]]

[[3, 0, 9, 10, 11, 12],
[2, 0, 8, 0, 12, 0],
[3, 0, 7, 0, 13, 14],
[4, 5, 6, 0, 14, 15]]

[[3, 0, 9, 10, 11, 12],
[2, 0, 8, 0, 12, 0],
[3, 0, 7, 0, 13, 14],
[4, 5, 6, 0, 14, 15]]

[[3, 0, 9, 10, 11, 12],
[2, 0, 8, 0, 12, 0],
[3, 0, 7, 0, 13, 14],
[4, 5, 6, 0, 14, 15]]