[백준 3197번] 백조의 호수

문제 링크: https://www.acmicpc.net/problem/3197

3197번: 백조의 호수

<문제 풀이> BFS

하루가 지날 때마다 모든 물을 확인해서 얼음을 녹이고 백조의 처음 시작 위치에서 BFS를 돌리면

얼음을 녹이는데 O(RC), 백조 BFS O(RC)

->O(R^2 * C^2)이 되기 때문에 시간 초과가 나게 됩니다.

 

그래서 시간을 단축하는 방법은

1. 하루가 지날 때 마다 빙판을 녹일 물을 탐색하는데 이미 확인했던 물은 무시

2. 물 주위에 빙판은 다음에 물이 되니깐 빙판을 물로 바꾸고 다음에 물의 탐색을 그 빙판이 있던 'X' 위치에서 시작합니다.

-> 다음 물의 시작 위치를 저장하고 있어야 되기 때문에 임시 큐가 필요합니다. (tempWater)

 

그리고 하루가 지날 때마다 백조 한 마리를 BFS로 움직여보면 되는데

1. 하루가 지날 때 마다 백조를 움직일 때 이미 방문했던 물은 무시

->이미 방문했던 물을 무시해도 되는 이유는 백조의 경로가 중요하지 않기 때문입니다.

->빙판 때문에 막혀서 못만났으니깐 백조를 처음 위치에서 다시 시작할 필요 없이 빙판을 만난 직전의 위치에서 시작하면 됩니다. 

2. 백조가 다른 백조를 만나면 종료

3. 백조의 다음 위치가 빙판 'X'이면 다음 날에 현재 위치부터 다시 백조 BFS 진행

->다음 백조의 시작 위치를 저장하고 있어야 되기 때문에 임시 큐가 필요합니다.(tempSwan)

<C++ 소스 코드>

#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <utility>
#include <climits>
using namespace std;
 
#define X first 
#define Y second 
 
char board[1500][1500];
bool visited[1500][1500];
int dx[4] = {0, -1, 0, 1};
int dy[4] = {1, 0, -1, 0};
int r, c;
int res = 0;
void bfs() {
    queue<pair<int, int> > swan;
    queue<pair<int, int>> tempSwan;
    queue<pair<int, int> > water;
    queue<pair<int, int> > tempWater;
    bool found = false;
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            if (board[i][j] == '.') {
                water.push({ i, j });
            }
            else if (!found && board[i][j] == 'L') {
                swan.push({ i, j });
                visited[i][j] = true;
                found = true;
                water.push({ i, j });
            }
            else if (found && board[i][j] == 'L') {
                water.push({ i, j });
            }
        }
    }
    while (true) {
        while (!tempSwan.empty()) { //백조의 다음 시작 위치를 백조 큐에 넣음
            swan.push(tempSwan.front());
            visited[tempSwan.front().X][tempSwan.front().Y] = true;
            tempSwan.pop();
        }
        while (!swan.empty()) { //백조 이동 BFS
            auto cur = swan.front(); swan.pop();
            for (int dir = 0; dir < 4; dir++) {
                int nx = cur.X + dx[dir];
                int ny = cur.Y + dy[dir];
                if (nx < 0 || ny < 0 || nx >= r || ny >= c) continue;
                if (visited[nx][ny]) continue;
                if (board[nx][ny] == '.') {
                    visited[nx][ny] = true;
                    swan.push({ nx, ny });
                }
                else if (board[nx][ny] == 'X') {
                    tempSwan.push({ cur.X, cur.Y });
                }
                else if (board[nx][ny] == 'L') {
                    return;
                }
            }
        }
        res++;
        while (!water.empty()) { //얼음 녹이기 BFS
            auto cur = water.front(); water.pop();
            for (int dir = 0; dir < 4; dir++) {
                int nx = cur.X + dx[dir];
                int ny = cur.Y + dy[dir];
                if (nx < 0 || ny < 0 || nx >= r || ny >= c) continue;
                if (visited[nx][ny]) continue;
                if (board[nx][ny] == 'X') {
                    board[nx][ny] = '.';
                    tempWater.push({ nx, ny });
                }
            }
        }
        while (!tempWater.empty()) { //물의 다음 시작 위치는 얼음이 녹은 위치
            water.push(tempWater.front());
            tempWater.pop();
        }
    }
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> r >> c;
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            cin >> board[i][j];
        }
    }
    bfs();
    cout << res;
    return 0;
}