백조의 호수

내풀이 ❌

거의 다풀었는데 잘못 생각했던 부분이 따로 DFS를 만들어서 Connect되었는지 확인 했던 부분이다.

그냥 백조의 첫번째 위치부터 내가 while 문 두개를 사용해서 구현했던 부분처럼 쭉 진행하면 되었던 문제이다.

문제를 조금더 단순화 해서 생각하도록 하자.

백조라는 어느 출발지점부터 BFS를 돌린다.

백조하나를 기반으로 쭉쭉 나간다.

또한 queue를 두개를 사용해준다.

cpp 코드

#include <iostream>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
using namespace std;
#define endl "\n"
#define MAX 1501
const int dy[4] = {0, 1, 0, -1}, dx[4] = {-1, 0, 1, 0};
int visited_swan[MAX][MAX], visited[MAX][MAX], R, C, day, swanY, swanX, y, x;
char arr[MAX][MAX];
queue<pair<int, int>> waterQ, water_tempQ, swanQ, swan_tempQ;
string s;
void QClear(queue<pair<int, int>>& q)
{
    queue<pair<int, int>> E;
    swap(q, E);
}

void WaterMelting()
{
    while (!waterQ.empty())
    {
        int y = waterQ.front().first;
        int x = waterQ.front().second;
        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 (arr[ny][nx] == 'X')
            {
                visited[ny][nx] = 1;
                water_tempQ.push({ny ,nx});
                arr[ny][nx] = '.';
            }
        }
    }
}

bool MoveSwan()
{
    while (!swanQ.empty())
    {
        int y = swanQ.front().first;
        int x = swanQ.front().second;
        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 (arr[ny][nx] == '.') swanQ.push({ny, nx});
            else if (arr[ny][nx] == 'X')
            {
                swan_tempQ.push({ny, nx});
            }
            else if (arr[ny][nx] == 'L')
            {
                return true;
            }
        }
    }
    return false;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> R >> C;
    for (int i = 0; i < R; ++i)
    {
        cin >> s;
        for (int j = 0; j < C; ++j)
        {
            arr[i][j] = s[j];
            if (arr[i][j] == 'L')
            {
                swanY = i; swanX = j;
            }
            if (arr[i][j] == '.' || arr[i][j] == 'L')
            {
                visited[i][j] = 1;
                waterQ.push({i, j});
            }
        }
    }
    swanQ.push({swanY, swanX});
    visited_swan[swanY][swanX] = 1;
    while (true)
    {
        if (MoveSwan()) break;
        WaterMelting();
        waterQ = water_tempQ;
        swanQ = swan_tempQ;
        QClear(water_tempQ);
        QClear(swan_tempQ);
        ++day;
    }

    cout << day << endl;

    return 0;
}