C# 백준 3197 백조의 호수(너비우선탐색)

 

3197번: 백조의 호수

IDEA

만약 문제가 "얼음이 전부 녹는 데 걸리는 시간은?" 이었다면 정말 간단히 풀 수 있는 문제다.

이 문제의 함정은 얼음이 녹을 때마다 백조가 만날 수 있는지 없는지 여부를 확인한다는 것에 있다.

여기서 '매일 녹여보고 확인해보면 되지 않을까?' 생각했지만 호수의 범위가 가로 1~1500칸, 세로 1~1500칸이다.

만약 이 방법을 사용한다면 최대 225만칸을 확인해야하는데 무조건 시간초과가 나올 것이다.

다른 분들의 풀이를 보면서 어떻게 접근해야하는지 알았다.

이 문제는 큐를 여러개 사용해야한다.

 

기존의 아이디어를 알고리즘화 하면 이렇게 된다.

1) 얼음을 녹이기 위한 BFS 큐를 하나 사용한다.

2) 한 수준의 탐색이 끝나면 백조가 만날 수 있는지 BFS 큐를 하나 더 사용한다.

3) 백조가 만나지 못했다면 1) 로 돌아간다.

 

여기서 마지막 탐색이 이루어진 위치, 그러니까 얼음을 녹이는 경우 물에서 얼음을 만났을 때,

백조의 경우 얼음을 만났을 때, 각각의 좌표를 기억해두고 다음 BFS를 그 시점에서 시작한다.

그렇다면 매번 번거롭게 처음부터 탐색을 하는 헛수고를 하지 않아도 된다.

탐색 범위가 좁다면 별 의미가 없겠지만 탐색 범위가 넓을수록, 탐색이 길어질수록 절약할 수 있는 시간은 훨씬 커진다.

따라서 매 탐색이 끝날 때마다 끝난 곳의 위치를 새로운 큐에 저장한다.

얼음을 녹이는 BFS, 백조를 찾는 BFS 각각 하나씩의 큐가 더 필요하다.

이렇게 총 4개의 큐를 생성하고 탐색을 실행한다.

매 탐색마다 시간을 1씩 증가시키고 백조를 만났다면 시간을 출력하고 코드를 종료한다.

 

SourceCode

