알고리즘 문제

백준 3197번 - 백조의 호수 (C++)

als982001 2025. 1. 18. 18:21

Image by Jürgen from Pixabay

 

 

https://www.acmicpc.net/problem/3197

 

1. 개요

 이 문제는 2차원 배열의 호수가 주어진다. 호수의 각 요소는 물('.'), 얼음('X'), 백조('L') 중 하나이고 백조는 총 2마리가 존재한다. 그리고 물과 상하좌우 중 한 곳이라도 접촉한 얼음은 하루가 지나면 녹아서 물이 된다. 이 때, 상하좌우로만 이동할 수 있는 백조는 며칠 후 서로 만날 수 있는지를 구하는 문제이다.

 이 문제의 알고리즘 분류에서도 알 수 있듯, 너비 우선 탐색(BFS)을 이용하여 문제를 풀었다. 처음에는 두 백조가 서로 만날 수 있는지 구하는 코드는 항상 하던 것처럼 큐를 이용하면 될 것이라 생각했다. 그리고 얼음의 경우에는 우선 단순하게 생각해서 새로운 2차원 배열을 만들고, 녹을 수 있는 얼음들을 기록한 후 기존 2차원 호수 배열을 업데이트하면 될 것이라고 생각했다. 이를 구현한 코드는 아래와 같다.

 

2. 풀이 01

#include <iostream>
#include <vector>
#include <queue>

#define MAX 1501

using namespace std;

int R, C;
bool meet = false;
int days = 0;
char lake[MAX][MAX];
char tempLake[MAX][MAX];
bool visited[MAX][MAX];
vector<pair<int, int>> swans;
int dir[4][2] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };

bool IsIn(pair<int, int> pos)
{
    int r = pos.first;
    int c = pos.second;
    
    return 0 <= r && r < R && 0 <= c && c < C;
}

bool CanMelt(pair<int, int> pos)
{
    for (int i = 0; i < 4; ++i)
    {
        pair<int, int> nxt = { pos.first + dir[i][0], pos.second + dir[i][1] };
        
        if (IsIn(nxt) && tempLake[nxt.first][nxt.second] == '.')
            return true;
    }
    
    return false;
}

void Melt()
{
    bool checked[MAX][MAX];
    
    for (int r = 0; r < R; ++r)
    {
        for (int c = 0; c < C; ++c)
        {
            tempLake[r][c] = lake[r][c];
            checked[r][c] = false;
        }
    }
    
    for (int r = 0; r < R; ++r)
    {
        for (int c = 0; c < C; ++c)
        {
            
            if (tempLake[r][c] == 'X' && checked[r][c] == false)
            {
                queue<pair<int, int>> q;
                q.push({ r, c });
                
                checked[r][c] = true;
                
                while(!q.empty())
                {
                    pair<int, int> cur = q.front();
                    q.pop();
                    
                    bool canMelt = CanMelt(cur);
                    
                    if (canMelt)
                        lake[cur.first][cur.second] = '.';
                    
                    for (int i = 0; i < 4; ++i)
                    {
                        pair<int, int> nxt = { cur.first + dir[i][0], cur.second + dir[i][1] };
                        
                        if (IsIn(nxt) && tempLake[nxt.first][nxt.second] == 'X' && checked[nxt.first][nxt.second] == false)
                        {
                            checked[nxt.first][nxt.second] = true;
                            q.push(nxt);
                        }
                    }
                }
            }
        }
    }
}

bool Meet()
{
    bool success = false;
    
    for (int r = 0; r < R; ++r)
    {
        for (int c = 0; c < C; ++c)
            visited[r][c] = false;
    }
    
    pair<int, int> destination = swans[1];
    
    queue<pair<int, int>> q;
    
    q.push(swans[0]);
    
    while(!q.empty())
    {
        pair<int, int> cur = q.front();
        q.pop();
        
        if (cur.first == destination.first && cur.second == destination.second)
        {
            success = true;
            break;
        }
        
        for (int i = 0; i < 4; ++i)
        {
            pair<int, int> nxt = { cur.first + dir[i][0], cur.second + dir[i][1] };

            
            if (IsIn(nxt) && visited[nxt.first][nxt.second] == false && lake[nxt.first][nxt.second] != 'X')
            {
                visited[nxt.first][nxt.second] = true;
                q.push(nxt);
            }
        }
    }
    
    return success;
}

