백준 C# - 2667 +) 풀이

이 문제를 풀기 앞서 아래 문제를 풀고 오는 것을 추천한다. 2667이 아래 문제의 심화버전이다.

백준 C# - 1012

백준 C# - 1012 +) 풀이

---

백준 C# - 1012를 풀었다는 전제하에 문제 풀이를 진행하겠다.

출력에 필요한 두 부분

01 총 그룹의 갯수 출력(1012 : 지렁이의 갯수)

이 부분은 원래 1012와 동일하게 출력하면 된다.

02 단지내 집의 수 오름차순으로 출력(1012 : 각 지렁이에 해당되는 배추들의 수)

각 단지내 집의 수는 DFS가 호출되는 횟수와 동일하므로 DFS가 호출될때마다 이 값을 증가시킨다.

static void DFS(int x, int y)
{
    count++;
    graph[x, y] = 0;

    for (int i = 0; i<4;i++)
    {     
        int newX = x + dirX[i];
        int newY = y + dirY[i];
        if (graph[newX,newY] == 1)
        DFS(newX, newY);
    }
}

현재 그룹의 크기(count)는 DFS가 시작될때마다 초기화 시켜주어야 한다. 그리고 각 그룹의 크기를 answer리스트에 추가 해주어야 한다. 이를 추가한다음 다른 그룹을 찾아 이를 반복한다.

for (int i = 1; i <= N; i++)
{
    for (int j = 1; j <= N; j++)
    {
        if (graph[j, i] == 1)
        {
            count = 0;
            answer2++;
            DFS(j, i);
            answer.Add(count);
        }
    }
}

마지막으로 오름차순으로 정렬한 다음 출력한다.

answer.Sort();
foreach (int i in answer)
{
    Console.WriteLine(i);
}

---

코드 전문

using System;
using System.Collections.Generic;

namespace baek2
{
    class Program
    {
        static int[,] graph;
        static int count;
        static int[] dirX = { 1, -1, 0, 0 };
        static int[] dirY = { 0, 0, 1, -1 };
        static List<int> answer;
        static void DFS(int x, int y)
        {
            count++;
            graph[x, y] = 0;

            for (int i = 0; i < 4; i++)
            {
                int newX = x + dirX[i];
                int newY = y + dirY[i];
                if (graph[newX, newY] == 1)
                    DFS(newX, newY);
            }
        }
        public static void Main()
        {
            int N = int.Parse(Console.ReadLine());
            graph = new int[30, 30];
            visited = new bool[30, 30];
            answer = new List<int>(55);
            int answer2 = 0;
            for (int i = 0; i < N; i++)
            {
                string a = Console.ReadLine();
                int index = 1;
                foreach (char c in a)
                {
                    graph[i + 1, index] = c - '0';
                    index++;
                }
            }

            for (int i = 1; i <= N; i++)
            {
                for (int j = 1; j <= N; j++)
                {
                    if (graph[j, i] == 1)
                    {
                        count = 0;
                        answer2++;
                        DFS(j, i);
                        answer.Add(count);
                    }
                }
            }
            Console.WriteLine(answer2);
            answer.Sort();
            foreach (int i in answer)
            {
                Console.WriteLine(i);
            }
        }
    }
}