[백준] 4963 - 섬의 개수

1. 문제

4963번: 섬의 개수

2. 개요

정사각형으로 이루어진 섬과 바다 지도가 주어진다. 가로 세로 대각선으로 연결되어있는 섬들은 한 개의 섬으로 간주한다. 이 때 섬의 개수를 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

모든 좌표를 탐색하며 아직 방문하지 않은 섬이 있다면 DFS를 진행한다. DFS를 실행하면서 답을 1씩 늘려주며 DFS를 진행하면서 방문한 모든 섬들을 방문처리한다.

모든 좌표를 탐색했다면 답을 출력한다.

3-2. Python

import sys

sys.setrecursionlimit(100000)

while True:
    w, h = map(int, sys.stdin.readline().split())

    if w == 0 and h == 0:
        break
    
    m = []
    visited = [[False for i in range(w)] for j in range(h)]
    answer = 0

    for i in range(h):
        m.append(list(map(int, sys.stdin.readline().split())))

    def DFS(y, x):
        dirY, dirX = [-1, -1, 0, 1, 1, 1, 0, -1], [0, -1, -1, -1, 0, 1, 1, 1]

        for i in range(8):
            nextY, nextX = y + dirY[i], x + dirX[i]

            if nextY < 0 or nextY >= h or nextX < 0 or nextX >= w:
                continue

            if visited[nextY][nextX] == True:
                continue

            if m[nextY][nextX] == 0:
                continue

            visited[nextY][nextX] = True
            DFS(nextY, nextX)

    for i in range(h):
        for j in range(w):
            if m[i][j] == 1 and visited[i][j] == False:
                answer += 1
                visited[i][j] = True
                DFS(i, j)

    print(answer)

3-3. C#

namespace boj_4963
{
    internal class Program
    {
        static bool[,] visited;
        static int[,] m;
        static int w;
        static int h;

        static void Main(string[] args)
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

            while (true)
            {
                string[] input = sr.ReadLine().Split();
                w = int.Parse(input[0]);
                h = int.Parse(input[1]);

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

                int answer = 0;
                visited = new bool[h, w];
                m = new int[h, w];

                for (int i = 0; i < h; i++)
                {
                    string[] row = sr.ReadLine().Split();

                    for (int j = 0; j < w; j++)
                    {
                        m[i, j] = int.Parse(row[j]);
                    }
                }

                for (int i = 0; i < h; i++)
                {
                    for (int j = 0; j < w; j++)
                    {
                        if (m[i, j] == 1 && visited[i, j] == false)
                        {
                            visited[i, j] = false;
                            answer++;
                            DFS(i, j);
                        }
                            
                    }
                }

                sw.WriteLine(answer);
            }

            sw.Close();
        }

        static void DFS(int y, int x)
        {
            int[] dirY = { -1, -1, 0, 1, 1, 1, 0, -1 };
            int[] dirX = { 0, -1, -1, -1, 0, 1, 1, 1 };

            for (int i = 0; i < 8; i++)
            {
                int nextY = y + dirY[i];
                int nextX = x + dirX[i];

                if (nextY < 0 || nextY >= h || nextX < 0 || nextX >= w)
                    continue;

                if (visited[nextY, nextX] == true)
                    continue;

                if (m[nextY, nextX] == 0)
                    continue;

                visited[nextY, nextX] = true;
                DFS(nextY, nextX);
            }
        }
    }
}