2573. 빙산 (C#)

문제

• 빙산 | 골드 IV (2025년 9월 1일 기준)
• 알고리즘 분류
  • 구현
  • 그래프 이론
  • 그래프 탐색
  • 너비 우선 탐색
  • 깊이 우선 탐색

접근

한 해가 지날 때 마다 빙산이 녹는 양은 인접한 바다 타일의 개수다. 이를 인접하지 않은 두 빙산으로 쪼개질 때 까지 걸린 햇수(위 상황에선 2가 정답)을 출력하는 것이 이 문제의 요구사항이다. 만약 빙산이 완전히 녹아 없어질 때 까지 쪼개지지 않았다면(빙산이 1조각인 상태를 유지했다면) 0을 출력한다. 인접의 기준은 상, 하 , 좌, 우 만 해당된다.

풀이

메인 함수에서 문제 풀이를 위한 기본 뼈대를 세우고 점점 작은 함수로 쪼개면서 문제를 풀었다.

입력 처리

static void Main(string[] args)
{
    /* 입력
     * 1. 이차원 배열의 행의 개수와 열의 개수 row col
     * 2. 3 <= row , col <= 300
     * 3. 빙산의 높이 -> 0 이상 10 이하
     */
    int[,] iceberg; //빙산 데이터
    string[] input = Console.ReadLine().Split(' ');
    int row = int.Parse(input[0]);
    int col = int.Parse(input[1]);
    iceberg = new int[row, col]; //동적배열 생성

    for (int i = 0; i < row; i++)
    {
        input = Console.ReadLine().Split(' ');
        for (int j = 0; j < col; j++)
        {
            iceberg[i, j] = int.Parse(input[j]);
        }
    }

    Console.WriteLine(calcDivide(iceberg, row, col));
}

메인 함수에서 문제의 입력과 정답 출력을 위한 뼈대를 먼저 작성했다.  calcDivide 메서드에 빙산 데이터, 행, 열 변수를 매개변수로 전달하고 내부에서 계산한 햇수(문제의 정답)을 콘솔에 출력하는 구조로 접근했다. 

빙산이 쪼개진 햇수 구하기

static int calcDivide(int[,] iceberg, int row, int col)
{
    int result = 0;

    while (countIsland(iceberg, row, col) == 1)
    {
        applyMelt(iceberg, row, col);
        result++;
    }

    if (countIsland(iceberg, row, col) == 0)
    {
        return 0;
    }
    else
    {
        return result;
    }
}

calcDivide에서는 빙산이 1조각인 동안 반복해서 applyMelt를 실행해서 빙산을 녹이면서 햇수를 기록한다. 빙산이 1조각이 아니게 되었을 때, 만약 빙산이 0조각인 경우(모든 빙산이 녹아 없어진 경우) 0을 반환하고 아닌 경우 햇수를 반환한다. 

빙산의 조각 세기

static int countIsland(int[,] iceberg, int row, int col)
{
    int result = 0; //섬의 개수
    bool[,] visited = new bool[row, col]; //방문 기록

    for (int i = 0; i < row; i++)
    {
        for (int j = 0; j < col; j++)
        {
            if (visited[i, j] || iceberg[i, j] == 0)
            {
                //이미 방문한 지점이거나 바다라면 pass
                continue;
            }
            //BFS
            Queue<Point> queue = new Queue<Point>();
            queue.Enqueue(new Point(i, j));
            visited[i, j] = true;
            while (queue.Count > 0)
            {
                Point curr = queue.Dequeue();
                Point[] cardinates = new Point[]
                {
                    new Point(curr.row + 1, curr.col),
                    new Point(curr.row - 1, curr.col),
                    new Point(curr.row, curr.col + 1),
                    new Point(curr.row, curr.col - 1)
                };
                foreach (Point p in cardinates)
                {
                    if (p.row >= 0 && p.col >= 0 && p.row < row && p.col < col && !visited[p.row, p.col] && iceberg[p.row, p.col] > 0)
                    {
                        queue.Enqueue(p);
                        visited[p.row, p.col] = true;
                    }
                }
            }
            result++;
        }
    }
    return result;
}

빙산의 조각을 세는것은 BFS로 구현할 수 있었다. 빙산 데이터의 모든 좌표를 순회하면서 아직 방문하지 않은 빙산을 발견하면 인접한 빙산을 BFS로 모두 찾아서 방문처리하고 result를 1증가 시킨다. 이렇게 하면 인접하지 않은 빙산의 갯수를 알아낼 수 있다.

빙산 녹이기 

static void applyMelt(int[,] iceberg, int row, int col)
{
    int[,] meltPower = new int[row, col];
    Stack<Point> stack = new Stack<Point>();

    for (int i = 0; i < row; i++) //녹는 정도 계산하기
    {
        for (int j = 0; j < col; j++)
        {
            if (iceberg[i, j] == 0) continue; //바다라면 pass

            Point[] cardinates = new Point[4] //상하좌우 후보위치
                {
                    new Point(i + 1, j),
                    new Point(i - 1, j),
                    new Point(i, j + 1),
                    new Point(i, j - 1)
                };


            int count = 0;
            foreach (Point p in cardinates)
            {
                if (p.row >= 0 && p.col >= 0 && p.row < row && p.col < col)
                {
                    if (iceberg[p.row, p.col] == 0)
                    {
                        count++;
                    }
                }

            }
            if (count > 0)
            {
                meltPower[i, j] = count; //녹는 정도 계산
                stack.Push(new Point(i, j)); //녹는 위치 기록
            }

        }
    }

    while (stack.Any()) //녹이기
    {
        Point p = stack.Pop();
        iceberg[p.row, p.col] -= meltPower[p.row, p.col];
        if (iceberg[p.row, p.col] < 0) iceberg[p.row, p.col] = 0; //음수가 되지 않게 cap
    }

    printIceberg(iceberg, row, col);
}

빙산은 한 번에 녹는다. 즉, 빙산이 녹는 사이클 중간에 바다가 된 타일은 빙산이 녹는 정도에 영향을 주지 않는 다는 것이다. 만약 빙산을 녹이는 과정중에 녹아서 바다가 된 타일이 다른 빙산 타일의 녹는 정도에 영향을 준다면 오답이 될 가능성이 있다. 그래서 빙산이 녹는 정도를 기록하는 meltPower 배열을 만들고, 각 빙산의 좌표를 모두 순회한 다음 한 번에 빙산이 녹는 정도를 적용했다. 추가로, 녹는 위치를 stack에 기록해서 시간 복잡도가 증가하지 않도록 했다.

 

코드를 살펴보니 메서드 이름이 죄다 소문자로 시작하고 있는데, 이 문제를 해결할 당시에는 이게 맞는 명명규칙인줄 알았던 것 같다.