문제 링크(Link)
https://www.acmicpc.net/problem/16236
문제 해결(Solution)
반복적인 BFS와 Sort를 이용해서 문제를 해결한다. 단, 구현이 까다롭다.
주의할 점 || 생각해볼 점(Caution || Consideration)
1. 생각해야하는 조건
: 이 문제는 생각해야하는 조건들이 많다. 그 중 가장 까다로운 것이 '어떤 물고기를 먹을 것인가?' 다. 이는 vector를 이용해서 쉽게 해결할 수 있다. vector<pair<int, pair<int, int> > >를 해서 거리, row, col 순으로 저장하면 단순한 sort함수를 통해서 다음에 먹을 물고기를 쉽게 찾을 수 있다.
2. 시간 복잡도는?
: 인접행렬로 구현했기 때문에 BFS는 N^2, sort() 함수를 사용했기 때문에 정렬은 NlgN. 그러므로 시간복잡도는 O(N^3*lgN)
참고(Reference)
-
※ 정확하고 부드러운 태클은 언제나 환영입니다.
'Problem Solving > 그래프_최단 거리' 카테고리의 다른 글
BOJ 4179 - 불! (3) | 2017.11.03 |
---|---|
BOJ 2206 - 벽 부수고 이동하기 (0) | 2017.10.19 |
BOJ 9370 - 미확인 도착지 (0) | 2017.07.29 |