[2178. 미로탐색]

링크텍스트

이 문제는 보면 되게 간단해보이는 DFS/BFS문제다.

벽들을 피해갔을 때, 얼마나 빨리 목적지에 다다를 수 있는지 tracking 하는 문제이고, 최단경로의 단순 탐색 뿐만 아니라 이동 횟수도 중요한 정보이기 때문에 BFS 방법을 택했다.

간만에 노치팅으로 한 문제를 완성하여 기분이가 매우 조은거시다💕

자 그럼 나의 코.드. 세상에 공.개.
특: 별거 없음 (^>^)

import sys
from collections import deque
n,m = map(int, sys.stdin.readline().split())
graph = []
for _ in range(n):
    graph.append(list(map(int, input())))
step=[[0 for _ in range(m)] for _ in range(n)]

여기까지는 입력을 재구성하는 단계이고, depth 마킹을 위해 step 리스트를 새로 구성했다.

중간에 count += 1을 추가해가면서 카운팅하려고 했더니, 왠지 모르는 오류가 발생했다;;

depth tracking을 위한 dummy array를 도입하는 것이 핵심

# 동서남북 direction 마킹
dr = [0,0,1,-1]
dc = [1,-1,0,0]

def bfs(n,m):
    q = deque() # BFS에서는 필수인 deque 지정
    q.append([0,0]) 
    while q: # 처리 que가 차있다면,
        cur = q.popleft()
        r = cur[0]
        c = cur[1]
        if graph[r][c] == 1: #검사하지 않은 경로라면,
            graph[r][c] = 0
            for p in range(4):
                newr = r+dr[p]
                newc = c+dc[p]
                if 0<=newr<=n-1 and 0<=newc<=m-1 and graph[newr][newc] == 1:
                    step[newr][newc] = step[r][c] + 1
                    q.append([newr,newc])

여기가 bfs의 본체다. 코드를 써내려가는 과정은 그렇게 어렵지는 않았지만, 아까 말했듯 count 변수 조건 설정이 조금의 허들이었다

bfs(n,m)
print(1+step[-1][-1])

나머지는 그저 EZPZ 그 잡채였다. 푸히히 😒