[백준] 3197 c++ 백조의 호수

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

3197번: 백조의 호수

[문제]

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

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

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

 

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

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

[입력]

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

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

[출력]

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

[풀이]

처음 풀 때 현재 맵을 새로운 맵에 복사해서 푸는 방식으로 풀었더니 시간 초과가 났습니다.

아래 코드는 백조의 위치를 벡터에 담고 물의 위치를 모두 water 큐에 담습니다.

여기서 큐를 하나 더 사용하는데 이 nq는 백조의 다음 시작 위치를 담는 큐입니다.

즉, 백조가 물을 떠다니다가 X라는 벽을 만나면 다음날 이 벽은 녹고 그 위치부터 백조가 BFS를 진행해서 다른 백조를 만나는 것입니다.

[코드]

#include<bits/stdc++.h>

#define Y first
#define X second
using namespace std;

int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};
int r,c;
string lake_map[1501];
bool vst[1501][1501];
vector<pair<int,int>> swan;
queue<pair<int,int>> water;

int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> r >> c;

    for(int i=0; i< r; i++){
        cin >> lake_map[i];
        for(int j=0; j<c; j++){
            if(lake_map[i][j] == 'L'){
                swan.push_back({i,j});
                lake_map[i][j] = '.';
                water.push({i,j});
            }
            else if(lake_map[i][j] == '.') water.push({i,j});
        }
    }
    queue<pair<int,int>> q;
    int day =0;
    q.push(swan[0]);
    vst[swan[0].Y][swan[0].X] = 1; 
    while(1){
        queue<pair<int,int>> nq;
        while(!q.empty()){
            auto cur = q.front();
            q.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 >= c || ny >= r || vst[ny][nx]) continue;
                else if(swan[1].X == nx && swan[1].Y == ny){
                    cout << day;
                    return 0;
                }
                else if(lake_map[ny][nx] == 'X') nq.push({ny,nx});
                else q.push({ny,nx});
                vst[ny][nx] = 1;
            }
        }
        q = nq;
        day++;
        int ws = water.size();
        while(ws--){
            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 >= c || ny >= r) continue;
                else if(lake_map[ny][nx] == 'X'){
                    water.push({ny,nx});
                    lake_map[ny][nx] = '.';
                }
            }   
        }
    }
    
    return 0;

}