[백준 4963] 섬의 개수 (C#, C++) - soo:bak

문제 링크

4963번 - 섬의 개수

설명

땅과 바다로 이루어진 지도가 주어지고, 가로, 세로, 대각선으로 인접한 땅끼리는 하나의 섬으로 간주될 때, 지도에 존재하는 섬의 개수를 구하는 문제입니다.

여러 테스트 케이스가 주어지며, 각 테스트 케이스마다 지도의 너비와 높이, 그리고 각 칸의 정보가 입력됩니다.

너비와 높이가 모두 0으로 입력되면 입력이 종료됩니다.

접근법

지도의 모든 칸을 순회하면서 아직 방문하지 않은 땅을 발견하면, 그곳을 시작점으로 탐색을 시작합니다.

탐색 과정에서 현재 위치에서 8방향(상하좌우 및 대각선)으로 인접한 모든 땅을 찾아 방문 표시를 합니다.

이렇게 하나의 탐색이 끝나면 하나의 섬을 모두 확인한 것이므로 섬 개수를 증가시킵니다.

8방향 인접성을 확인하기 위해 현재 위치에서 상하좌우 및 네 개의 대각선 방향으로 이동합니다.

각 방향으로 이동할 때, 지도 범위를 벗어나지 않는지, 해당 위치가 땅인지, 이미 방문했는지를 확인합니다.

예를 들어, 3×3 지도에서 가운데 땅(1,1)이 있고 그 주변 8칸 중 오른쪽(1,2)과 대각선 오른쪽 아래(2,2)에 땅이 있다면, 이 세 칸은 모두 하나의 섬으로 연결됩니다.

각 테스트 케이스마다 새로운 지도와 방문 배열을 생성하여 독립적으로 처리합니다.

너비와 높이가 모두 0이 입력되면 모든 테스트 케이스 처리를 종료합니다.

---

Code

C#

using System;
using System.Collections.Generic;

namespace Solution {
  class Program {
    static readonly int[] dy = {-1,-1,-1, 0, 0, 1, 1, 1};
    static readonly int[] dx = {-1, 0, 1,-1, 1,-1, 0, 1};

    static void Main(string[] args) {
      while (true) {
        var first = Console.ReadLine()!.Split();
        var w = int.Parse(first[0]);
        var h = int.Parse(first[1]);

        if (w == 0 && h == 0) break;

        var board = new int[h][];

        for (var i = 0; i < h; i++) {
          var line = Console.ReadLine()!.Split();
          board[i] = new int[w];

          for (var j = 0; j < w; j++)
            board[i][j] = int.Parse(line[j]);
        }

        var visited = new bool[h][];

        for (var i = 0; i < h; i++)
          visited[i] = new bool[w];

        var islands = 0;

        for (var y = 0; y < h; y++) {
          for (var x = 0; x < w; x++) {
            if (board[y][x] == 0 || visited[y][x]) continue;

            islands++;

            var q = new Queue<(int y, int x)>();
            visited[y][x] = true;
            q.Enqueue((y, x));

            while (q.Count > 0) {
              var cur = q.Dequeue();

              for (var dir = 0; dir < 8; dir++) {
                var ny = cur.y + dy[dir];
                var nx = cur.x + dx[dir];

                if (ny < 0 || ny >= h || nx < 0 || nx >= w) continue;
                if (visited[ny][nx]) continue;
                if (board[ny][nx] == 0) continue;

                visited[ny][nx] = true;
                q.Enqueue((ny, nx));
              }
            }
          }
        }

        Console.WriteLine(islands);
      }
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<vi> vvi;
typedef vector<vb> vvb;
typedef pair<int, int> pii;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  const int dy[8] = {-1,-1,-1, 0, 0, 1, 1, 1};
  const int dx[8] = {-1, 0, 1,-1, 1,-1, 0, 1};

  while (true) {
    int w, h; cin >> w >> h;

    if (w == 0 && h == 0) break;

    vvi board(h, vi(w));

    for (int i = 0; i < h; i++)
      for (int j = 0; j < w; j++)
        cin >> board[i][j];

    vvb visited(h, vb(w, false));
    int islands = 0;

    for (int y = 0; y < h; y++) {
      for (int x = 0; x < w; x++) {
        if (board[y][x] == 0 || visited[y][x]) continue;

        ++islands;

        queue<pii> q;
        visited[y][x] = true;
        q.push({y, x});

        while (!q.empty()) {
          auto [cy, cx] = q.front();
          q.pop();

          for (int dir = 0; dir < 8; dir++) {
            int ny = cy + dy[dir];
            int nx = cx + dx[dir];

            if (ny < 0 || ny >= h || nx < 0 || nx >= w) continue;
            if (visited[ny][nx]) continue;
            if (board[ny][nx] == 0) continue;

            visited[ny][nx] = true;
            q.push({ny, nx});
          }
        }
      }
    }

    cout << islands << "\n";
  }

  return 0;
}