BOJ 백준 2573 : 빙산

시작하면서

이번 문제는 너비 우선 탐색(BFS) 카테고리 문제이다.

BOJ 2573 - 빙산

​

문제 이해

​ 이 문제는 언뜻 보면 매번 갱신했을 때 시간초과가 나지 않을까 싶은 문제이다. 하지만 최악의 경우를 생각했을 때 빙산이 존재할 수 있는 최대 10,000개 * 각 칸에 들어가는 값 10 = 100,000 이므로 무식하게 전부 돌려도 시간초과가 발생하지 않는다.

​

해결

using System;
using System.Collections.Generic;

public class Solution
{
    static readonly int[,] direction = { { -1, 0 }, { 1, 0 }, { 0, 1 }, { 0, -1 } };

    class MeltingIceberg
    {
        public KeyValuePair<int, int> Point;
        public int MeltingCount;

        public MeltingIceberg(KeyValuePair<int ,int> p, int c)
        {
            this.Point = p;
            this.MeltingCount = c;
        }
    };

    static void Main()
    {
        string[] line = Console.ReadLine().Split();
        int N = Convert.ToInt32(line[0]);
        int M = Convert.ToInt32(line[1]);

        int currentIcebergCount = 0;
        List<List<int>> icebergLists = new List<List<int>>();
        for (int i = 0; i < N; i++)
        {
            icebergLists.Add(new List<int>());
            icebergLists[i].Capacity = M;

            line = Console.ReadLine().Split();
            for (int j = 0; j < M; j++)
            {
                icebergLists[i].Add(Convert.ToInt32(line[j]));
                if (icebergLists[i][j] != 0)
                {
                    currentIcebergCount++;
                }
            }
        }

        int yearCount = 0;
        while (true)
        {
            // 1. 시작 위치 찾기
            bool[,] isVisited = new bool[N, M];
            Queue<KeyValuePair<int, int>> queue = new Queue<KeyValuePair<int, int>>();
            for (int i = 0; i < N; i++)
            {
                for (int j = 0; j < M; j++)
                {
                    if (icebergLists[i][j] != 0)
                    {
                        queue.Enqueue(new KeyValuePair<int, int>(i,j));
                        isVisited[i, j] = true;
                        break;
                    }
                }
                if (queue.Count != 0)
                    break;
            }

             //**빙산이 남지 않았을 때 예외 처리
            if (queue.Count == 0)
            {
                yearCount = 0;
                break;
            }

            // 2. 빙산이 한 그룹에 모두 포함되어있는지 확인
            int findIcebergCount = 0;
            while (queue.Count > 0)
            {
                KeyValuePair<int, int> currentPoint = queue.Dequeue();
                findIcebergCount++;

                for (int i = 0; i < 4; i++)
                {
                    int row = currentPoint.Key + direction[i, 0];
                    int col = currentPoint.Value + direction[i, 1];
                    if (row < 0 || col < 0 || row >= N || col >= M)
                        continue;

                    if (isVisited[row, col] == true)
                        continue;

                    if (icebergLists[row][col] == 0)
                        continue;

                    queue.Enqueue(new KeyValuePair<int, int>(row, col));
                    isVisited[row, col] = true;
                }
            }
            
            // 2-.한 그룹이 아니면 중단
            if (findIcebergCount != currentIcebergCount)
                break;

            // 3. 녹을 빙산 정보 수집
            //    : 실시간으로 녹이면 다른 빙산에 영향을 주어서 답이 틀림.
            //    : 수집 후 나중에 따로 녹여줘야 함
            Queue<MeltingIceberg> meltingIcebergQueue = new Queue<MeltingIceberg>();
            for (int i = 0; i < N; i++)
            {
                for (int j = 0; j < M; j++)
                {
                    if (icebergLists[i][j] != 0)
                    {
                        int nearbyNoneIcebergCount = 0;
                        for (int k = 0; k < 4; k++)
                        {
                            int row = i + direction[k, 0];
                            int col = j + direction[k, 1];
                            if (row < 0 || col < 0 || row >= N || col >= M)
                                continue;

                            if (icebergLists[row][col] == 0)
                            {
                                nearbyNoneIcebergCount++;
                            }
                        }
                        
                        if (nearbyNoneIcebergCount > 0)
                        {
                            meltingIcebergQueue.Enqueue(new MeltingIceberg(new KeyValuePair<int, int>(i, j), nearbyNoneIcebergCount));
                        }
                    }
                }
            }

            // 3-. 녹일 빙산이 있으면 녹이기
            while (meltingIcebergQueue.Count > 0)
            {
                MeltingIceberg info = meltingIcebergQueue.Dequeue();
                icebergLists[info.Point.Key][info.Point.Value] -= info.MeltingCount;

                if (icebergLists[info.Point.Key][info.Point.Value] <= 0)
                {
                    icebergLists[info.Point.Key][info.Point.Value] = 0;
                    currentIcebergCount--;
                }
            }

            yearCount++;
        }

        Console.WriteLine(yearCount);
    }
}