[백준/C++] 3197번 백조의 호수

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

3197번: 백조의 호수

백준에서 bfs를 많이 연습했다면 크게 어렵지는 않았을 거라 생각한다.

문제를 풀이해보겠다!

우선, 백조의 위치를 vector에 저장한다. 그리고 물과 백조의 위치를 wq라는 큐에 저장해놓는다. 백조의 위치를 물의 위치와 같이 저장하는 이유는, 백조도 물에 떠있기 때문이다!!

만약 백조가 X에 둘러 쌓여져 있는 상황에 처할 경우, 다음 날이 되면 물의 영향으로 길이 생기지만, 백조의 위치를 wq에 저장해주지 않으면 백조는 탈출 불가능하다.

그리고 백조 한마리를 정해서 bfs 탐색을 한다. 이 때 만날 수 있는 모든 X를 따로 nq라는 큐에 저장해준다.

(즉, 백조를 최대한 전진시킨다는 의미)

그리고 나면 물과 인접한 얼음을 녹이면 된다. 이때는 wq의 사이즈만큼 진행하는데, 치즈와 같은 bfs 문제를 풀어보았다면 쉽게 접근 가능하다. (큐의 사이즈만큼 돌리는 이유는, 얼음을 녹여서 물로 만들었을 때 방금 막 녹아서 물이 된 부분을 탐색하는 것을 막기 위함이다.)

백조 이동 -> 만약 다른 백조만나면 탈출 -> 아니라면 얼음 녹이고 -> nq에 있는 정보 이용해서 다시 q를 탐색 (=백조 이동)

위 과정을 반복해주면 된다! 시간 초과만 조심해주면 되는 문제인 것 같다. 또한 4개의 큐를 이용하는 것이 조금 까다로웠다고 생각한다.. 아래는 정답 코드이다.

#include <bits/stdc++.h>
#define ll long long
using namespace std;

int r,c,day=0;
char board[1501][1501];
bool visited[1501][1501];
int dx[]={0,1,0,-1};
int dy[] = {1,0,-1,0};

vector<pair<int,int>> L;
queue<pair<int,int>> wq;
queue<pair<int,int>> q;


void bfs(){
    q.push(L[0]);
    visited[L[0].first][L[0].second]=true;

    while(1){

        queue<pair<int,int>> nq;
        bool flag = false;

        while(!q.empty()){
            int x = q.front().first;
            int y = q.front().second;
            q.pop();

            if(x == L[1].first && y == L[1].second){
                flag = true;
                break;
            }

            for(int i=0; i<4; i++){
                int nx = x+dx[i];
                int ny = y + dy[i];

                if(nx <0 || nx >=r || ny <0 || ny >= c || visited[nx][ny]) continue;

                visited[nx][ny]=true;

                if(board[nx][ny]=='X'){
                    nq.push({nx,ny});
                }
                else q.push({nx,ny});

            }
        }
        if(flag) break;

        int siz = wq.size();
        while (siz--){
            int x = wq.front().first;
            int y = wq.front().second;
            wq.pop();

            for(int i=0; i<4; i++){
                int nx = x + dx[i];
                int ny = y + dy[i];

                if(nx <0 || nx >=r || ny < 0 || ny >=c) continue;

                if(board[nx][ny]=='X'){
                    board[nx][ny]='.';
                    wq.push({nx,ny});
                }
            }
        }
        day++;

        while(!nq.empty()){
            q.push(nq.front());
            nq.pop();
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> r >> c;

    for(int i=0; i<r;i++){
        string s;
        cin >> s;
        for(int j=0; j<c;j++){
            board[i][j] = s[j];
            if(board[i][j]=='L'){
                L.push_back({i, j});
            }
            if(board[i][j]=='.' || board[i][j]=='L'){
                wq.push({i,j});
            }
        }
    }
    bfs();

    cout << day;
    return 0;
}