백준 3197번: 백조의 호수

백준 3197: 백조의 호ㅇ

백준 3197번 백조의 호수

3197번: 백조의 호수

 

시뮬레이션 느낌이 나는 BFS 문제이다. 문제의 답을 내는대에는 많이 어렵지는 않지만 시간 제버 부분이 많이 촉박하다. 덕분에 시간초과로 꽤 애를 먹었다. BFS를 쓸 때 사용하는 visit 배열을 최소한으로 이용해야 bfs 탐색도 최소로 할 수 있다. 나는 물웅덩이를 최초에 큐에 넣는 과정에서 잘못된 선택을 해서 오류가 났었다. 다음부터는 조건에 대한 것을 조금 더 확실히 정의해야 할 것 같다.

 

내가 푼 방식은 다음과 같다.

 

맨 처음 탐색말고는 항상 탐색은 호수의 가장자리에 있는 빙하에서 시작한다.

이전 방문노드는 전부 visit를 해 bfs를 시작할 때 이전 탐색 경로는 되돌아보면 안된다.

백조 역시 가장자리 빙하에서 시작해서 탐색 경로를 미리 최소로 만든다.

이렇게 하다보면 큐에 자연스레 물에관한 것 2개, 백조에 관한 것 2개가 생성된다.

물에서 가장자리를 찾기위해 bfs를 하고 찾은 가장자리 빙하 위치는 다음 물이라는 큐에 저장한다.

마찬가지로 백조도 가장자리를 찾기위해 bfs를 하고 찾은 가장자리 빙하 위치는 다음 백조라는 큐에 저장한다.

가장자리에 저장한 큐에서 부터 다시 bfs를 하는 방식으로 시작하면 이전 탐색위치는 visit 되어있는 상황이고

그 다음 물의 위치로 이동할 수 있게 된다.

그리하면 두마리의 망할 백조들을 만나게 할 수 있다.

 

#include<iostream>
#include<cstring>
#include<queue>

#define MAX_ICE 1500

using namespace std;

typedef struct xy{
    int y;
    int x;
}xy;

int r, c;
char ice[MAX_ICE][MAX_ICE];
queue<xy> water;
queue<xy> nextWater;
queue<xy> cygnus;
queue<xy> nextCygnus;
int dirX[] = {1,-1,0,0};
int dirY[] = {0,0,1,-1};
bool swanVisit[MAX_ICE][MAX_ICE];
bool meet = false;      //백조 두마리가 만났는지 유무

//백조 이동
void moveMent(){
    int y, x;
    int dy, dx;
    while(!cygnus.empty()){
        y = cygnus.front().y;
        x = cygnus.front().x;
        cygnus.pop();
        for(int i = 0; i < 4; i++){
            dy = y + dirY[i];
            dx = x + dirX[i];
            if(dy < 0 || dy >= r || dx < 0 || dx >= c) continue;
            if(swanVisit[dy][dx]) continue;
            if(ice[dy][dx] == 'X'){
                 nextCygnus.push({dy, dx}); //물웅덩이 근처에있는 빙하를 백조 큐에 추가
            }
            else if(ice[dy][dx] == 'L'){ 
                meet=true;
                return;
            }
            else if(ice[dy][dx] == '.'){
                cygnus.push({dy, dx});
            }
            swanVisit[dy][dx] = true;
        }
    }
    cygnus = nextCygnus;    //bfs탐색을 할 백조 옮기기
}

//빙하 녹이기
void melt(){
    int y, x;
    int dy, dx;
    while(!water.empty()){
        y = water.front().y;
        x = water.front().x;
        water.pop();
        for(int i = 0; i < 4; i++){
            dy = y + dirY[i];
            dx = x + dirX[i];
            if(dy < 0 || dy >= r || dx < 0 || dx >= c) continue;
            if(swanVisit[dy][dx]) continue;
            if(ice[dy][dx] == 'X'){
                nextWater.push({dy, dx});   //물웅덩이 가장자리에 있는 빙하를 큐에 추가
                ice[dy][dx] = '.';
            }
        }
    }
    water = nextWater;      //bfs 탐색을 할 물 큐 추가
    
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    bool flag = false;
    int days = 0;
    cin >> r >> c;

    for(int i = 0; i < r; i++){
        for(int j = 0; j < c; j++){
            cin >> ice[i][j];

            //틀렸던 부분
            //ice[i][j] == '.'로 설정하여 백조가 있는 물웅덩이를 고려하지 않았다.
            if(ice[i][j] != 'X')
                water.push({i, j});
            //백조를 한마리만 넣기 위해 flag를 사용했다.
            if(!flag && ice[i][j] == 'L'){
                swanVisit[i][j] = true;
                cygnus.push({i, j});
                flag=true;
            }
        }
    }

    while(!meet){
        moveMent();
        if(meet){
            break;
        }
        melt();
        days += 1;
        while(!nextCygnus.empty()) nextCygnus.pop();
        while(!nextWater.empty()) nextWater.pop();
    }
    cout << days;
    return 0;
}