[백준] 백조의 호수 3197번 (c++)

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

 

풀이 방법

 

처음에는 매 번 visited를 초기화하고 BFS를 두 번씩 수행하면서 얼음을 녹이고, 백조가 만날 수 있는지 확인하는 방식을 사용했다. 그러나 이 방법은 시간 초과가 발생한다.

 

이를 개선하기 위해, 다음 턴에 녹일 얼음을 따로 큐에 저장해 두고, 해당 얼음들만 녹인 뒤 인접한 얼음을 다시 큐에 넣는 방식으로 변경한다. 이렇게 하면 불필요한 중복 연산을 줄여 얼음을 녹이는 알고리즘의 시간 복잡도를 낮출 수 있다.

 

백조가 만날 수 있는지 확인할 때에도, 첫 번째 백조 위치에서 BFS를 진행하며 물과 인접한 얼음을 별도로 저장한다. 이후 턴에서 그 얼음이 녹았는지 확인한 뒤, 녹았다면 그 지점부터 다시 BFS를 탐색하며, 녹지 않았다면 다음 턴에서 계속 확인하도록 관리한다. 이로써 이전 턴에서 이미 확인한 물의 위치를 중복 검사하지 않아 시간 복잡도를 한층 더 줄일 수 있다.

 

이 방식에서 두 번의 BFS를 할 때마다 ‘visited’를 초기화하지 않는 점이 핵심이며, 또한 초기 백조 위치도 물로 간주해야 함을 놓치지 말아야 한다.

코드

 

#include <iostream>
#include <vector>
#include <memory.h>
#include <queue>

using namespace std;

string board[1501];
int visited[1501][1501];
int swan_visited[1501][1501];
int r, c;

int dy[4] = {0, 0, 1, -1};
int dx[4] = {1, -1, 0, 0};

queue<pair<int, int> > melt; // 이전에 녹은 얼음
vector<pair<int, int> > swan; // 백조 위치
queue<pair<int, int> > meet_loc; // 이전 턴에 물과 인접한 얼음의 위치 


// 초기 백조의 상태확인
bool init_swan() {
    memset(swan_visited, 0, sizeof(visited));
    queue<pair<int, int> > q;
    q.push(make_pair(swan[0].first, swan[0].second));
    swan_visited[swan[0].first][swan[0].second] = 1;
    while(!q.empty()) {        
        pair<int, int> now = q.front();
        q.pop();
        for (int i = 0;i < 4;i++) {
            int ny = now.first + dy[i];
            int nx = now.second + dx[i];
            if (ny < 0 || ny >= r || nx < 0 || nx >= c) continue;
            if (swan_visited[ny][nx] == 1) continue;
            if (ny == swan[1].first && nx == swan[1].second) return true;
            if (board[ny][nx] == 'X') { // 물이랑 인접한 얼음인 경우 다음 번 조사할 때 해당 지점에서 bfs를 수행한다.
                meet_loc.push(make_pair(ny, nx));
                swan_visited[ny][nx] = 1;
            }
            if (board[ny][nx] == '.') { // 물이라면 오리 이동 시켜보기
                q.push(make_pair(ny, nx));
                swan_visited[ny][nx] = 1;                
            }
        }
    }
    return false;

}   


void melt_ice() {    
    queue<pair<int, int> > temp;
    while(!melt.empty()) {        
        pair<int, int> now = melt.front();
        melt.pop();
        board[now.first][now.second] = '.'; // 얼음을 녹임
        for (int i = 0;i < 4;i++) {
            int ny = now.first + dy[i];
            int nx = now.second + dx[i];
            if (ny < 0 || ny >= r || nx < 0 || nx >= c) continue;
            if (visited[ny][nx] == 1) continue;
            if (board[ny][nx] == 'X') { // 물과 인접한 얼음인 경우 다음에 탐색할 위치로 저장하기
                temp.push(make_pair(ny, nx));
                visited[ny][nx] = 1;
            }
        }
    }
    melt = temp;
    return ;
}

void ice_bfs(int y, int x) {    
    queue<pair<int, int> > q;
    q.push(make_pair(y, x));
    visited[y][x] = 1;
    while(!q.empty()) {        
        pair<int, int> now = q.front();
        q.pop();
        for (int i = 0;i < 4;i++) {
            int ny = now.first + dy[i];
            int nx = now.second + dx[i];
            if (ny < 0 || ny >= r || nx < 0 || nx >= c) continue;
            if (visited[ny][nx] == 1) continue;
            if (board[ny][nx] == 'X') { // 다음 턴에 녹일 얼음
                melt.push(make_pair(ny, nx));
                visited[ny][nx] = 1;
                continue;
            }
            if (board[ny][nx] == '.') { // 물인 경우
                q.push(make_pair(ny,nx));
                visited[ny][nx] = 1;
            }            
        }
    }
}

// 처음에 녹일 얼음 선정
void pick_melt() { 
    memset(visited, 0, sizeof(visited));
    for (int i = 0;i < r;i++) {
        for (int j = 0;j < c;j++) { // 백조도 물로 취급한다.
            if (visited[i][j] == 0 && (board[i][j] == '.' || board[i][j] == 'L')) {
                ice_bfs(i, j);
            }
        }
    }
}


// 만나는지 체크하는 함수;

bool go_swan() {
    queue<pair<int ,int> > temp;
    while(!meet_loc.empty()) {        
        pair<int, int> now = meet_loc.front();
        meet_loc.pop();
        if (board[now.first][now.second] == 'X') { // 탐색 얼음이 녹지 않은 경우
            temp.push(now); // 다음 번에도 확인
            continue;
        }
        // 녹은 경우
        for (int i = 0;i < 4;i++) { // 주변 탐색 
            int ny = now.first + dy[i];
            int nx = now.second + dx[i];
            if (ny < 0 || ny >= r || nx < 0 || nx >= c) continue;
            if (swan_visited[ny][nx] == 1) continue;
            if (ny == swan[1].first && nx == swan[1].second) return true;
            if (board[ny][nx] == '.' && swan_visited[ny][nx] == 0) { // 물을 만났을 때 이동
                meet_loc.push(make_pair(ny, nx));
                swan_visited[ny][nx] = 1;
                continue;
            }
            if (board[ny][nx] == 'X') { // 벽을 만났을 때 다음에 녹는지 확인 후보
                temp.push(make_pair(ny, nx));
                swan_visited[ny][nx] = 1;
                continue;
            }
        }
    }
    meet_loc = temp;
    return false;
}

int main() {
    cin >> r >> c;

    for (int i = 0;i < r;i++) {
        cin >> board[i];
        for (int j = 0;j < c;j++) {
            if (board[i][j] == 'L') swan.push_back(make_pair(i, j));
        }
    }
    int t = 0;
    pick_melt();
    if (init_swan()) {
        cout << 0;
        return 0;
    }

    while(true) {
        t++;        
        melt_ice();        
        if(go_swan()) break;        
    }    
    cout << t << endl;
    return 0;
}