[백준] 3197번 : 백조의 호수 (C++)

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를 진행하여 문제를 풀어준다.

이때 현재의 이동과 다음 날 시작할 위치의 큐를 따로 두고 문제를 풀어야 시간초과에 걸리지 않는다.

 

예를 들어 물을 기준으로 설명해보면

첫째 날 bfs를 진행하며, 만나는 X를 (X의 테두리) 임시 큐에 넣어준 뒤,

다음 날 임시 큐에 들어있는 값을 기준으로 다시 bfs를 실행한다면, 굳이 기존에 방문했었던 경로를 다시 돌지 않아도 된다.

 

마찬가지로 백조 역시 만나는 얼음에서 하루를 기다렸다가 다시 그곳에서부터 시작한다고 생각하면 된다.

 

좀 더 자세한 설명은 소스코드에 주석으로 달아놓았다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <algorithm>
 
using namespace std;
 
int r, c, day;
int swanX, swanY;
 
int dx[] = { -1, 0, 1, 0 };
int dy[] = { 0, -1, 0, 1 };
 
// 호수의 지도
vector<vector<char>> vec;
// 얼음을 방문처리할 배열
vector<vector<int>> ice_visited;
// 백조를 방문처리할 배열
vector<vector<int>> swan_visited;
 
// bfs를 진행할 큐들
// bfs를 진행함에 따라 다음에 진행할 곳을 temp에 넣어두어
// 처음부터 bfs를 다시 진행하지 않도록 한다.
queue<pair<int, int>> waterQ;
queue<pair<int, int>> temp_waterQ;
 
queue<pair<int, int>> swanQ;
queue<pair<int, int>> temp_swanQ;
 
// temp_queue들을 비워주기 위한 함수
void Qclear(queue<pair<int, int>>& q)
{
    queue<pair<int, int>> empty;
    swap(q, empty);
    return;
}
 
// 백조가 만날 수 있는지 확인한다.
bool move_check()
{
    // 주어진 queue를 활용하여 현재 위치 기준으로
    // 다른 백조를 만날 수 있는지 bfs를 진행한다.
    while (!swanQ.empty())
    {
        int x = swanQ.front().first;
        int y = swanQ.front().second;
        swanQ.pop();
 
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            if (0 > nx || nx >= r) continue;
            if (0 > ny || ny >= c) continue;
            if (swan_visited[nx][ny]) continue;
 
            swan_visited[nx][ny] = 1;
 
            // 물이라면 백조를 이동시킨다.
            if (vec[nx][ny] == '.')
            {
                swanQ.push(make_pair(nx, ny));
            }
            // 얼음이라면 다음날에 해당 위치로부터 bfs를 진행하면 된다.
            else if (vec[nx][ny] == 'X')
            {
                temp_swanQ.push(make_pair(nx, ny));
            }
            // 만약 다른 백조를 만났다면 true를 return하면 된다.
            else if (vec[nx][ny] == 'L')
            {
                return true;
            }
        }
    }
 
    // 이동할 수 있는 곳에서 다른 백조를 만나지 못했을 경우
    return false;
}
 
// 얼음을 녹인다.
void ice_melting()
{
    // 주어진 물의 위치로부터 bfs를 진행해 방문처리와 얼음을 녹여준다.
    while (!waterQ.empty())
    {
        int x = waterQ.front().first;
        int y = waterQ.front().second;
        waterQ.pop();
 
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
 
            // 영역 확인
            if (0 > nx || nx >= r) continue;
            if (0 > ny || ny >= c) continue;
            if (ice_visited[nx][ny]) continue;
 
            // 처음 방문하는 곳이라면 방문체크
            ice_visited[nx][ny] = 1;
 
            // 만약 얼음을 발견했다면, 
            if (vec[nx][ny] == 'X')
            {
                // 다음 bfs는 해당 얼음으로부터 시작하면 되므로
                // temp_waterQ 배열에 넣어주고.
                // 해당 얼음은 물로 바꿔준다.
                temp_waterQ.push(make_pair(nx, ny));
                vec[nx][ny] = '.';
                ice_visited[nx][ny] = 1;
 
                // bfs를 통해 진행하므로 테두리만 녹게 된다.
            }
        }
    }
}
 
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    cin >> r >> c;
 
    vec.resize(r, vector<char>(c, '0'));
    ice_visited.resize(r, vector<int>(c, 0));
    swan_visited.resize(r, vector<int>(c, 0));
 
    char temp;
    for (int i = 0; i < r; i++)
    {
        for (int j = 0; j < c; j++)
        {
            cin >> temp;
            vec[i][j] = temp;
 
            if (temp == 'L')
            {
                swanX = i;
                swanY = j;
            }
 
            if (temp == '.' || temp == 'L')
            {
                ice_visited[i][j] = 1;
                waterQ.push(make_pair(i, j));
            }
        }
    }
 
    swanQ.push(make_pair(swanX, swanY));
    swan_visited[swanX][swanY] = 1;
 
    while (1)
    {
        // 백조들이 만나는지 확인
        if (move_check()) break;
        // 얼음을 녹이고
        ice_melting();
 
        // 다음 bfs를 위해 temp를 교체해준다.
        waterQ = temp_waterQ;
        swanQ = temp_swanQ;
 
        // 다음 bfs를 통해 temp를 비워준다.
        Qclear(temp_waterQ);
        Qclear(temp_swanQ);
 
        // 다음 날
        day++;
    }
 
    cout << day;
 
    return 0;
}

---

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

3197번: 백조의 호수