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

• 출력

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

• 예제 입력

10 2
.L
..
XX
XX
XX
XX
XX
XX
..
.L

4 11
..XXX...X..
.X.XXX...L.
....XXX..X.
X.L..XXX...

8 17
...XXXXXX..XX.XXX
....XXXXXXXXX.XXX
...XXXXXXXXXXXX..
..XXXXX.LXXXXXX..
.XXXXXX..XXXXXX..
XXXXXXX...XXXX...
..XXXXX...XXX....
....XXXXX.XXXL...

• 예제 출력

3

2

2

• 접근방식

호수가 녹는 함수와 백조가 움직이는 함수를 구현하기 > bfs로 구현

백조가 움직이는 함수나 호수가 녹는 함수 즉, bfs를 사용할 때 큐를 두개를 사용하여 막히는 부분 저장해두기

X(얼음)으로 막히면 swan_tempQ에 막힌 정점들 저장

백조가 움직이는 부분은 swan_tempQ에 저장해두면 while(swanQ.size()) 부분에서 빠져나올수 있음(더이상 큐 사이즈가 증가하지 않기때문) > 물이 녹은 다음에 다시 swan_tempQ의 정보를 가지고 탐색

• 코드

#include <iostream>
#include <queue>
#include <algorithm>
#include <tuple>

using namespace std;

const int MAX = 1500;
const int dy[4] = { -1,0,1,0 };
const int dx[4] = { 0,1,0,-1 };
char _map[MAX][MAX];
int r, c, day, y, x, swanY, swanX, visited[MAX][MAX], visited_swan[MAX][MAX];
queue<pair<int,int>> waterQ, swanQ, water_tempQ, swan_tempQ;
string s;

void Qclear(queue<pair<int,int>> &q)
{
	// 둘다 가능
    //while (q.size())
    //{
    //    q.pop();
    //}
    queue<pair<int, int>> empty;
    swap(q, empty);
}

void water_melting() {
    while (waterQ.size())
    {
        tie(y, x) = waterQ.front();
        waterQ.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;
            if (_map[ny][nx] == 'X')
            {
                visited[ny][nx] = 1;
                water_tempQ.push({ ny, nx });
                _map[ny][nx] = '.';
            }
        }
    }
}

bool move_swan()
{
    while (swanQ.size())
    {
        tie(y, x) = swanQ.front();
        swanQ.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_swan[ny][nx]) continue;
            visited_swan[ny][nx] = 1;
            if (_map[ny][nx] == '.')
            {
                swanQ.push({ ny, nx });
            }
            else if (_map[ny][nx] == 'X')
            {
                swan_tempQ.push({ ny, nx });
            }
            else if (_map[ny][nx] == 'L')
            {
                return true;
            }
        }
    }
    return false;
}

int main()
{
    cin >> r >> c;
    for (int i = 0; i < r; i++)
    {
        cin >> s;
        for (int j = 0; j < c; j++)
        {
            _map[i][j] = s[j];
            if (_map[i][j] == 'L')
            {
                swanY = i;
                swanX = j;
            }
            if (_map[i][j] == '.' || _map[i][j] == 'L')
            {
                visited[i][j] = 1;
                waterQ.push({ i,j });
            }
        }
    }

    swanQ.push({ swanY,swanX });
    visited_swan[swanY][swanX] = 1;

    while (1)
    {
        if (move_swan())   break;
        water_melting();
        waterQ = water_tempQ;
        swanQ = swan_tempQ;
        Qclear(water_tempQ);
        Qclear(swan_tempQ);
        day++;
    }

    cout << day;
    return 0;
}

 

• 문제링크 : https://www.acmicpc.net/problem/3197

3197번: 백조의 호수