[백준] 2178번: 미로 탐색 - Python

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

 

아이디어

• 최단거리 -> BFS 사용
• 입력받은 리스트를 수정하며 몇번째 방문인지 표시함과 동시에 방문 여부도 표시
  • 이동하기 이전 좌표의 값 + 1 한 값을 저장하며 진행
• 그럼 (N, M) 좌표의 값을 출력하면 끝 

구현

from collections import deque

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

miro = [list(map(int, list(input().strip()))) for _ in range(N)]

q= deque()
q.append((0,0))

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

while q:
    y, x = q.popleft()
    for i in range(4):
        ny = y+dy[i]
        nx = x+dx[i]
        if 0<=ny<N and 0<=nx<M:
            if miro[ny][nx] == 1:
                miro[ny][nx] = miro[y][x] + 1
                q.append((ny, nx))

print(miro[N-1][M-1])

 

마무리

기본 BFS 문제는 이제 쉽게 풀린다.

담부턴 좀 더 난이도 있는 문제로 풀기 시작해야겠다. ㅇㅅㅇ