using System;
using System.Collections.Generic;
public class Location
{
    public int x;
    public int y;
    public Location(int a, int b)
    {
        x = a;
        y = b;
    }
}
class Program
{
    static int R, C, day, r, c;
    static int[,] lake = new int[1500, 1500];
    static bool[,] wcheck = new bool[1500, 1500];
    static bool[,] scheck = new bool[1500, 1500];
    static Queue<Location> water = new Queue<Location>();
    static Queue<Location> Nwater = new Queue<Location>();
    static Queue<Location> swan = new Queue<Location>();
    static Queue<Location> Nswan = new Queue<Location>();
    static void Main()
    {
        var rc = Console.ReadLine().Split();
        R = int.Parse(rc[0]); C = int.Parse(rc[1]);
        for (int i = 0; i < R; i++)
        {
            var row = Console.ReadLine();
            for (int j = 0; j < C; j++)
            {
                if (row[j] == '.') lake[i, j] = 0;      // 0 : water
                else if (row[j] == 'X') lake[i, j] = 1; // 1 : glacier
                else lake[i, j] = -1;                   // -1: swan
            }
        }
        for (int i = 0; i < R; i++)
        {
            for (int j = 0; j < C; j++)
            {
                if (lake[i, j] < 1)
                {
                    water.Enqueue(new Location(i, j));
                    wcheck[i, j] = true;
                }
                if (lake[i, j] == -1)
                {
                    swan.Enqueue(new Location(i, j));
                    scheck[i, j] = true;
                }
            }
        }
        scheck[swan.Peek().x, swan.Peek().y] = false;
        swan.Dequeue();
        while (true)
        {
            while (Nwater.Count > 0)
            {
                r = Nwater.Peek().x; c = Nwater.Peek().y;
                if (lake[r, c] == 1) lake[r, c] = 0;
                water.Enqueue(new Location(r, c));
                Nwater.Dequeue();
            }                               // Nwater 빙하 녹이고
                                            // water  으로 큐 옮기기
            while (water.Count > 0)
            {
                r = water.Peek().x; c = water.Peek().y;
                if (r > 0 && !wcheck[r - 1, c])
                {
                    if (lake[r - 1, c] == 1) Nwater.Enqueue(new Location(r - 1, c));
                    else water.Enqueue(new Location(r - 1, c));
                    wcheck[r - 1, c] = true;
                }
                if (c > 0 && !wcheck[r, c - 1])
                {
                    if (lake[r, c - 1] == 1) Nwater.Enqueue(new Location(r, c - 1));
                    else water.Enqueue(new Location(r, c - 1));
                    wcheck[r, c - 1] = true;
                }
                if (r < R - 1 && !wcheck[r + 1, c])
                {
                    if (lake[r + 1, c] == 1) Nwater.Enqueue(new Location(r + 1, c));
                    else water.Enqueue(new Location(r + 1, c));
                    wcheck[r + 1, c] = true;
                }
                if (c < C - 1 && !wcheck[r, c + 1])
                {
                    if (lake[r, c + 1] == 1) Nwater.Enqueue(new Location(r, c + 1));
                    else water.Enqueue(new Location(r, c + 1));
                    wcheck[r, c + 1] = true;
                }                               // water  좌표 상하좌우 확인하고
                                                // 빙하 있으면 Nwater에 Enqueue,
                                                // 빙하 없으면  water에 Enqueue
                water.Dequeue();
            }
            while (Nswan.Count > 0)
            {
                r = Nswan.Peek().x; c = Nswan.Peek().y;
                swan.Enqueue(new Location(r, c));
                Nswan.Dequeue();
            }                               // Nswan에서 swan으로 큐 옮기기
            while (swan.Count > 0)
            {
                r = swan.Peek().x; c = swan.Peek().y;
                if (r > 0 && !scheck[r - 1, c])
                {
                    if(lake[r - 1, c] == -1)
                    {
                        Console.WriteLine(day);
                        return;
                    }
                    else if (lake[r - 1, c] == 1) Nswan.Enqueue(new Location(r - 1, c));
                    else swan.Enqueue(new Location(r - 1, c));
                    scheck[r - 1, c] = true;
                }
                if (c > 0 && !scheck[r, c - 1])
                {
                    if (lake[r, c - 1] == -1)
                    {
                        Console.WriteLine(day);
                        return;
                    }
                    else if (lake[r, c - 1] == 1) Nswan.Enqueue(new Location(r, c - 1));
                    else swan.Enqueue(new Location(r, c - 1));
                    scheck[r, c - 1] = true;
                }
                if (r < R - 1 && !scheck[r + 1, c])
                {
                    if (lake[r + 1, c] == -1)
                    {
                        Console.WriteLine(day);
                        return;
                    }
                    else if (lake[r + 1, c] == 1) Nswan.Enqueue(new Location(r + 1, c));
                    else swan.Enqueue(new Location(r + 1, c));
                    scheck[r + 1, c] = true;
                }
                if (c < C - 1 && !scheck[r, c + 1])
                {
                    if (lake[r, c + 1] == -1)
                    {
                        Console.WriteLine(day);
                        return;
                    }
                    else if (lake[r, c + 1] == 1) Nswan.Enqueue(new Location(r, c + 1));
                    else swan.Enqueue(new Location(r, c + 1));
                    scheck[r, c + 1] = true;
                }
                swan.Dequeue();
            }
            day++;
        }
    }
}

큐에 2개 이상의 값을 저장하는 방법을 새로 적용해봤다.

Queue<(int, int)> 와 같은 해괴한 표현보다는 훨씬 실용적이고 깔끔한 것 같다.

 

BFS에서 if문을 두 번씩 겹쳐썼는데 가독성이 영 별로인 것 같고 메모리, 시간 면에서 효율이 많이 떨어지는 것 같다.

더 깔끔한 방법을 찾아봐야겠다.