[BOJ][Python]2178번 풀이

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

2178번: 미로 탐색

from collections import deque
import sys
ssr = sys.stdin.readline

def sol():
    while q:
        r,c,s = q.popleft()
        if r == n-1 and c == m-1:
            return s
        for i in range(4):
            if r+dr[i] < 0 or r+dr[i] >= n or c+dc[i] <0 or c+dc[i] >= m:
                continue
            else:
                if t[r+dr[i]][c+dc[i]] == '1' and visited[r+dr[i]][c+dc[i]] == False:
                    q.append((r+dr[i],c+dc[i],s+1))
                    visited[r+dr[i]][c+dc[i]] = True
        
n,m = map(int, ssr().split())
t = [list(ssr().rstrip()) for _ in range(n)]
q = deque([(0,0,1)])
visited = [[False for _ in range(m)] for _ in range(n)]
visited[0][0] = True
dr = [-1,1,0,0]
dc = [0,0,-1,1]
ans = sol()
print(ans)

사실 오늘은 상당히 감회가 새로웠습니다. 풀이를 작성하기 위해서 생각을 정리하던 중 너무 기본적인 bfs문제다 라는 생각이 들었는데요. 문득 예전에 bfs가 어려워서 낮은 난이도부터 고민하고 풀이를 찾아보던 기억이 나서 그래도 내가 성장을 하는구나 라는 생각이 들었습니다. 약간 뿌듯해지네요.

 

문제 접근은 많이 풀어오던 bfs 문제들과 동일합니다. 항상 몇번 지나쳤는지 몇일이 지났는지 등등을 체크하기 위해서 큐에 값을 함께 집어넣고 다음에는 올리고 하던 스킬이 생각이 나시나요? 이번에도 그와 동일하게 진행하시면 됩니다. 방문을 이미 했던 곳인지, 해당 위치가 벽이 아닌지를 체크한다음 큐에 넣어주기만 하면 쉽게 해결 가능한 문제입니다.

 

여전히 구현 문제는 풀어보면 실버 하위 티어에서도 조금 고민을 하는데 대놓고 무슨 알고리즘인지 알만한 문제들은 난이도가 높게 나와도 엄청 어렵지는 않네요. 어떻게든 이겨내겠다고 책도 빌리고 사고 유튜브 강의도 듣던 시절이 문득 기억이 나네요. 그렇게 오래되지도 않았습니다. 아마 5월까지만 해도 어떻게 공부를 해야하는지도 감이 안잡혀서 헤매던 기억이 나는데요. 지금 알고있던 걸 1년만 일찍 알았더라면 어땠을까하는 씁쓸함도 있습니다만 지금이라도 알아서 다행이라는 안도감이 드네요.