[백준] 3197번 백조의 호수

3197 백조의 호수

문제

---

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

호수는 가로로 R, 세로로 C만큼의 직사각형 모양이다. 어떤 칸은 얼음으로 덮여있다.

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

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

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

입력

---

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

각 R줄 동안 C만큼의 문자열이 주어진다.

'.'은 물 공간, 'X'는 빙판 공간, 'L'은 백조가 있는 공간으로 나타낸다.

출력

---

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

---

풀이)

BFS를 이용한 문제이다.

매일 매일 (백조1의 위치에서 bfs를 통해 백조끼리 만나는 지 확인 -> 녹일 수 있는 빙판 녹임)했더니 시간초과가 난 문제이다.

map size가 1500*1500이므로

bfs마다 매번 새롭게 방문표시(visited[][])를 초기화해서 탐색하고, 물과 인접한 빙판을 녹여주면 오래 걸려서이다.

bfs 횟수를 줄이기 위해, 백조가 이미 방문했던 위치는 다음 bfs에 방문하지 않도록 하는 방법을 사용했다.

이 방법을 위해 총 3개의 queue를 만들었다.

① 현재 백조가 이동할 위치를 저장한 queue => queue<pair<int, int>> qu;

② 다음날에 백조가 이동할 위치를 저장한 queue => queue<pair<int, int>> next_qu;

③ 물의 위치를 저장한 queue => queue <pair<int, int>> water;

3개의 queue를 이용한 과정은 이러하다.

1. 백조가 움직일 수 있는 위치를 저장한 qu를 이용해 탐색한다.

   (탐색 중에 빙판을 만나 못 갈 경우, 그 빙판의 위치를 다음날에 백조가 탐색할 위치를 저장하는 next_qu에 저장해 놓는다.)

   (탐색 중에 다른 백조를 만날 경우 걸린 날짜 출력)

2. 백조가 다음에 탐색할 next_qu를 현재 탐색할 qu에 저장한다. (qu <= next_qu)

3. 물의 위치를 저장한 water를 이용해 물과 인접한 빙판들을 물로 바꾼다.

   (빙판을 물로 바꾸면서, 그 위치를 다시 water에 저장해 놓는다.)

다시 1번으로 돌아간다.

이런식으로 풀면, 백조가 이미 갔던 위치를 다시 방문안해도 되므로 시간이 절약된다.

참고사항

백조는 물을 통해서만 이동할 수 있으므로, 백조가 있는 곳이 곧 물이다.

초기 백조의 위치도 물의 위치를 저장하는 water queue에 저장한다.

코드)

#include <stdio.h>
#include <vector>
#include <queue>
using namespace std;
 
int R, C;
char map[1500][1500];
vector<pair<int, int>> bird;//백조 위치
queue <pair<int, int>> water;//물 위치
queue<pair<int, int>> qu;//백조1이 탐색할 위치
queue<pair<int, int>> next_qu;//백조1이 다음날에 탐색할 위치
bool visited[1500][1500];//방문표시
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
 
bool move() {    
    while (!qu.empty())
    {
        int y = qu.front().first;
        int x = qu.front().second;
        qu.pop();
        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (ny < 0 || ny >= R || nx < 0 || nx >= C || visited[ny][nx]) continue;
            
            visited[ny][nx] = true;
            if (ny == bird[1].first && nx == bird[1].second) {//백조끼리 만났으면
                return true;
            }
            if (map[ny][nx] == 'X') { //백조가 다음에 탐색할 위치
                next_qu.push({ ny,nx });
            }
            else qu.push({ ny,nx });
        }
    }
    return false;
}
 
void melt() {
    int size = water.size();
    while (size--)
    {
        int y = water.front().first;
        int x = water.front().second;
        water.pop();
        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (ny < 0 || ny >= R || nx < 0 || nx >= C ) continue;
 
            if (map[ny][nx] == 'X') { //물 주위의 빙판 = 녹일 빙판
                map[ny][nx] = '.';
                water.push({ ny,nx });//다음에 주위를 확인할 물 위치로 저장
            }
        }
    }
}
 
int main() {
    scanf("%d %d", &R, &C);
    getchar();
    
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            map[i][j] = getchar();
            if (map[i][j] == 'L') {
                bird.push_back({ i,j });
                map[i][j] = '.';
                water.push({ i,j });
            }
            else if (map[i][j] == '.') {
                water.push({ i,j });
            }
        }
        getchar();
    }
 
    int day = 0;
    bool suc = false;
    qu.push({ bird[0].first,bird[0].second });
    visited[bird[0].first][bird[0].second] = true;
    
    while (true)
    {
        suc = move();//백조 탐색
        if (suc) break;
 
        qu = next_qu;//백조가 탐색할 다음 위치를 저장
        
        melt();//빙판 녹임
        day++;
    }
    printf("%d", day);
 
 
 
    return 0;
}