[백준] 3197 백조의 호수

 

BFS를 이용해 풀 수 있는 문제다

2년전에 풀다가 직접 누구나 풀 수있는 방법인

매번 bfs하고 얼음녹이기를 했다가 시간초과나서 틀렸었다 ㅎㅎ

 

시간을 어떻게 줄일까 고민하다가 실패했는데

오늘 질문을 보다가 얼음을 매번녹이지말고 다음에 녹을것을 큐에 넣으라는 말을 봤다

그제서야 떠올랐다..!!  이런 생각은 어케하는걸까

 

문제를 푸는 방법은 bfs를 2개 돌린다고 생각하면 된다

백조 1마리가 도는 bfs와 땅(== '.') 이 도는 bfs

 

먼저 백조가 갈 수 있는 땅은 모두 다 가야한다

그리고 녹아야 할 땅을 bfs를 통해 모두 녹여준다

 

이걸 반복하는데 백조가 갈 수 있는 땅에 인접한 얼어있는 땅은

백조 bfs에서 check를 true로 바꿔주고 

얼음 bfs에서 큐에 넣어준다

 

이 작업이 백조가 다음날부터 갈 수 있는 땅을 큐에 넣어주는 작업이다

 

이렇게 하면 시간안에 너무너무 충분하게 들어온다!

 

다른 사람들은 유니온파인드를 썼는데 그걸 한번 봐야겠다..!

 

소스코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
char map[1505][1505];
bool check[1505][1505];
bool dcheck[1505][1505];
int Sx=-1,Sy,Ex,Ey,n,m;
int dx[4] = {0,0,-1,1};
int dy[4] = {1,-1,0,0};
 
bool inner(int x,int y){
    return (0<=x && x<n && 0<=y && y<m);
}
 
int main(){
    queue<pair<int,int>> dot,q;
    scanf(" %d %d",&n,&m);
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            scanf(" %1c",&map[i][j]);
            if(map[i][j]=='L'){
                if(Sx==-1) Sx=i,Sy=j;
                else Ex=i,Ey=j;
            }
            if(map[i][j] !='X') {
                dot.push({i,j});
                dcheck[i][j]=true;
            }
        }
    }
 
    q.push({Sx,Sy});
    check[Sx][Sy]=true;
    int ans=0;
    while(int s = q.size()){
        while(!q.empty()){
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
            if(x==Ex && y==Ey){
                printf("%d\n",ans); return 0;
            }
            for(int i=0;i<4;i++){
                int nx = x+dx[i];
                int ny = y+dy[i];
                if(inner(nx,ny) && map[nx][ny] != 'X' && !check[nx][ny]){
                    check[nx][ny]=true;
                    q.push({nx,ny});
                }
                if(inner(nx,ny) && map[nx][ny]=='X') check[nx][ny]=true;
            }
        }
        int ds = dot.size();
        while(ds--){
            int x = dot.front().first;
            int y = dot.front().second;
            dot.pop();
 
            for(int i=0;i<4;i++){
                int nx = x+dx[i];
                int ny = y+dy[i];
                if(inner(nx,ny) && map[nx][ny]=='X' && !dcheck[nx][ny]){
                    dcheck[nx][ny]=true;
                    map[nx][ny]='.';
                    dot.push({nx,ny});
                    if(check[nx][ny]) q.push({nx,ny});
                }
            }
        }
        ans++;
    }
}

 

+++

유니온 파인드를 이용해 풀어봤따!

 

참고하며 풀었는데 이렇게 거꾸로 생각한다는게 참 신기하다

먼저 큐에는 점을 다 넣어준다

그리고 bfs를 돌며 X가 아니라면 merge를 시켜주고

X라면 큐에넣고 점으로 바꿔준다

이 때 check배열을 통해 방금 점으로 바꾼곳은 merge를 시키지 않았다

처음에 큐에 X를 넣고 점으로 바꾸지 않아서 계속 큐에들어가고 메모리 초과가 났다

 

 

어렵게 풀었다 깔끔하지는 않은것같다 내 코드는!

 

소스코드

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
int n,m,Sx=-1,Sy,Ex,Ey;
char map[1505][1505];
bool check[1505][1505];
int p[1505 * 1505];
int dx[4] = { 0,0,-1,1 };
int dy[4] = { 1,-1,0,0 };
 
bool inner(int x, int y) {
    return (0 <= x && x < n && 0 <= y && y < m);
}
 
int find(int x) {
    if (p[x] == x) return x;
    return p[x] = find(p[x]);
}
 
void merge(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return;
    p[x] = y;
}
 
int main() {
    //freopen("input.txt", "r", stdin);
    for (int i = 0; i < 1500 * 1500 + 2; i++) p[i] = i;
    scanf(" %d %d", &n, &m);
    queue<pair<int, int>> q;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf(" %1c", &map[i][j]);
            if (map[i][j] == 'X') continue;
            if (map[i][j] == 'L') {
                if (Sx == -1) Sx = i, Sy = j;
                else Ex = i, Ey = j;
                map[i][j] = '.';
            }
            q.push({ i,j });
        }
    }
    int ans = 0;
    while (int s = q.size()) {
        memset(check, 0, sizeof(check));
        while (s--) {
            int x = q.front().first;
            int y = q.front().second;
            q.pop();
            for (int i = 0; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (!inner(nx, ny)) continue;
                if (map[nx][ny] == 'X') {
                    q.push({ nx,ny });
                    check[nx][ny] = true;
                    map[nx][ny] = '.';
                }
                else {
                    if(!check[nx][ny]) merge(find(x*m + y), find(nx*m + ny));
                }
            }
        }
        if (find(Sx*m + Sy) == find(Ex*m + Ey)) {
            printf("%d\n", ans); return 0;
        }
        ans++;
    }
}