[백준 3197] 백조의 호수

3197번: 백조의 호수

BFS

---

1. 문제 해결 아이디어

2021.07.01 - [Algorithm/BOJ] - [백준 2636] 치즈 C++

[백준 2636] 치즈 C++

 

백조 문제에서 매일 얼음 표면을 찾고, 얼음을 녹이는 과정은 치즈 문제와 똑같다고 볼 수 있다.

 

그런데 백조 2마리가 서로 만나야 하기 때문에 서로간의 통로가 있는지 확인 작업을 하는데 시간이 많이 걸릴 것 같다..

표면을 녹이는데 O(RC) * 통로를 찾는데 O(RC) = 총 O(R^2*C^2) 이 예상되어서 접근하기가 어려웠다.

 

시간 복잡도는 표면상 O(RC)이지만 절대 모든 블럭을 탐색해서는 안될것 같다.

이미 탐색한 부분을 다시 탐색할 필요가 전혀 없다는 말이다.

 

백조는 자신이 이동할 수 있는 곳을 모두 돌아본다

(하나의 백조만 bfs를 해도 상관없다. 어차피 아직 방문하지 않은 물 공간을 모두 돌아보게 되는데 백조를 찾는경우는 변하지 않는다)

이때 빙하의 표면이 백조가 다음날에 위치할 수 있는 공간이 되고, 이를 임의의 백조queue(tmpswanQ)에 저장한다.

 

물을 돌아보는 와중에 다른 백조를 만난다면  답을 출력한다.

 

백조가 다음날에 위치할 공간이 정해졌다.
이제 빙하를 녹여보자

 

현재 물 공간을 돌아보면서 X를 발견 한다면 빙하는 녹게되고 해당 공간은 다음날의 물 공간이 될 것이다!

따라서 X를 .으로 바꿔주고, 좌표를 임의의 물queue(tmpwaterQ)에 저장한다.

 

백조가 다음번에 이동할 공간을 모두 탐색했고, 빙하가 녹았다면

tmpwaterQ를 다음날에 탐색할 waterQ에 넣어주고

tmpswanQ를 다음날에 탐색할 swanQ에 넣어준다.

그리고 tmpQ들을 비워주면 된다.

 

방문했던 공간은 다시 탐색하지않고 앞으로 갱신될 정보들만 tmpQ를 통해서 저장하기 때문에

백조dfs는 O(RC)가 될 것이고

물dfs도 O(RC)가 될 것이다.

따라서 O(RC) + O(RC) 가 되어서 시간내에 답을 구할 수 있다!

---

2. 코드

#include <iostream>
#include <vector>
#include <queue>
 
using namespace std;
 
struct P{
    int r, c;
};
 
int R, C;
vector<string> Lake;
queue<P> swanQ, waterQ, tmpswanQ, tmpwaterQ;
int dr[4] = {1, -1, 0, 0}, dc[4] = {0, 0, 1, -1};
bool visited[1501][1501], found = false;
 
void input(){
    string line;
    P swan;
    cin >> R >> C;
    for(int i = 0; i < R; i++){
        cin >> line;
        Lake.push_back(line);
        for(int j = 0; j < C; j++){
            if(line[j] != 'X'){
                waterQ.push({i, j});
            }
            if(line[j] == 'L'){
                swan.r = i;
                swan.c = j;
            }
            
        }
    }
    swanQ.push(swan);
    visited[swan.r][swan.c] = true;
}
 
void swanBFS(){
    while(!swanQ.empty()){
        P now = swanQ.front();
        swanQ.pop();
        
        for(int i = 0; i < 4; i++){
            int nr = now.r + dr[i];
            int nc = now.c + dc[i];
            if(nr < 0 || nr >= R || nc < 0 || nc >= C || visited[nr][nc]) continue;
            
            visited[nr][nc] = true;
            if(Lake[nr][nc] == 'X'){
                tmpswanQ.push({nr, nc});
            }
            else if(Lake[nr][nc] == '.'){
                swanQ.push({nr, nc});
            }
            else if(Lake[nr][nc] == 'L'){
                found = true;
                break;
            }
        }
    }
}
 
void waterBFS(){
    while(!waterQ.empty()){
        P now = waterQ.front();
        waterQ.pop();
        
        for(int i = 0; i < 4; i++){
            int nr = now.r + dr[i];
            int nc = now.c + dc[i];
            if(nr < 0 || nr >= R || nc < 0 || nc >= C) continue;
            
            if(Lake[nr][nc] == 'X'){
                Lake[nr][nc] = '.';
                tmpwaterQ.push({nr, nc});
            }
        }
    }
}
 
void solve(){
    int day = 0;
    
    while(!found){
        swanBFS();
        if(found) break;
        waterBFS();
        
        swanQ = tmpswanQ;
        waterQ = tmpwaterQ;
        
        tmpswanQ = queue<P>();
        tmpwaterQ = queue<P>();
        
        day++;
    }
    
    cout << day << "\n";
}
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    input();
    solve();
    
    return 0;
}
 

 

나한테는 어려웠던 문제! 다른사람의 코드를 많이 참고했다..

어떤 정보를 저장하고, 어떤 정보를 최적화하고, 정보를 어떤 자료구조에 넣는지에 관한 생각을 좀 더 깊어지게 해준 문제.

너무 좋은 문제같다

 

 

 

글쓰는 스타일이나 문제 풀이에 관한 피드백 감사히 받고있습니다