문제 링크 (https://www.acmicpc.net/problem/3055)
여름방학 때 들었던 알고리즘 특강에서 푼 문제! 그땐 강사님이 바로 해답을 알려주셔서 풀었는데 혼자 풀었다면 매우 헤맸을 듯 ㅎㅎ...
bfs로 해결하면 되는데 포인트는 고슴도치가 물이 찰 예정인 칸으로 이동할 수 없는 점이다. 현재 물이 차있는 칸도 아니고 물이 찰 예정인 칸을 어떻게 알지..? => 고슴도치보다 물을 먼저 이동시켜주면 된다!
입력받을 때 물의 좌표(여러 곳 가능), 고슴도치 좌표, 비버 좌표를 기억해둔다.
물과 고슴도치 둘 다 bfs를 해야 하므로 물과 고슴도치의 좌표를 담는 큐가 필요하다. 고슴도치는 물이 찰 예정인 칸으로 이동할 수 없으므로 bfs함수에서 고슴도치의 이동보다 물을 먼저 이동시켜준다.
1. 고슴도치가 비버의 굴에 도착했다면 => 거리를 출력하고 끝
2. 고슴도치가 더 이상 탐색을 할 수 없다면 => KAKTUS를 출력하고 끝
[소스코드]
'ALGORITHM > BOJ' 카테고리의 다른 글
[BOJ] 16234번 인구 이동 (C++) (0) | 2021.11.18 |
---|---|
[BOJ] 20055번 컨베이어 벨트 위의 로봇 (C++) (0) | 2021.10.22 |
[BOJ] 10026번 적록색약 (C++) (0) | 2021.10.14 |
[BOJ] 14501번 퇴사 (C++) (0) | 2021.10.09 |
[BOJ] 14502번 연구소 (C++) (0) | 2021.10.08 |