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

 

 

문제

두 마리의 백조가 호수에서 살고 있었다. 그렇지만 두 마리는 호수를 덮고 있는 빙판으로 만나지 못한다.

호수는 행이 R개, 열이 C개인 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있다.

호수는 차례로 녹는데, 매일 물 공간과 접촉한 모든 빙판 공간은 녹는다. 두 개의 공간이 접촉하려면 가로나 세로로 닿아 있는 것만 (대각선은 고려하지 않는다) 생각한다.

아래에는 세 가지 예가 있다.

...XXXXXX..XX.XXX ....XXXX.......XX .....XX.......... 
....XXXXXXXXX.XXX .....XXXX..X..... ......X.......... 
...XXXXXXXXXXXX.. ....XXX..XXXX.... .....X.....X..... 
..XXXXX..XXXXXX.. ...XXX....XXXX... ....X......XX.... 
.XXXXXX..XXXXXX.. ..XXXX....XXXX... ...XX......XX.... 
XXXXXXX...XXXX... ..XXXX.....XX.... ....X............ 
..XXXXX...XXX.... ....XX.....X..... ................. 
....XXXXX.XXX.... .....XX....X..... ................. 
      처음               첫째 날             둘째 날

백조는 오직 물 공간에서 세로나 가로로만(대각선은 제외한다) 움직일 수 있다.

며칠이 지나야 백조들이 만날 수 있는 지 계산하는 프로그램을 작성하시오.

입력

입력의 첫째 줄에는 R과 C가 주어진다. 단, 1 ≤ R, C ≤ 1500.

다음 R개의 줄에는 각각 길이 C의 문자열이 하나씩 주어진다. '.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다.

출력

 

첫째 줄에 문제에서 주어진 걸리는 날을 출력한다.

 

접근 방식

 

플래티넘 문제라서 겁을 먹었는데

문제 자체는 간단한 문제였다 약간 빙산 녹는 문제랑 비슷해서

그렇게 풀면 되겠다 싶었는데 시간초과가 뜬다!

visited 배열을 계속 초기화하면서 반복해서 시간 초과가 뜨는 것 같았다

다른 분들 코드를 참고하니 큐를 사용하면 시간 초과 문제를 해결할 수 있는 것 같았다 (이미 지나간 곳들은 다시 보지 않아도 되기 때문에..)

 

얼음이 녹고 백조가 움직여야 하는데

이를 큐로 관리하려면

 

1. 물인 좌표를 모두 큐로 저장

2. 다음에 물일 좌표들을 큐로 저장

3. 백조의 좌표들을 큐로 저장

4. 다음에 백조가 갈 수 있는 좌표들을 큐로 저장

이렇게 네가지 큐를 사용하면 간단하게 문제를 해결할 수 있다!

 

왜 빙하의 좌표가 아니고 물의 좌표를 저장하냐면

물인데 만약 빙하를 만나면 그 빙하는 무조건 녹기 때문이다

따라서 빙하의 좌표를 저장해두는 것 보다 물의 좌표를 저장하는게 훨씬 효율적이다

 

 

코드

 

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

int R,C;
char mat[1502][1502];
bool visited[1502][1502];

int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};

queue<pair<int,int>> swanQ, swanNQ, q, nq;
pair<int,int> swanP;

int ans = 0;

bool swanMove() {

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

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

            if(nx <= 0 || ny <= 0 || nx > R || ny > C || visited[nx][ny]) continue;
            visited[nx][ny] = true;
            if(mat[nx][ny] == '.') swanQ.push({nx,ny});
            else if(mat[nx][ny] == 'L') return true;
            else if(mat[nx][ny] == 'X') swanNQ.push({nx,ny});
        }

    }
    return false;
}

void melt() {

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

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

            if(nx <= 0 || ny <= 0 || nx > R || ny > C ) continue;
            if(mat[nx][ny] == 'X') {
                mat[nx][ny] = '.';
                nq.push({nx,ny});
            }     
        }
    }
}


int main() {
    cin>>R>>C;
    for(int i=1; i<=R; i++) {
        for(int j=1; j<=C; j++) {
            cin>>mat[i][j];
            if(mat[i][j] == 'L') {
                swanP.first = i;
                swanP.second = j;
            }
            if(mat[i][j] != 'X') q.push({i,j});
        }
    }

    swanQ.push({swanP.first,swanP.second});
    visited[swanP.first][swanP.second] = true;

    while(true) {

        if(!swanMove()) {
            melt();
            q = nq;
            swanQ = swanNQ;

            while(!nq.empty()) nq.pop();
            while(!swanNQ.empty()) swanNQ.pop();
            ans++;
            
            
        }
        else break;
        
    }
    cout<<ans;
}

 

풀고나니 역시 플래티넘이다 싶었던..