[2667] c# 풀이 단지번호 붙이기 - DFS

DFS (깊이 우선 탐색) 방법으로 풀이했습니다.

C#을 이용한 풀이입니다.

[ 문제 풀이 ]

using System;
using System.collections.Generic;
using System.Linq;

namespace Programs
{
    public class Program
    {
    	private static int[,] array;
        private static readonly int[,] dir = new int[,]{{-1, 0}, {1, 0}, {0,-1}, {0, 1}};
        private static int count = 1;
        private static Dictionary<int, int> sorted;
        
        public static void Main()
        {
            var r = int.Parse(Console.ReadLine());
            
            array = new int[r,r];
            
            for (int i = 0; i<r; i++)
            {
            	var re = Console.ReadLine();
                
                for(int j=0; j<r; j++)
                {
                	array[i, j] = int.Parse(re[j].ToString());
                }
            }
            
            for (int i = 0; i<array.GetLength(0); i++)
            {
            	for (int j=0; j<array.GetLength(0); j++)
                {
                    if (array[i,j] == 1)
                    {
                        Dfs(i, j, ++count);
                    }
                }
            }
            
            sorted = new Dictionary<int, int>();
            
            foreach(var item in array)
            {
            	if (item == 0) continue;
                
                if (!sorted.ContainsKey(item))
                	sorted.Add(item, 1);
                else
                	sorted[item] += 1;
            }
            
            Console.WriteLine(sorted.Count());
            
            var so = sorted.Values.ToList();
            
            so.Sort();
            
            so.ForEach(x => { Console.WriteLine(x); });
        }
        
        private static void Dfs(int i, int j, int v)
        {
            array[i, j] = v;
            
            for (int k=0; k<4; k++)
            {
            	var dy = i + dir[k, 0];
                var dx = j + dir[k, 1];
                
                if (IsCheck(dy, dx) && array[dy, dx] == 1)
                {
                	Dfs(dy, dx, v);
                    count++;
                }
            }
        }
        
        private static bool IsCheck(int dy, dx)
        {
        	return (dy >= 0 && dy < array.GetLength(0) && 
            		(dx >= 0 && dx < array.GetLength(0)));
        }
    }
}

 

[ 주의 ]

풀이하면서 놓칠 수 있는 부분 참조 : https://www.acmicpc.net/board/view/27731

[ 테스트 케이스 ]

3               5
010             11000
101             00000
010             00000
                00001
4               00000
1
1               2
1               1
1               2