int main()
{
    scanf("%d %d", &R, &C);
    
    for (int r = 0; r < R; ++r)
    {
        for (int c = 0; c < C; ++c)
        {
            cin >> lake[r][c];
                        
            if (lake[r][c] == 'L')
                swans.push_back({ r, c });
        }
    }
    
    while(meet == false && days < 10)
    {
        ++days;
        Melt();        
        meet = Meet();
    }
    
    printf("%d\n", days);

    return 0;
}

 

코드가 좀 길긴 하지만, 내용은 아래처럼 요약할 수 있다.

  1. 호수를 입력받는다.
    1. 만약 입력받은 값이 백조('L')일 경우, swans라는 벡터에 따로 저장한다.
  2. 반복문을 통해 아래의 내용들을 반복한다.
    1. 일수를 1 증가시킨다.
    2. 녹을 수 있는 얼음을 녹인다.
      1. 방문한 칸을 기록하는 2차원 배열(checked)을 초기화하고 기존 호수를 tempLake에 따로 저장한다.
      2. 기존 호수의 모든 칸을 한 번씩 검사한다. 만약 현재 칸이 얼음이면서 방문한 적이 없을 경우, 아래의 동작을 실행한다.
        1. 현재 칸이 녹을 수 있는 얼음(canMelt)이라면 lake의 값을 물('.')로 변경한다.
        2. 현재 칸의 상하좌우 칸(즉 다음 칸)이 얼음으면서 방문한 적이 없으면, 큐에 다음 칸을 넣어서 이 동작을 실행하게 한다.
    3. 백조가 만날 수 있는지 확인한다.
      1. swans의 첫 번째 값을 이동할 백조로 간주하여 큐에 넣고,  두 번째 값을 도착지(코드의 destination)로 설정한다.
      2. 큐가 비어있지 않을 경우 아래의 동작을 반복한다.
        1. 만약 현재 백조의 칸에 도착지일 경우, 두 백조가 만났다는 것을 return한다.
        2. 만약 현재 백조의 칸이 도착지가 아닐 경우, (상하좌우) 다음 칸이 얼음이 아니면서 방문한 적이 없으면 다음 칸을 큐에 넣는다.
    4. 백조가 만났을 경우에는 2번의 반복문을 종료한다.

 

위의 일련의 동작들을 확인해본 결과, 답은 제대로 나왔지만 시간이 초과되었다.

 

3. 풀이 02

 조금이라도 시간을 줄여보고자 얼음을 물로 바꾸는 함수, Melt의 로직을 변경하였다. 다시 한 번 생각해보니 한 번 반복할 때마다 모든 호수의 칸을 확인하지 않아도 되었기 때문이다. 호수의 얼음들에 대한 정보를 따로 저장한다면, 굳이 모든 호수의 칸을 확인하지 않아도 되며 시간을 줄일 수 있을 것이라 생각했다. 그래서 코드를 아래처럼 수정하였다.

 

#include <iostream>
#include <vector>
#include <queue>

#define MAX 1501

using namespace std;

int R, C;
bool meet = false;
int days = 0;
char lake[MAX][MAX];
bool visited[MAX][MAX];
vector<pair<int, int>> swans;
queue<pair<int, int>> ices;
int dir[4][2] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };

bool IsIn(pair<int, int> pos)
{
    int r = pos.first;
    int c = pos.second;
    
    return 0 <= r && r < R && 0 <= c && c < C;
}

bool CanMelt(pair<int, int> pos)
{
    for (int i = 0; i < 4; ++i)
    {
        pair<int, int> nxt = { pos.first + dir[i][0], pos.second + dir[i][1] };
        
        if (IsIn(nxt) && lake[nxt.first][nxt.second] == '.')
            return true;
    }
    
    return false;
}

