[BOJ] 3917번 백조의 호수 (C++)

 

3197번: 백조의 호수 (acmicpc.net)

3197번: 백조의 호수

 

- 1차 접근

자료구조랑 그래프 탐색만 잘하면 풀릴 것 같다는 생각으로 접근해 아래의 로직을 구현했다.

 

1. 백조가 만날 때까지 아래 과정을 반복한다.

  1-1. 백조가 만나는지 확인하고 만난다면 반복문을 종료한다. (bfs 활용)

  1-2. 물에 닿아 있는 얼음을 물로 바꾼다. (set 활용)

  1-3. day를 1만큼 증가시킨다.

 

이 때, 다음 얼음을 녹일 가능성이 존재하는 물의 좌표를 Set 자료구조로 관리했다.

하지만, 결과는 시간 초과.. 예상하긴 했다. 

 

- 2차 접근

백조의 마지막 탐색 위치도 메모이제이션 할 수 있다고 생각했었기 때문에 바로 시도했다.

먼저 백조의 마지막 위치를 다시 Set으로 관리했다.

백조가 만나는지 확인하는 탐색 중에 마지막 탐색 위치 중 벽이면 해당 위치를 Set에 추가했다.

그리고 다음 확인에는 해당 Set에 있는 좌표들을 Queue에 넣고 탐색했다.

해당 방식으로 통과했다.

 

- 특이 사항

처음 백조의 위치도 '물'인 것을 간과했다.

 

- 코드

#include <iostream>
#include <string>
#include <set>
#include <queue>
#define P pair<int,int>
#define MAX 1500
using namespace std;

int R, C;
vector<string> lake;
set<P> lasts;
set<P> waters;
int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
bool visits[MAX][MAX];

bool checkReachable() {
    queue<P> q;
    set<P> newLasts;
    set<P>::iterator iter;

    for(iter = lasts.begin(); iter != lasts.end(); iter++) {
        q.push(*iter);
        visits[iter->second][iter->first] = true;
    }

    while(!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        for(int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if(nx < 0 || ny < 0 || C <= nx || R <= ny || visits[ny][nx]) 
                continue;
            
            if(lake[ny][nx] == 'X') {
                newLasts.insert({nx, ny});
                continue;
            }

            if(lake[ny][nx] == 'L') 
                return true;

            visits[ny][nx] = true;
            q.push({nx, ny});
        }
    }

    lasts = newLasts;

    return false;
}

void updateLake() {
    set<P>::iterator iter;
    set<P> newWaters;

    for(iter = waters.begin(); iter != waters.end(); iter++) {
        for(int i = 0; i < 4; i++) {
            int nx = iter->first + dx[i];
            int ny = iter->second + dy[i];

            if(nx < 0 || ny < 0 || C <= nx || R <= ny) continue;

            if(lake[ny][nx] == 'X') {
                lake[ny][nx] = '.';
                newWaters.insert({nx, ny});
            }
        }
    }

    waters = newWaters;
}

int main() {
    string str;
    P swan;
    int curDay = 0;

    cin >> R >> C;

    for(int i = 0; i < R; i++) {
        cin >> str;
        lake.push_back(str);

        for(int j = 0; j < C; j++) {
            if(str[j] == '.') 
                waters.insert({j, i});
            else if(str[j] == 'L') {
                swan = make_pair(j, i);
                waters.insert({j, i});
            }
        }
    }

    lasts.insert(swan);

    while(1) {
        if(checkReachable())
            break;

        updateLake();
        curDay++;
    }

    cout << curDay << '\n';

    return 0;
}

 

굳굳