백준[3197번] 백조와 호수

참고: https://codecollector.tistory.com/1184

(C++) - 백준(BOJ) 3197번 : 백조의 호수

생각 못한 부분:

1. 백조의 현재위치도 어쨋든 물일 것이다.

2. 기존에 생각했던 것은 방문위치를 매 번 BFS를 돌릴 때마다 초기화했는데, 그렇게 되면 1500*1500 ~= 대략 200만 이걸 최악의 경우로 가정했을때 1500*1500*1500 => 시간제한에 걸릴 것이다.

아이디어는 참고자료와 비슷하였으나, 백조가 움직일 때 다음 이동이 'X'라면 다음날 이동할 수 있는 것이므로(백조의 현재 위치는 물('.')이기 때문에) 해당 위치들을 저장해두고 다시 BFS를 돌렸으며, 방문위치는 백조가 멈춘위치에서 계속 진행하므로 시간초과도 나지 않을 것이다.

 

해당 코드는 참고 코드를 클론 코딩해보았다. 몇 일 뒤에 다시 스스로 코드를 짜 볼 예정.

#include <iostream>
#include <vector>
#include <queue>
#define pii pair<int, int>
using namespace std;

int r, c, ck[1501][1501], timer;
int dx[] = {0, 0, -1, 1};
int dy[] = {-1, 1, 0, 0};
char lake[1501][1501];

struct Swan
{
    int r, c;
};
vector<Swan> swan;
queue<pii> swanQ, waterQ;

void meltIce()
{
    int wSize = waterQ.size();
    while (wSize--)
    {
        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 (nx < 0 || ny < 0 || nx >= r || ny >= c)
            {
                continue;
            }
            if (lake[nx][ny] != 'X')
            {
                continue;
            }
            waterQ.push({nx, ny});
            lake[nx][ny] = '.';
        }
    }
}

bool canMeet()
{
    queue<pii> s;
    while (!swanQ.empty())
    {
        int x = swanQ.front().first;
        int y = swanQ.front().second;
        swanQ.pop();
        if (x == swan[1].r && y == swan[1].c)
        {
            return true;
        }
        for (int i = 0; i < 4; i++)
        {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx < 0 || ny < 0 || nx >= r || ny >= c)
            {
                continue;
            }
            if (ck[nx][ny])
            {
                continue;
            }
            ck[nx][ny] = true;
            if (lake[nx][ny] == 'X')
            {
                s.push({nx, ny}); // 다음날에 날 수 있다.
            }
            else
            {
                swanQ.push({nx, ny});
            }
        }
    }
    swanQ = s;
    return false;
}
int main(int argc, char const *argv[])
{
    cin >> r >> c;
    for (int i = 0; i < r; i++)
    {
        for (int j = 0; j < c; j++)
        {
            cin >> lake[i][j];
            if (lake[i][j] == 'L')
            {
                waterQ.push({i, j});
                swan.push_back({i, j});
            }
            if (lake[i][j] == '.')
            {
                waterQ.push({i, j});
            }
        }
    }
    swanQ.push({swan[0].r, swan[0].c});
    while (1)
    {
        if (canMeet())
        {
            break;
        }
        timer++;
        meltIce();
    }
    cout << timer;

    return 0;
}