(C++) - 백준(BOJ) 3197번 : 백조의 호수

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

3197번: 백조의 호수

bfs로 해결한 문제였습니다.

 

 

📕 풀이방법

📔 입력 및 초기화

호수의 세로, 가로 길이를 저장할 변수 r, c, 빙하를 제거하기 위해 물의 (행, 열) 좌표들을 저장하는 waterQ, 백조가 다닐 수 있는 최전선 범위의 좌표들이 담겨있는 swanQ, 백조 두 마리의 좌표가 저장된 vector 변수 swan, 호수의 모양을 저장할 이차원 문자 배열 lake, 답을 출력할 timer 상 하 좌 우 네 방향을 확인하기 위한 일차원 배열 dx, dy를 선언합니다.

 

 1. r, c를 입력받습니다

 

 2. r x c만큼 lake에 입력합니다. 이 때 백조는 물 위에 있기 때문에 'L'인 경우에도 waterQ에 push합니다. 그 외에 'L'인 경우 swan에 각 백조의 좌표를 저장합니다.

 

 3. 마지막으로 0번째 백조부터 시작할 예정이므로 0번째 swan의 좌표를 swanQ에 push합니다.

📔 풀이과정

크기가 최대 1500 x 1500까지 가질 수 있으니 이는 대략 200만으로 매번 bfs를 수행할 시 시간초과가 나게 됩니다. 따라서 중복 탐색을 없애고 효율적으로 탐색하는 방법으로 해결할 수 있습니다.

 1. 0번째 백조부터 출발해서 1번째 백조와 만날 수 있는지 여부를 확인합니다. 만날 수 없다면 다음 날에 빙하가 녹은 구역들의 좌표는 0번째 백조가 다닐 수 있습니다. 따라서 확인하는 도중 다음에 확인하기 위해 백조의 좌표를 넣어줍니다. 이때는 임시 queue s가 사용됩니다.

 

 2. 다음 날 백조가 다닐수 있는 최전선의 좌표들이 저장되었습니다. 이제는 다음날이 되어 녹아 물이된 곳들의 좌표를 저장해야합니다. 저장된 waterQ의 size만큼 확인한다면 다음 날에 녹을 빙하들의 좌표들을 빠르게 확인할 수 있습니다. 현재 날의 시점에서 waterQ의 좌표들과 인접한 곳들 중 빙하 'X'가 있다면 그 구역을 물로 만들어주고 waterQ에 넣어줍니다.

 

 3. 0번 백조가 계속해서 녹은 빙하쪽으로 이동하며 1번 백조와 빠르게 만나게 됩니다. 만났다면 그 날을 출력해줍니다.

 

📔 정답출력

 timer를 출력합니다.

---

📕 Code

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
int r, c, ck[1501][1501], timer;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
char lake[1501][1501];

struct Swan {int r,c; };
vector <Swan> swan;
queue <pii> swanQ, waterQ;

void meltIce(){
    int wSize = waterQ.size();
    while(wSize--){
        int x = waterQ.front().first;
        int y = waterQ.front().second;
        waterQ.pop();
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(0 > nx || nx >= r || 0 > ny || ny >=c) continue;
            if(lake[nx][ny] != 'X') continue;
            waterQ.push({nx,ny});
            lake[nx][ny] = '.';
        }
    }
}

bool canMeet(){
    queue <pii> s;
    while(!swanQ.empty()){
        int x = swanQ.front().first;
        int y = swanQ.front().second;
        swanQ.pop();
        if(x == swan[1].r && y == swan[1].c) return true;
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(0 > nx || nx >= r || 0 > ny || ny >= c) continue;
            if(ck[nx][ny]) continue;
            ck[nx][ny] = 1;
            if(lake[nx][ny] == 'X') s.push({nx,ny}); //다음날에 다닐수 있다.
            else swanQ.push({nx,ny});
        }
    }
    swanQ = s;
    return false;
}

int main(){
    cin >> r >> c;
    for(int i = 0; i < r; i++){
        for(int j = 0; j < c; j++) {
            cin >> lake[i][j];
            if(lake[i][j] == 'L') waterQ.push({i,j}),swan.push_back({i,j});
            if(lake[i][j] == '.') waterQ.push({i,j});
        }
    }
    swanQ.push({swan[0].r,swan[0].c});
    while(1){
        if(canMeet()) break;
        timer++;
        meltIce();
    }
    cout << timer;
}