[BOJ]3197 백조의 호수

• sol1: 매번 O(RC)에 걸처 빙판을 녹임 -> 두 백조가 있는 곳이 연결되었는지 BFS 탐색

• 해당 방식 시간 초과

#include <bits/stdc++.h>
using namespace std;
int R, C, ans = 0;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
vector<vector<char>> board(1501, vector<char>(1501));
vector<pair<int, int>> Bpos;
bool dir_4_check(int x, int y){
    int cnt = 0;
    for(int i = 0; i < 4; ++i){
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(nx < 0 || ny < 0 || nx >= R || ny >= C || board[nx][ny] == 'X') ++cnt;
    }
    if(cnt == 4) return true;
    else return false;
}
bool bfs(int x, int y, vector<vector<bool>>& visited){
    queue<tuple<int, int>> que;
    visited[x][y] = true;
    que.push({x, y});
    while(!que.empty()){
        int cx, cy;
        tie(cx, cy) = que.front();
        if(cx == Bpos[1].first && cy == Bpos[1].second){
            return true;
        }
        que.pop();
        for(int i = 0; i < 4; ++i){
            int nx = cx + dx[i];
            int ny = cy + dy[i];
            if(nx < 0 || ny < 0 || nx >= R || ny >= C) continue;
            if(visited[nx][ny] || board[nx][ny] == 'X') continue;
            visited[nx][ny] = true;
            que.push({nx, ny});
        }
    }
    return false;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> R >> C;
    char tmp;
    for(int i = 0; i < R; ++i){
        for(int j = 0; j < C; ++j){
            cin >> tmp;
            if(tmp == 'L') {
                board[i][j] = '.';
                Bpos.push_back({i, j});
            }
            else{
                board[i][j] = tmp;
            }
        }
    }
    //아이디어
    vector<vector<bool>> visited(R, vector<bool>(C, false));
    //0. 두 마리의 백조가 만날 때까지 아래 과정 반복
    //1. 현재 시점에서 백조1 -> 백조2 루트 BFS 탐색
    while(!bfs(Bpos[0].first, Bpos[0].second, visited)){
        ++ans;
        //2. 빙판 감소 => 매번 녹일 빙하를 찾고, 빙하를 녹이는 방식(시간 초과)
        vector<vector<char>> newboard(1501, vector<char>(1501));
        for(int i = 0; i < R; ++i){
            for(int j = 0; j < C; ++j){
                if(board[i][j] == '.' || board[i][j] == 'L'){
                    newboard[i][j] = board[i][j];
                }
                else if(board[i][j] == 'X'){
                    if(dir_4_check(i, j)) { // 4방향 모두 X인 경우
                        newboard[i][j] = 'X';
                    }
                    else{ // 4방향 모두 X가 아닌 경우
                        newboard[i][j] = '.';
                    }
                }
            }
        }
        board = newboard;
        //방문 배열 초기화
        for(int i = 0; i < R; ++i){
            for(int j = 0; j < C; ++j){
                visited[i][j] = false;
            }
        }
    }
    cout << ans;
    return 0;
}

• sol2
  r, c: 호수 가로, 세로 길이 저장
  dx, dy: 네 방향 이동을 위한 배열
  waterQ: 빙하 제거를 위한 물의 좌표를 저장
  swanQ: 백조가 다닐 수 있는 최전선(물과 빙하의 경계)의 좌표를 저장
  swanpos: 백조 두마리의 좌표 저장
  lake: 호수 모양 저장(빙하, 물, 백조 위치정보)
  ans: 정답
• 0. 아래 과정 무한 반복
• 1. 백조 만남 체크
     백조끼리 만난 경우 반복문 탈출
• 2. 시간 증가
• 3. 빙하 녹이기

#include <bits/stdc++.h>
using namespace std;
int r, c, ans = 0;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
int visited[1501][1501];
char lake[1501][1501];
vector<pair<int, int>> swanpos;
queue<pair<int, int>> swanQ, waterQ;
//백조끼리의 만남을 체크하는 로직
bool check_meet(){
    queue<pair<int, int>> tmp;
    //백조 시작점에서 BFS 출발
    while(!swanQ.empty()){
        int x = swanQ.front().first;
        int y = swanQ.front().second;
        swanQ.pop();
        //백조 1과 백조 2가 만났다면
        if(x == swanpos[1].first && y == swanpos[1].second) return true;
        for(int i = 0; i < 4; ++i){
            int nx = x + dx[i];
            int ny = y + dy[i];
            if(nx < 0 || ny < 0 || nx >= r || ny >= c) continue;
            if(visited[nx][ny]) continue;
            visited[nx][ny] = 1;
            if(lake[nx][ny] == 'X') tmp.push({nx, ny}); // 다음날 다음 빙하에 백조가 다닐 수 있기 때문에 임시 큐에 넣는다.
            else swanQ.push({nx, ny});
        }
    }
    //제작한 임시 Queue를 백조 이동 큐로 만든다.
    swanQ = tmp;
    return false;
}
//모든 물 BFS 탐색
void melt_ice(){
    int wsize = waterQ.size();
    for(int i = 0; i < wsize; ++i){
        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(nx < 0 || ny < 0 || nx >= r || ny >= c) continue;
            //물에서 X로 이동하는 경우, 해당 위치를 물로 바꾼다(= 빙하 녹이기)
            if(lake[nx][ny] != 'X') continue;
            waterQ.push({nx, ny});
            lake[nx][ny] = '.';
        }
    }
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    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}), swanpos.push_back({i, j});
            if(lake[i][j] == '.') waterQ.push({i, j});
        }
    }
    swanQ.push({swanpos[0].first, swanpos[0].second});
    while(true){
        //백조 만남 체크 -> 만난 경우 반복문 탈출 and 정답 출력
        if(check_meet()) break;
        ++ans;
        //빙하 녹이기
        melt_ice();
    }
    cout << ans;
}