void Melt()
{
    queue<pair<int, int>> melted;
    queue<pair<int, int>> notMelted;

    while(!ices.empty())
    {
        pair<int, int> ice = ices.front();
        ices.pop();
        
        bool canMelt = CanMelt(ice);
        
        if (canMelt)
            melted.push(ice);
        else
            notMelted.push(ice);
            
    }
    
    while(!melted.empty())
    {
        pair<int, int> meltedIce = melted.front();
        melted.pop();
        
        lake[meltedIce.first][meltedIce.second] = '.';
    }
    
    ices = notMelted;
}

bool Meet()
{
    bool success = false;
    
    for (int r = 0; r < R; ++r)
    {
        for (int c = 0; c < C; ++c)
            visited[r][c] = false;
    }
    
    pair<int, int> destination = swans[1];
    
    queue<pair<int, int>> q;
    
    q.push(swans[0]);
    
    while(!q.empty())
    {
        pair<int, int> cur = q.front();
        q.pop();
        
        if (cur.first == destination.first && cur.second == destination.second)
        {
            success = true;
            break;
        }
        
        for (int i = 0; i < 4; ++i)
        {
            pair<int, int> nxt = { cur.first + dir[i][0], cur.second + dir[i][1] };
            
            if (IsIn(nxt) && visited[nxt.first][nxt.second] == false && lake[nxt.first][nxt.second] != 'X')
            {
                visited[nxt.first][nxt.second] = true;
                q.push(nxt);
            }
        }
    }
    
    return success;
}

int main()
{
    scanf("%d %d", &R, &C);
    
    for (int r = 0; r < R; ++r)
    {
        for (int c = 0; c < C; ++c)
        {
            cin >> lake[r][c];
            
            if (lake[r][c] == 'L')
                swans.push_back({ r, c });
                
            if (lake[r][c] == 'X')
                ices.push({ r, c });
        }
    }
    
    while(meet == false)
    {
        ++days;
        Melt();
        meet = Meet();
    }
    
    printf("%d\n", days);

    return 0;
}

 

첫 번째 풀이와 달라진 부분은 다음과 같다.

  • 호수의 각 칸을 입력받을 때, 만약 얼음일 경우 ices라는 큐에 그 칸을 저장한다.
  • Melt 함수에서 아래의 동작들을 수행한다.
    • ices 큐의 모든 요소(얼음)마다, 만약 얼음이 녹을 수 있는 얼음이라면 melted라는 큐에 넣고, 그렇지 않으면 notMelted라는 큐에 넣는다.
    • melted 큐의 모든 요소의 위치에 해당하는 lake의 값을 물('.')로 변경한다.
    • ices 큐를 notMelted로 업데이트한다.

 

Melt 함수의 반복문 동작을 수정했기에 시간을 대폭 줄일 수 있을 것이라 기대했다. 하지만 여전히 시간이 초과되었다.

 

4. 풀이 03

 어디서 시간을 더 줄일 수 있을까 고민해보았는데, 백조가 서로 만날 수 있는지 확인하는 로직(Meet 함수)에서도 시간을 줄일 수 있다는 생각이 들었다. 위 로직을 보면, Meet을 실행할 때마다 visited를 초기화하는데, 한 번 방문했던 곳은 어차피 얼음이 녹더라도 또 방문할 수 있기에 Melt 후 또 확인할 필요가 없다. 이를 반영하여 코드를 수정해보았다.

 

#include <iostream>
#include <vector>
#include <queue>

#define MAX 1501

using namespace std;

int R, C;
bool meet = false;
int days = 0;
char lake[MAX][MAX];
bool visited[MAX][MAX];
queue<pair<int, int>> ices;
queue<pair<int, int>> swans;
pair<int, int> startSwan;
int dir[4][2] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };

bool IsIn(pair<int, int> pos)
{
    int r = pos.first;
    int c = pos.second;
    
    return 0 <= r && r < R && 0 <= c && c < C;
}

