[BOJ] 3197 백조의 호수

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

3197번: 백조의 호수

---

문제

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

호수는 행이 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'은 백조가 있는 공간으로 나타낸다.

---

출력

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

---

풀이

빙판이 녹을 때 마다 백조의 위치에서 bfs를 돌린다면 R과 C가 최대 1500까지 가능하므로 무조건 시간초과가 날 것이다.

따라서 매번 새롭게 bfs를 돌기보다는 한 번 방문한 칸은 다시 방문하지 않게 구현하는 것이 핵심이었다.

 

예제 3번

위는 예제 3번이다. 우선 호수 전체를 방문하면서 해당 칸이 빙판일 경우 bfs를 이용하여 호수와 인접한 칸을 모두 구하고 칸의 좌표를 큐에 넣어준다.

호수와 인접한 빙판을 큐에 넣어준다.

빨간 X는 호수와 인접한 빙판이다. 이렇게 처리를 하고 백조 한마리를 골라 bfs를 돌려서 백조가 갈 수 있는 호수를 모두 체크해준다.

백조가 갈 수 있는 호수 영역 표시

그 다음이 중요한데 큐에 넣었던 호수와 인접한 빙판들을 pop해주면서 호수로 바꿔주고 상,하,좌,우를 확인해준다. 상,하,좌,우에 빙판이 있다면 다음날 녹을 빙판이므로 큐에 넣어주고 만약 백조가 갈 수 있는 호수가 있다면 해당 칸에서 bfs를 돌려 백조가 갈 수 있는 칸을 늘려준다.(기존에 백조가 갈 수 있는 영역은 방문할 필요가 없다.) 이 과정을 백조들이 만날 때 까지 반복해주면 된다.

1일차(파란 칸 옆에도 빨간색 처리 해줘야 한다....ㅠ)

2일차 백조끼리 만날 수 있다

1. 호수에 인접한 빙판의 위치를 큐에 넣는다.
2. 백조 한 마리가 갈 수 있는 위치를 방문 처리한다.
3. 큐를 pop하면서 빙판을 호수로 만들고 상,하,좌,우를 확인하면서 빙판이라면 큐에 넣어주고 백조가 방문한 호수라면 bfs를 돌려 추가로 갈 수 있는 칸을 구해 방문 처리 한다.
4. 3을 두 백조가 만날 때 까지 반복한다.

---

코드

#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <climits>

#define INF 1000000000
#define endl '\n'
#define ll long long

using namespace std;

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

char map_[1500][1500];

bool check[1500][1500]; // 녹는 빙하에 포함되었는지 안되었는지 체크
bool visit[1500][1550]; // 백조가 방문 했는지 안했는지 체크

int R,C;

vector<pair<int,int> > swan_pos; // 백조의 위치
queue<pair<int,int> > melt; // 다음날 녹을 빙판의 위치 저장


void bfs(int i,int j){ // 호수에 인접한 빙판을 큐에 넣어주는 bfs 함수
    queue<pair<int,int> > q;
    q.push(make_pair(i,j));
    visit[i][j]=true;
    while(!q.empty()){
        int y=q.front().first,x=q.front().second; q.pop();
        for(int k=0;k<4;k++){
            int ny=y+dy[k],nx=x+dx[k];
            if(0<=ny&&ny<R&&0<=nx&&nx<C){
                if(map_[ny][nx]=='.'&&!check[y][x]){ // 인접한 칸에 호수가 있다면 melt에 push
                    melt.push(make_pair(y,x));
                    check[y][x]=true;
                }
                if(map_[ny][nx]=='X'&&!visit[ny][nx]){
                    q.push(make_pair(ny,nx));
                    visit[ny][nx]=true;
                }
            }
        }
    }
}

void bfs2(int i,int j){ // 백조가 방문하지 않은 호수가 있다면 방문처리 해주는 bfs
    queue<pair<int,int> > q;
    q.push(make_pair(i,j));
    
    visit[i][j]=true;
    
    while(!q.empty()){
        int y=q.front().first,x=q.front().second; q.pop();
        for(int k=0;k<4;k++){
            int ny=y+dy[k],nx=x+dx[k];
            if(0<=ny&&ny<R&&0<=nx&&nx<C){
                if(map_[ny][nx]=='.'&&!visit[ny][nx]){
                    visit[ny][nx]=true;
                    q.push(make_pair(ny,nx));
                }
            }
        }
    }
}

void input() {
    cin>>R>>C;
    for(int i=0;i<R;i++){
        for(int j=0;j<C;j++){
            cin>>map_[i][j];
            if(map_[i][j]=='L'){ // 편의상 백조는 위치만 저장하고 호수 처리해주는 것이 좋다
                swan_pos.push_back(make_pair(i,j));
                map_[i][j]='.';
            }
        }
    }
}

void init() {}

void solution() {
    int ans=0;
    int y1=swan_pos[0].first,x1=swan_pos[0].second;
    int y2=swan_pos[1].first,x2=swan_pos[1].second;
    
    //bfs로 가장자리 얼음들 구하기
    for(int i=0;i<R;i++){
        for(int j=0;j<C;j++){
            if(map_[i][j]=='X'&&!visit[i][j]) bfs(i,j);
        }
    }
    
    // 이제 visit을 한 백조가 방문했는지를 알려주는 배열로 바꾼다.
    fill(&visit[0][0],&visit[1499][1500],false);
    
    bfs2(y1,x1); // 백조 한마리가 갈 수 있는 호수를 방문처리 해준다.
    
    while(1){
        if(visit[y2][x2]) break; // 만약 백조끼리 만날 수 있다면 break
        
        int size=melt.size();
        while(size--){ // 오늘 녹는 얼음의 개수만큼 돌아야 한다.
            int y3=melt.front().first , x3=melt.front().second; melt.pop();
            map_[y3][x3]='.';
            
            for(int k=0;k<4;k++){
                int ny=y3+dy[k],nx=x3+dx[k];
                if(0<=ny&&ny<R&&0<=nx&&nx<C){
                    if(map_[ny][nx]=='.'&&visit[ny][nx]){ // 인접한 칸이 백조가 방문한 호수라면 bfs를 돈다.
                        bfs2(y3,x3);
                    }
                    else if(map_[ny][nx]=='X'&&!check[ny][nx]){ // 인접한 칸이 빙판이라면 큐에 넣어준다.
                        check[ny][nx]=true;
                        melt.push(make_pair(ny,nx));
                    }
                }
            }
        }
        ans++;
    }
    
    
    cout<<ans;
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    input();
    solution();
    return 0;
}