문제
출처 : https://www.acmicpc.net/problem/14442
14442번: 벽 부수고 이동하기 2
첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자.
www.acmicpc.net
N*M크기의 맵이 있고, 이 맵은 벽과 땅으로 이루어져있다.
벽을 부술수있는 횟수 K가 주어질때, K번 이하로 벽을 부수면서 (N,K)지점에 도착하는 최소 거리를 구하는 문제다.
풀이
BFS에 3차원 체크배열로 재방문을 잡아내며푸는 문제였다.
체크배열을 3차원으로 지정해야하는 이유는, (y,x)지점에 도달했을때, 벽을 A+1번 부순횟수보다 A번 부순횟수가 작더라도, 이 후에는 더 커질수 있기때문이다. 쉽게 생각해서 지금 벽을 부수지 않고 돌아간 후 나중에 벽을 부수는 것이 더 작은 경로가 될 수 있다는 이야기이다.
한가지 특이한점은 이 문제는 자바의 경우 (다른 언어는 모른다.) 최소힙을 사용하면 시간초과가 나온다는 점 이다.
나는 처음에 우선 최소힙으로 최소경로를 찾아준 후, 이 다음부터 나오는 최소경로 보다 큰 경로는 모두 제거해주는방식으로 구현했는데(사실 바로 return해도 되는데 시간초과가 나오는건 변함없음), 계속해서 시간초과가 나왔다.
이런 유형의 문제를 풀어본적이 있어서 알고리즘에는 오류가 없다고 생각했고, 잡아내지못한 예외가 있나 찾아보다가 PriorityQueue를 Queue로 바꾸니 AC를 맞았다.
아마... PriorityQueue를 정렬하는데 필요한 비용이 항상 최솟값을 우선적으로 찾는 비용보다 큰 테스트케이스가 있는것 같다.
전체소스코드
'알고리즘 (2020 : 08 : 10 ~ ) > BFS,DFS' 카테고리의 다른 글
| [백준 / BOJ] 2251 물통 (cpp) (0) | 2023.02.10 |
|---|---|
| [백준 / BOJ] 18809 Gaaaaaaaaaarden (Java) (0) | 2022.06.03 |
| [백준 / BOJ] 1765 닭싸움 팀 정하기 (Java) (0) | 2021.08.30 |
| [백준 / BOJ] 5827 What's Up With Gravity (0) | 2021.05.14 |
| [백준 / BOJ] 14466 소가 길을 건너간 이유 6 (Java) (0) | 2021.05.12 |