bool CanMelt(pair<int, int> pos)
{
    for (int i = 0; i < 4; ++i)
    {
        pair<int, int> nxt = { pos.first + dir[i][0], pos.second + dir[i][1] };
        
        if (IsIn(nxt) && lake[nxt.first][nxt.second] == '.')
            return true;
    }
    
    return false;
}

void Melt()
{
    queue<pair<int, int>> melted;
    queue<pair<int, int>> notMelted;

    while(!ices.empty())
    {
        pair<int, int> ice = ices.front();
        ices.pop();
        
        bool canMelt = CanMelt(ice);
        
        if (canMelt)
            melted.push(ice);
        else
            notMelted.push(ice);
            
    }
    
    while(!melted.empty())
    {
        pair<int, int> meltedIce = melted.front();
        melted.pop();
        
        lake[meltedIce.first][meltedIce.second] = '.';
    }
    
    ices = notMelted;
}

bool Meet()
{
    bool success = false;

    queue<pair<int, int>> afterMove;

    while(!swans.empty() && success == false)
    {
        pair<int, int> swan = swans.front();
        swans.pop();

        for (int i = 0; i < 4; ++i)
        {
            pair<int, int> movedSwan = { swan.first + dir[i][0], swan.second + dir[i][1] };

            if (IsIn(movedSwan) && visited[movedSwan.first][movedSwan.second] == false)
            {
                visited[movedSwan.first][movedSwan.second] = true;

                char& movedSwanPos = lake[movedSwan.first][movedSwan.second];

                switch(movedSwanPos)
                {
                    case 'X':
                        afterMove.push(movedSwan);
                        break;
                    case 'L':
                        success = true;
                        break;
                    case '.':
                        swans.push(movedSwan);
                        break;
                    default:
                        break;
                }
            }
        }
    }

    swans = afterMove;
    
    return success;
}

int main()
{
    scanf("%d %d", &R, &C);
    
    for (int r = 0; r < R; ++r)
    {
        for (int c = 0; c < C; ++c)
        {
            cin >> lake[r][c];
            
            if (lake[r][c] == 'L')
                startSwan = { r, c };
                
            if (lake[r][c] == 'X')
                ices.push({ r, c });
        }
    }

    swans.push(startSwan);
    visited[startSwan.first][startSwan.second] = true;
    
    while(meet == false)
    {
        meet = Meet();

        if (meet)
            break;

        ++days;

        Melt();        
    }
    
    printf("%d\n", days);

    return 0;
}

 

이번에 수정한 부분은 다음과 같다.

  • 백조가 존재한, 혹은 이동한 곳을 저장할 큐(swans)를 생성한다. 그리고 Melt, Meet을 반복하기 전 처음 입력받은 백조 위치 중 한 곳을 swans에 넣고, 이 곳을 방문했다고 기록한다.
  • Meet에서 swans 큐가 비거나 방문에 성공할 때까지 일련의 동작들을 반복한다.
    • 현재 위치에서 다음 칸으로 이동할 경우, 이동한 곳에 무엇이 있냐에 따라 다른 동작을 수행한다.
      • 얼음의 경우, 다음 Meet을 실행할 때 녹아서 물이 될 것이기에 afterMove라는 큐에 현재 위치를 저장한다.
      • 백조의 경우, 두 백조가 서로 만났다는 것이므로 서로 만났음을 기록한다.
      • 물의 경우, swans 큐에 다음 칸을 넣는다.
    • swans 큐를 (얼음의 경우에서 언급한) afterMove라는 큐의 값으로 업데이트한다. 

 

시간을 줄일 수 있는 방법은 다 적용한 것 같은데도 시간이 초괴가 되었다.

 

