반응형
https://www.acmicpc.net/problem/1261
1261번: 알고스팟
첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미한다. (1, 1)과 (N, M)은 항상 뚫려있다.
www.acmicpc.net
BFS를 사용하지만, BFS에서 사용하는 queue를 heap 자료구조로 활용해야 하는 독특한 문제.
heap을 사용하는 이유는 '벽을 가장 적게 부수고 이동하는 경우'가 항상 우선순위에 위치한 채 BFS로 순회해야 하기 때문.
이 개념을 생각 못해서 문제를 푸는 데 정말 오래 걸렸다.
반응형
'프로그래밍 > 코딩테스트 문제풀이' 카테고리의 다른 글
| [Python] 프로그래머스. 정수 삼각형 (Level 3) (0) | 2019.12.02 |
|---|---|
| [Python] 백준 3055. 탈출 (0) | 2019.12.01 |
| [Python] 프로그래머스. 단어 변환 (Level 3) (0) | 2019.11.29 |
| [Python] 프로그래머스. 2020 카카오 recruit - 기둥과 보 설치 (Level 3) (0) | 2019.11.28 |
| [Python] 프로그래머스. 단속카메라 (Level 3) (0) | 2019.11.27 |