4963번: 섬의 개수 www.acmicpc.net 이 문제는 섬과 바다 지도가 주어질 때 섬의 개수를 세는 문제이다. 단, 두 정사각형이 같은 섬에 있기 위해서는 두 정사각형이 가로, 세로 또는 대각선으로 인접하고 있어야 한다. 이는 그래프 탐색을 이용해 쉽게 해결할 수 있다. 우선 깊이 우선 탐색이나 너비 우선 탐색 중 하나를 구현한 뒤, 지도 내 모든 정사각형을 방문하면서 만약 해당 정사각형이 섬의 일부인 경우 그 정사각형과 연결되어 있고, 섬의 일부인 모든 정사각형을 방문하는 그래프 탐색을 진행한다. 그러면 이후 그 섬을 다시 방문했을 경우 이미 방문한 섬이기에 섬의 개수를 셀 때 영향을 끼치지 않는다. 단, 보통 문제와는 달리 두 정사각형이 가로, 세로, 또는 대각선으로 인접한 경우 하나의 섬 ..
