[BOJ] 3197번 : 백조의 호수

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

3197번: 백조의 호수

 

꽤 복잡한 BFS 문제다. BFS로 해결해야 한다는 건 알겠는데, 하루가 지날 때마다 BFS를 쓰면 $O(E) \sim 10^7$ 를 최대 ${150 \over 2} = 75$번 수행하고, 백조도 다시 BFS를 써야 하므로, 여기에 2를 곱해주면 된다. 그럼 대충 $10^8 \times \alpha$가 나오는데.. 이대로 하면 TLE가 뜰 것이다..

 

따라서 조금 최적화를 해 줘야 하는데.. queue를 두 개 만들어서, 어제 X와 인접했던 지점들만 확인해서 인접한 얼음들을 녹여 주면 된다. 사방이 X거나 사방이 .인 지점은 확인할 필요가 없다. 백조도 같은 접근 방식을 사용하면 된다. 이미 방문한 지점들은 다시 방문하지 말고, 새로 얼음이 녹아서 갈 수 있게 된 지점들만 BFS로 확인해서, 그 안에 다른 백조가 위치해 있는지 확인하면 된다.

 

이렇게 하면 time complexity가 $O(E)$ 언저리로 줄어드니까.. 해결할 수 있다.

 

다만 전체를 뭉텅이들의 graph로 보고 union-find로 해결할 수도 있을 것 같은데.. 조금 더 고민해 볼 필요는 있다.

 

전체 코드는 내 github에서 확인할 수 있다.

https://github.com/Jordano-Jackson/PS/blob/main/BOJ/3197/3197.cpp 

---

References

Footnotes