[백준][3197] 백조의 호수

이 포스트는 백준 사이트의 백조의 호수 문제 풀이입니다.

문제

해결 과정

이 문제에서 결과를 출력하기 위해서는 3가지 행동을 반복해서 진행해야 합니다.

1. 두 마리의 백조가 만날 수 있는지 확인
2. 물에 인접한 얼음 녹이기
3. 출력할 날짜 증가

1번 과정의 경우, 탐색 알고리즘(BFS, DFS, … etc)를 사용하여 풀 수 있고
2번 과정은 물과 인접한 얼음들을 찾아 녹일 수 있습니다.

따라서 첫 번째 시도에서는 1번 과정에서 Queue 기반 BFS 를 사용해 두 백조의 경로를 탐색하고
2번 과정에서는 입력할 때, 저장했던 얼음을 순회하며 녹는지 확인했습니다.

첫 번째 시도 (시간 초과)

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

using namespace std;

struct POINT {
    enum TYPE {
        SWAN,
        ICE,
        WATER
    };

    int row, col;
    TYPE type;
};

int N, M;
vector<vector<char>> board;
vector<POINT> swans;
vector<POINT> ice;

void input() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M;

    board.assign(N, vector<char>(M, ' '));
    for(int row = 0; row < N; ++row) {
        string line;
        cin >> line;
        for(int col = 0; col < M; ++col) {
            board[row][col] = line[col];
            
            if('L' == board[row][col]) {
                swans.push_back({row, col, POINT::SWAN});
            } else if('X' == board[row][col]) {
                ice.push_back({row, col, POINT::ICE});
            }
        }
    }
}

bool disconnect_swan_pair() {
    queue<POINT> q;
    q.push(swans[0]);

    vector<vector<bool>> visited(N, vector<bool>(M, false));
    visited[swans[0].row][swans[0].col] = true;

    int dir_row[4]{-1, 1, 0, 0};
    int dir_col[4]{0, 0, -1, 1};
    while(false == q.empty()) {
        auto curr = q.front();
        q.pop();

        if(curr.row == swans[1].row && curr.col == swans[1].col) {
            return false;
        }

        for(int dir = 0; dir < 4; ++dir) {
            int new_row = curr.row + dir_row[dir];
            int new_col = curr.col + dir_col[dir];

            if(new_row < 0 || new_row >= N || new_col < 0 || new_col >= M)
                continue;
            if('X' == board[new_row][new_col])
                continue;
            if(visited[new_row][new_col])
                continue;

            visited[new_row][new_col] = true;
            q.push({new_row, new_col, POINT::SWAN});
        }
    }

    return true;
}

void melt_ice_board() {
    int dir_row[4]{-1, 1, 0, 0};
    int dir_col[4]{0, 0, -1, 1};

    auto next_board = board;
    for(auto& melt_ice : ice) {
        if(melt_ice.type != POINT::ICE) continue;

        for(int dir = 0; dir < 4; ++dir) {
            int new_row = melt_ice.row + dir_row[dir];
            int new_col = melt_ice.col + dir_col[dir];

            if(new_row < 0 || new_row >= N || new_col < 0 || new_col >= M)
                continue;
            if('.' == board[new_row][new_col]) {
                melt_ice.type = POINT::WATER;
                next_board[melt_ice.row][melt_ice.col] = '.';
            }
        }
    }

    board = next_board;
}

int main() {
    input();

    int today = 0;
    while(disconnect_swan_pair()) {
        melt_ice_board();
        today += 1;
    }

    cout << today;

    return 0;
}

두 번째 시도 (성공)

첫 번째 시도에서 시간 초과가 발생한 이유로는
1, 2번 과정 모두 중복된 연산을 수행하였기 떄문입니다.

1번 과정에서는 탐색 경로 단축 없이 매번 새롭게 탐색을 진행하였기 때문에 중복된 연산을 했습니다.
2번 과정에서는 얼음을 기준으로 계산하였기 때문에 물이 N x M 칸 중 1칸에만 존재할 경우,
N x M - 1 만큼의 연산이 낭비됩니다.

따라서 두 과정을 개선하기 위해
1번 과정에서 사용한 BFS의 재방문 방지 배열(visited)를 전역으로 승격시켜 중복된 연산을 막고
2번 과정에서는 얼음 기준의 연산을 물 기준의 연산으로 변경하였습니다.

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

using namespace std;

struct POINT {
    int row, col;
};

int N, M;
int dir_row[4]{-1, 1, 0, 0};
int dir_col[4]{0, 0, -1, 1};

vector<vector<char>> board;
vector<vector<bool>> visited;
vector<POINT> goal;
queue<POINT> swans, water;

void input();
bool connect_swan_pair();
void melt_ice_board();

int main() {
    input();

    int today = 0;
    while(false == connect_swan_pair()) {
        melt_ice_board();
        today += 1;
    }

    cout << today;

    return 0;
}

void input() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M;
    board.assign(N, vector<char>(M, ' '));
    visited.assign(N, vector<bool>(M, false));

    for(int row = 0; row < N; ++row) {
        string line;
        cin >> line;
        for(int col = 0; col < M; ++col) {
            board[row][col] = line[col];
            
            if('L' == board[row][col]) {
                water.push({row, col});
                goal.push_back({row, col});
            } else if('.' == board[row][col]) {
                water.push({row, col});
            }
        }
    }

    swans.push(goal[0]);
}

bool connect_swan_pair() {
    queue<POINT> next_swan;
    while(false == swans.empty()) {
        auto curr = swans.front();
        swans.pop();
        
        if(curr.row == goal[1].row && curr.col == goal[1].col) {
            return true;
        }

        for(int dir = 0; dir < 4; ++dir) {
            int new_row = curr.row + dir_row[dir];
            int new_col = curr.col + dir_col[dir];

            if(new_row < 0 || new_row >= N || new_col < 0 || new_col >= M)
                continue;
            if(visited[new_row][new_col])
                continue;
            visited[new_row][new_col] = true;

            if('X' == board[new_row][new_col]) {
                next_swan.push({new_row, new_col});
            } else {
                swans.push({new_row, new_col});
            }
        }
    }

    swans = next_swan;
    return false;
}

void melt_ice_board() {
    int curr_water_cnt = water.size();
    while(curr_water_cnt--) {
        auto melt_ice = water.front();
        water.pop();

        for(int dir = 0; dir < 4; ++dir) {
            int new_row = melt_ice.row + dir_row[dir];
            int new_col = melt_ice.col + dir_col[dir];

            if(new_row < 0 || new_row >= N || new_col < 0 || new_col >= M)
                continue;
            if('X' != board[new_row][new_col])
                continue;
            water.push({new_row, new_col});
            board[new_row][new_col] = '.';
        }
    }
}

실행 결과