문제 링크
- http://icpc.me/16000
사용 알고리즘
- 단절점
시간복잡도
- $O(NM)$
풀이
인접한 바다들, 인접한 육지들은 dfs/bfs 등을 이용해 각각 한 개의 정점으로 압축해줄 수 있습니다.
인접한 같은 셀들을 묶어준 그래프를 생각해봅시다.
예제 2, 3번을 그래프로 나타내면 아래 그림과 같이 나옵니다.
만약 A섬에서 최외곽 셀로 가기 위해 B섬을 무조건 지나야 한다면, B섬을 나타내는 정점이 없어지면 최외곽을 나타내는 정점이 있는 컴포넌트로 이동하지 못한다는 것을 의미합니다.
이것은 B가 단절점 이라는 것을 의미합니다.
이제 문제는 단절점을 지나지 않고 각 섬에서 최외곽 정점으로 가는 경로가 존재하는지 판별하면 됩니다.
이는 단절점을 찾는 알고리즘을 약간 변형해서 구해도 되고, dfs tree에서 단절점을 루트로 하는 서브트리에 속한 정점을 dfs ordering을 이용해 체크하는 방식으로 구해도 됩니다.