📖 문제 탐색

문제

• 지도가 주어지고, 1(땅)과 0(바다)로 이루어져 있다.
• 가로, 세로, 대각선으로 연결된 1들은 같은 섬이다.
• 지도에서 섬의 개수를 세어야 한다.

• 지도의 너비 $w$, 높이 $h$ (1 ≤ w, h ≤ 50) (지도의 크기 $w$x$h$ 행렬)
• (0, 0)이 입력되면 종료한다.

시간복잡도

• 지도 크기는 최대 50x50=2500 칸이다.
• 각 칸을 탐색하면서 연결된 칸을 탐색하는 문제이므로 그래프 탐색 (DFS/BFS)를 사용해야 한다.
• 한번 탐색된 정점은 다시 탐색하지 않기 때문에 $O(w\times h)$개의 정점을 탐색하게 된다. 한 정점에서 8가지 방향으로 이동할 수 있기 때문에 8 x $O(w\times h)$의 시간복잡도가 소요된다.
  • 상수 배수를 무시하면 $O(w\times h)$이다.

알고리즘

• 그래프 탐색 문제

• 한 지점에서 상하좌우, 대각선으로 인접한 곳으로 이동한다. 연결된 모든 지점을 이동한다.

  ⇒ 2차원 배열에서 상하좌우 또는 상하좌우, 대각선으로 이동하는 인접탐색을 진행한다면 BFS/DFS 떠올릴 것!