백준# 4963 - 섬의 갯수

https://www.acmicpc.net/problem/4963

4963번: 섬의 개수

이번 문제는 그래프로 분류된 섬의 개수 문제 입니다.

 

 

using System;
using System.Collections.Generic;
using System.Linq;
 
namespace _4963
{
    class Program
    {
        public class Island
        {
            public const int LAND = 1;
            public const int SEA = 0;
 
            public static int IslandCount;
 
            public int width;
            public int height;
            public List<List<int>> island;
 
            public Island(int width, int height, List<List<int>> island)
            {
                this.width = width;
                this.height = height;
                this.island = island;
            }
 
            public void DFS(int x, int y)
            {
                if (x < 0 || y < 0 || x >= this.width || y >= this.height)
                    return;
 
                if (this.island[x][y] == SEA)
                    return;
 
                this.island[x][y] = SEA;
 
                for(int i = x - 1; i <= x + 1; i++)
                {
                    for(int j = y - 1; j <= y + 1; j++)
                    {
                        this.DFS(i, j);
                    }
                }
            }
 
        }
 
        static void Main(string[] args)
        {
 
            while (true)
            {
                Island.IslandCount = 0;
 
                var rect = Console.ReadLine().Split(' ')
                    .Select(x => int.Parse(x)).ToList();
 
                if (rect[0] == 0 && rect[1] == 0)
                    return;
 
                var landInfo = new List<List<int>>();
 
                //땅과 바다 입력.
                for(int i = 0; i < rect[1]; i++)
                    landInfo.Add(Console.ReadLine().Split(' ')
                        .Select(x => int.Parse(x)).ToList());
 
                var island = new Island(rect[1], rect[0], landInfo);
 
                for(int i = 0; i < island.width; i++)
                {
                    for(int j = 0; j < island.height; j++)
                    {
                        if(island.island[i][j] == Island.LAND)
                        {
                            Island.IslandCount++;
                            island.DFS(i, j);
                        }
                    }
                }
 
                Console.WriteLine(Island.IslandCount);
            }
 
        }
    }
}
 

이번 문제는 아주 전형적인 그래프 문제 이지만?

그래프가 아닌.. 그런 문제 입니다.

 

그래프 또한 트리처럼 구성하는 방법이 중요한데 단순히 2차원 배열만 써도

풀 수 있으면서 전형적인 DFS, BFS를 사용하는 문제입니다.

 

2차원 배열 섬을 클래스로 정의했습니다.

땅의 한 점을 찍어 맞닿아 있는 영역을 넓혀가면 되는 문제 입니다.

최초 땅을 발견 한다면 count를 하나 올리고 맞닿은 영역이 모두 칠해질 때 까지

넓히면 되겠습니다.

 

 

한점에서 넓히기만 하면 따로 떨어진 영역은 칠해지지 않으므로

섬의 모든 땅을 한 번씩 전부 확인해야 합니다.

 

모든 영역이 바다로 칠해질 때 까지 DFS 하면 되겠습니다.