[BOJ] [C++] 3197 백조의 호수

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

3197번: 백조의 호수

 

 

BFS문제인데, '두 백조가 만날 때 까지 반복한다'는 조건이 달렸다. 배열의 크기가 1500*1500으로 크기 때문에, 효율적인 코드 작성이 필요하다.

 

---

 

다음과 같은 기본 구조를 가지고 문제를 해결한다.

 

기본 구조

입력을 받고, 물 공간과 백조 위치를 Queue에 넣는다

>>> BFS 1회 실행

>>> 백조가 만나는지 확인

>>> 만났다면 break, 만나지 않았다면 반복

출력한다.

 

위 방식대로 작성하면 정답은 맞지만 시간초과가 나온다. 따라서 시간을 줄일 수 있는 방법을 고려해야한다.

BFS에서 시간을 단축하긴 어렵기 때문에, 백조가 만나는지 확인하는 코드를 효율적으로 구상 해 보자.

 

IsSwanMeet

>>> 백조 위치에서 빙판과 만날 때 까지 BFS 실행

>>> 빙판과 만나면 임시Queue에 push, 물과 만나면 Queue에 push, 백조와 만나면 break

>>> 탐색이 끝나고 Queue가 비면, Queue에 임시Queue 삽입

 

위 방법으로 백조의 움직임 또한 BFS로 구현하면 시간 복잡도를 줄일 수 있다.

 

---

 

// ANSWER

#include <queue>
#include <stdio.h>
#include <algorithm>
#include <math.h>
using namespace std;
using pii = pair<int,int>;

struct Swan {int r,c; };
vector <Swan> swan;

queue <pii> swanQ;
queue <pii> waterQ;

int R, C;

char arr[1501][1501];
int check[1501][1501];
int date = 0;

int di[5]={1, 0, -1, 0};
int dj[5]={0, 1, 0, -1};


void MeltIce(){
    int WaterSize = waterQ.size();
    while(WaterSize--){
        int ii = waterQ.front().first;
        int jj = waterQ.front().second;
        waterQ.pop();
        for(int k = 0 ; k < 4 ; k ++){
            int ni = ii + di[k];
            int nj = jj + dj[k];
            if(0 > ni || ni >= R || 0 > nj || nj >= C) continue;
            if(arr[ni][nj] != 'X') continue;
            waterQ.push({ni,nj});
            arr[ni][nj] = '.';
        }
    }
}


bool IsSwanMeet(){
    
    queue <pii> swanQ_next;
    
    while(!swanQ.empty()){
        int ii = swanQ.front().first;
        int jj = swanQ.front().second;
        swanQ.pop();
        if(ii == swan[1].r && jj == swan[1].c) return true;
        for(int k = 0 ; k < 4 ; k ++){
            int ni = ii + di[k];
            int nj = jj + dj[k];
            if(0 > ni || ni >= R || 0 > nj || nj >= C) continue;
            if(check[ni][nj]) continue;
            check[ni][nj] = 1;
            if(arr[ni][nj] == 'X') swanQ_next.push({ni,nj});
            else swanQ.push({ni,nj});
        }
    }
    swanQ = swanQ_next;
    return false;
}

int main(){
    scanf("%d %d", &R, &C);
    
    for (int i = 0 ; i < R ; i ++) {
        char tmp[1501];
        scanf("%s", tmp);
        for (int j = 0 ; j < C ; j ++) {
            arr[i][j] = tmp[j];
            if (arr[i][j] != 'X') {
                waterQ.push({i, j});
            }
            if (arr[i][j] == 'L') {
                swan.push_back({i,j});
            }
        }
    }
    swanQ.push({swan[0].r,swan[0].c});
    
    while(1){
        if (IsSwanMeet()) break;
        MeltIce();
        date++;
    }
    printf("%d", date);
    return 0;
}