5. 풀이 04

 이전 풀이까지는 얼음의 위치를 저장했었다. 그런데 얼음의 위치보다는 물(혹은 백조)의 위치를 저장하는 것이 더 효율적일 것이라는 생각이 들었다. 왜냐하면 얼음으로 둘러싸인 얼음은 어차피 녹지 않을 것이기에 이런 얼음들에 대해서는 굳이 동작을 하지 않아도 되기 때문이다. 그리고 물을 저장할 경우, 처음 입력 받을 때는 모든 물을 저장하더라도 한 번 얼음이 녹는지 확인한 후에는 얼음과 접촉하여 물이 된 칸만 저장한다면 훨씬 효율적일 것이기 때문이다. 이러한 생각을 적용한 코드는 아래와 같다. 

 

#include <iostream>
#include <vector>
#include <queue>

#define MAX 1501

using namespace std;

int R, C;
bool meet = false;
int days = 0;
char lake[MAX][MAX];
bool visited[MAX][MAX];
queue<pair<int, int>> waters;
queue<pair<int, int>> swans;
pair<int, int> startSwan;
int dir[4][2] = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };

bool IsIn(pair<int, int> pos)
{
    int r = pos.first;
    int c = pos.second;
    
    return 0 <= r && r < R && 0 <= c && c < C;
}

void Melt()
{
    queue<pair<int, int>> meltedIces;

    while(!waters.empty())
    {
        pair<int, int> water = waters.front();
        waters.pop();
        
        for (int i = 0; i < 4; ++i)
        {
            pair<int, int> nxtPos = { water.first + dir[i][0], water.second + dir[i][1] };

            if (IsIn(nxtPos) && lake[nxtPos.first][nxtPos.second] == 'X')
            {
                meltedIces.push(nxtPos);
                lake[nxtPos.first][nxtPos.second] = '.';
            }
        }
            
    }
    
    waters = meltedIces;
}

bool Meet()
{
    bool success = false;

    queue<pair<int, int>> afterMove;

    while(!swans.empty() && success == false)
    {
        pair<int, int> swan = swans.front();
        swans.pop();

        for (int i = 0; i < 4; ++i)
        {
            pair<int, int> movedSwan = { swan.first + dir[i][0], swan.second + dir[i][1] };

            if (IsIn(movedSwan) && visited[movedSwan.first][movedSwan.second] == false)
            {
                visited[movedSwan.first][movedSwan.second] = true;

                char& movedSwanPos = lake[movedSwan.first][movedSwan.second];

                switch(movedSwanPos)
                {
                    case 'X':
                        afterMove.push(movedSwan);
                        break;
                    case 'L':
                        success = true;
                        break;
                    case '.':
                        swans.push(movedSwan);
                        break;
                    default:
                        break;
                }
            }
        }
    }

    swans = afterMove;
    
    return success;
}

int main()
{
    scanf("%d %d", &R, &C);
    
    for (int r = 0; r < R; ++r)
    {
        for (int c = 0; c < C; ++c)
        {
            cin >> lake[r][c];
            
            if (lake[r][c] == 'L')
                startSwan = { r, c };
                
            if (lake[r][c] != 'X')
                waters.push({ r, c });
        }
    }

    swans.push(startSwan);
    visited[startSwan.first][startSwan.second] = true;
    
    while(meet == false)
    {
        meet = Meet();

        if (meet)
            break;

        ++days;

        Melt();        
    }
    
    printf("%d\n", days);

    return 0;
}

 

변경된 부분은 다음과 같다.

  • 처음 입력을 받을 때, 얼음이 아닐 경우 waters라는 큐에 넣는다. 백조 역시 물에 존재하기 때문에 백조도 waters에 넣는다.
  • Melt 함수에서, waters에 저장된 각 물에 대해서 아래의 동작을 수행한다.
    • 상하좌우로 물에 접촉한 칸이 얼음일 경우, 이 얼음은 녹아서 물이 될 것이기에 meltedIces라는 큐에 저장하고 이 칸의 값을 물('.')로 변경한다.
    • waters 큐를 녹아서 물이된 칸들(meltedIces)로 업데이트한다.

 

이렇게 시간을 줄이고 줄여서 문제를 맞출 수 있었다.