Baekjoon 3197번 백조의 호수

문제

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

걸린 시간

- 실패

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int r, c;
int dy[4] = {1, -1, 0, 0};
int dx[4] = {0, 0, -1, 1};
vector<pair<int, int>> water, swan;
vector<vector<char>> lake;
vector<vector<int>> v1, v2; // visited
queue<pair<int, int>> q1, q2;

bool moveSwan(){
    vector<pair<int, int>> tmp;
    while(!q2.empty()){
        int cy = q2.front().first;
        int cx = q2.front().second;
        q2.pop();
        if(cy == swan[1].first && cx == swan[1].second) return true;
        for(int i = 0; i < 4; i++){
            int ny = cy+dy[i];
            int nx = cx+dx[i];
            if(0 <= ny && ny < r && 0 <= nx && nx < c){
                if(!v2[ny][nx]){
                    if(lake[ny][nx] == 'X') tmp.push_back(make_pair(ny, nx));
                    else q2.push(make_pair(ny, nx));
                    v2[ny][nx] = 1;
                }
            }
        }
    }
    for(int i = 0; i < tmp.size(); i++)
        q2.push(make_pair(tmp[i].first, tmp[i].second));
    return false;
};

int meltsIce(){
    v1.resize(r, vector<int>(c, 0));
    v2.resize(r, vector<int>(c, 0));
    int y, x;
    // water : v1, q1
    for(int i = 0; i < water.size(); i++){
        y = water[i].first;
        x = water[i].second;
        q1.push(make_pair(y, x));
        v1[y][x] = 1;
    }
    // swan : v2, q2
    y = swan[0].first;
    x = swan[0].second;
    q2.push(make_pair(y, x));
    v2[y][x] = 1;
    // bfs
    int day = 0;
    while(!q1.empty()){
        if(moveSwan()) return day;
        day++;
        int size = q1.size();
        for(int i = 0; i < size; i++){
            int cy = q1.front().first;
            int cx = q1.front().second;
            q1.pop();
            for(int j = 0; j < 4; j++){
                int ny = cy+dy[j];
                int nx = cx+dx[j];
                if(0 <= ny && ny < r && 0 <= nx && nx < c){
                    if(!v1[ny][nx] && lake[ny][nx] == 'X'){
                        q1.push(make_pair(ny, nx));
                        v1[ny][nx] = 1;
                        lake[ny][nx] = '.';
                    }
                }
            }
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> r >> c;
    lake.resize(r, vector<char>(c));
    for(int y = 0; y < r; y++){
        for(int x = 0; x < c; x++){
            cin >> lake[y][x];
            if(lake[y][x] == 'X') continue;
            if(lake[y][x] == 'L') swan.push_back(make_pair(y, x));
            water.push_back(make_pair(y, x));
        }
    }
    cout << meltsIce();
    return 0;
}

백조들이 만날 수 있을지를 bfs 로 확인할 때 이미 방문했던 장소는 다시 확인할 필요가 없다는 사실을 생각하지 못해 정답을 보게 되었다. (너무 당연한 사실인데...)

입력을 받으며 모든 물의 좌표를 queue 에 저장하고 각 좌표마다 인접한 얼음을 하나씩 제거해나간다. 동시에 백조들이 만날 수 있을지를 확인해야 하므로 총 2번의 bfs 가 진행된다.

기타 연산을 제외한 시간복잡도를 계산해보면, 2차원 행렬(R x C) 위의 모든 좌표를 상하좌우로 움직여 모두 방문할 경우 O(4RC)로 최악의 경우 2 x 4 x 1,500 x 1,500 = 18,000,000 번 수행되어 2초안에 통과할 수 있어 보인다.

다른 풀이방법으로는 얼음이 녹는데 걸리는 일 수를 구한 뒤 결정문제로 바꾸어 풀이하는 방법, bfs + 우선순위 큐, disjoint-set 여러가지가 있다.

다른 풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
#define all(c) c.begin(), c.end()
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

struct disjointSet{
    vector<int> parent, rank;
    disjointSet(int r, int c) : parent(r*c), rank(r*c, 1){
        for(int i = 0; i < r*c; i++)
            parent[i] = i;
    }
    int find(int u){
        if(parent[u] == u) return parent[u];
        return parent[u] = find(parent[u]);
    }
    void merge(int u, int v){
        u = find(u); v = find(v);
        if(u == v) return;
        if(rank[u] > rank[v]) swap(u, v);
        parent[u] = v; 
        if(rank[u] == rank[v]) rank[v]++;
    }
};

int r, c;
int dy[4] = {-1, 1, 0, 0};
int dx[4] = {0, 0, -1, 1};
vector<vector<char>> lake;
vector<vector<int>> visited;
vector<pair<int, int>> water, swan;
queue<pair<int, int>> q;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> r >> c;
    disjointSet d(r, c);
    lake.resize(r, vector<char>(c)); 
    visited.resize(r, vector<int>(c, 0));
    for(int y = 0; y < r; y++)
        for(int x = 0; x < c; x++){
            cin >> lake[y][x];
            if(lake[y][x] == '.')
                q.push(make_pair(y, x));
            if(lake[y][x] == 'L'){
                swan.push_back(make_pair(y, x));
                q.push(make_pair(y, x));
            }
        }
    // bfs
    int day = 0;
    while(!q.empty()){
        vector<pair<int, int>> wall;
        int size = q.size();
        for(int i = 0; i < size; i++){
            int y = q.front().first;
            int x = q.front().second;
            q.pop();
            if(visited[y][x]) continue;
            visited[y][x] = 1;
            for(int j = 0; j < 4; j++){
                int ny = y+dy[j];
                int nx = x+dx[j];
                if(0 <= ny && ny < r && 0 <= nx && nx < c){
                    if(lake[ny][nx] == 'X')
                        wall.push_back(make_pair(ny, nx));
                    else{ // . L
                        d.merge(y*c+x, ny*c+nx);
                        q.push(make_pair(ny, nx));
                    }
                }
            }
        }
        if(d.find(swan[0].first*c+swan[0].second) == d.find(swan[1].first*c+swan[1].second)){
            cout << day << "\n";
            return 0;
        }
        day++;
        for(int i = 0; i < wall.size(); i++){
            int y = wall[i].first;
            int x = wall[i].second;
            q.push(make_pair(y, x));
            lake[y][x] = '.';
        }
        wall.clear();
    }
    return 0;
}

분리 집합(disjoint set)을 이용한 풀이이다.

분리집합의 구현에서 2차원 배열의 호수의 각 원소를 pair<int, int> 형태로 map 을 사용해서 관리하였더니 메모리 초과가 출력되어 정답을 보았다.

2차원 배열을 한줄로 풀어 나열했을 때, 좌표를 (y축 좌표 * 최대 x축 크기) + x축 좌표 로 계산하면 인덱스별로 고유한 값을 가질 수 있어 1차원 배열만으로도 관리가 가능했다.

bfs + bfs 풀이에 비해 두배정도의 실행시간이 나왔다.

참고

[BOJ 3197] 백조의 호수 - 종난아! 공부하자! - 티스토리