프로그래밍/코딩테스트 문제풀이
[Python] 백준 2206. 벽 부수고 이동하기
inspirit941
2019. 12. 4. 18:36
반응형
https://www.acmicpc.net/problem/2206
2206번: 벽 부수고 이동하기
N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 만약에 이동하는 도중에 한 개의 벽을 부수고 이동하는 것이 좀 더 경로가 짧아진다면, 벽을 한 개 까지 부수고 이동
www.acmicpc.net
BFS이면서 heapq 라이브러리를 활용하는 방식에서 실마리를 찾았고,
방문여부를 확인하는 visited배열에 하나의 dimension을 더 추가해야 한다는 개념을 이해한 다음에야 풀 수 있었던 문제.
반응형