[백준] 3197번 백조

[적용한 알고리즘]

BFS

-> BFS, 유니온파인드

 

[아이디어]

BFS 2개면 될거 같았다.

-> 문명이랑 똑같이 풀어주면 된다. BFS에 유니온 파인드를 곁들이면 된다.

 

[생각의 흐름 / 절차] 

1. 백조가 갈 수 있는지 없는지 검사

1-1) 갈 수 있으면 종료

1-2) 갈 수 없으면 2로 이동

2. 얼음 테두리 녹이기

3. ans+1 해준 뒤 1부터 반복

 

1. 물끼리 (+백조 포함해서) union 해준다.

2. 백조가 같은 영역 (=같은 root node를 공유하는지)를 find 함수를 통해 찾아준다.

3. 물 영역 확장하기.

4. 2번 조건을 만족할때까지 쭉 돌려준다.

 

[교훈]

자꾸 시간 초과가 나온다 어떻게 더 줄일 수 있을까..

path 가 있는지 없는지를 굳이 BFS를 돌려보지 않아도

"같은 영역에 있다." 를 통해 알 수 있다. 한참 멀었구나.

<코드>

 

<실패했을 때의 코드 (쌍 BFS)>

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef struct {
    int x;
    int y;
} cord;

int R, C;
char lake[1502][1502];
bool visited[1502][1502];
int dist[1502][1502];
int dirx[] = {-1, 1, 0, 0};
int diry[] = {0, 0, -1, 1};
queue<cord> q_Swan;
queue<cord> q_Lake;
queue<cord> q_Lake_nxt;

bool inLake(int x, int y){
    if (0 <= x && x < R && 0 <= y && y < C) return true;
    return false;
}
void bfs_lake(){
    while (!q_Lake.empty()){
        int curx = q_Lake.front().x;
        int cury = q_Lake.front().y;
        q_Lake.pop();

        for (int i = 0; i < 4; i++){
            int nx = curx + dirx[i];
            int ny = cury + diry[i];

            if (inLake(nx, ny)){
                if (lake[nx][ny] == 'X'){
                    lake[nx][ny] = lake[curx][cury];
                    q_Lake_nxt.push({nx, ny});
                }
            }
        }
    }
}

bool bfs_swan(int x1, int y1, int x2, int y2){
    q_Swan.push({x1, y1});
    visited[x1][y1] = true;

    while (!q_Swan.empty()){
        int curx = q_Swan.front().x;
        int cury = q_Swan.front().y;
        q_Swan.pop();

        if (curx == x2 && cury == y2){
            return true;
        }

        for (int i = 0; i < 4; i++) {
            int nx = curx + dirx[i];
            int ny = cury + diry[i];

            if (inLake(nx, ny)){
                if (lake[nx][ny] != 'X' && !visited[nx][ny]){
                    visited[nx][ny] = true;
                    q_Swan.push({nx, ny});
                    dist[nx][ny] = dist[curx][cury] + 1;
                }
            }
        }
    }
    return false;
}

int main(){
    int swan_cord[2][2]; // 백조의 (x,y) 저장
    int idx = 0;
    scanf("%d %d", &R, &C);
    for (int i = 0; i < R; i++){
        scanf("%s", lake[i]);
        for (int j = 0; j < C; j++){
            if (lake[i][j] == 'L'){
                swan_cord[idx][0] = i;
                swan_cord[idx][1] = j;
                idx++;

            }
            if (lake[i][j] == '.'){
                q_Lake.push({i, j});
            }
        }
    }

    int ans = 0;
    while (true){
        //백조가 갈 수 있는지 없는지 검사
        if(bfs_swan(swan_cord[0][0], swan_cord[0][1], swan_cord[1][0], swan_cord[1][1])){
            printf("%d\n", ans);
            break;
        }
        //얼음물 녹이기
        bfs_lake();

        q_Lake = q_Lake_nxt;
        while (!q_Lake_nxt.empty()){
            q_Lake_nxt.pop();
        }
        memset(dist, 0, sizeof(dist));
        memset(visited, 0, sizeof(visited));
        ans++;
    }

    return 0;
}

 

 

<성공한 코드>

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
typedef struct {
    int x;
    int y;
} cord;

int R, C;
int parent[1502 * 1502];
int swan[2][2]; // 백조의 (x,y) 저장
char lake[1502][1502];
int lake_map[1502][1502];
int dirx[] = {-1, 1, 0, 0};
int diry[] = {0, 0, -1, 1};
queue<cord> q_Lake, q_Melt;

int Find(int x){
    if (parent[x] == x) return x;
    return parent[x] = Find(parent[x]);
}

void Merge(int x, int y){
    x = Find(x);
    y = Find(y);

    if (x == y) return; //이미 같은 루트 노드 보유 중 Merge 필요 없음
    parent[x] = y;// merge 완료
}

bool inLake(int x, int y){
    if (0 <= x && x < R && 0 <= y && y < C) return true;
    return false;
}

void bfs_merge(){
    while (!q_Lake.empty()){
        int curx = q_Lake.front().x;
        int cury = q_Lake.front().y;
        q_Melt.push({curx, cury});
        q_Lake.pop();

        for (int i = 0; i < 4; i++){
            int nx = curx + dirx[i];
            int ny = cury + diry[i];

            if (inLake(nx, ny)){
                if (lake_map[nx][ny] > 0 && lake_map[curx][cury] != lake_map[nx][ny]){
                    Merge(lake_map[nx][ny], lake_map[curx][cury]);
                }
            }
        }
    }
}

void bfs_melt(){
    while (!q_Melt.empty()){
        int curx = q_Melt.front().x;
        int cury = q_Melt.front().y;
        q_Melt.pop();

        for (int i = 0; i < 4; i++){
            int nx = curx + dirx[i];
            int ny = cury + diry[i];

            if (inLake(nx, ny)){
                if (lake_map[nx][ny] == 0){
                    lake_map[nx][ny] = lake_map[curx][cury];
                    q_Lake.push({nx, ny});
                }
            }
        }
    }
}
int main(){
    int idx = 0;
    int cnt = 1;
    scanf("%d %d", &R, &C);
    for (int i = 0; i < R; i++){
        scanf("%s", lake[i]);
        for (int j = 0; j < C; j++){
            if (lake[i][j] == 'L'){
                swan[idx][0] = i;
                swan[idx][1] = j;
                idx++;
            }
            if (lake[i][j] == 'L' || lake[i][j] == '.'){
                lake_map[i][j] = cnt;
                parent[cnt] = cnt;
                cnt++;
                q_Lake.push({i, j});
            }
        }
    }

    int ans = 0;
    while (true){
        //얼음물 녹이기1 : 인접한 애들 merge, q로 해결해주면 된다.
        bfs_merge();

        //물끼리 union 해주면 된다.
        //백조가 갈 수 있는지 없는지 검사 : find로 알 수 있다.
        //if(find(백조1 좌표) == find(백조2 좌표)) 이면 탈출!
        if (Find(lake_map[swan[0][0]][swan[0][1]]) == Find(lake_map[swan[1][0]][swan[1][1]])){
            printf("%d\n", ans);
            return 0;
        }

        // 얼음물 녹이기2 : 물 영역 확장하기
        bfs_melt();
        ans++;
    }
}