3197 백조의 호수

간선의 가중치가 0이 나올 수 있는 문제이므로, 덱을 이용하거나 큐를 2개 이용해서 해결해야만 한다. 다음과 같은 과정을 통해서 문제를 해결했다

 

1. 얼음이 녹는 시간을 bfs로 탐색해서 저장한다

2. 한 쪽 백조에 대해서 그룹 bfs를 진행하고, 외곽에 있는 땅에 대해서 따로 큐에 넣어준다

3. 다른 한 쪽 백조에 대해서 그룹 bfs를 진행한다

4. 얼음이 녹는 시간과 이동 시간이 같으면 다음 큐에, 이하라면 현재 큐에 계속 넣어서 가중치가 다른 조건에서의 bfs 탐색을 한다

 

문제: https://www.acmicpc.net/problem/3197

깃허브주소: https://github.com/surinoel/boj/blob/master/3197.cpp