[BOJ] #3197 백조의 호수

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

 

---

 

BFS를 응용한 조금 난이도가 있는 문제이다. 확실히 실버나 골드 문제에 비해 플래티넘 난이도로 올라가다 보니 쉽지않았던 것 같다.

필자가 해결한 방법은 이분 탐색을 이용한 풀이인데, 이 풀이의 핵심은 'N일차에 백조들이 만나지 못한다면, N일 전의 날들은 백조들이 모두 만날 수 없다는 점' 을 이용하는 것이다. 이를 이용하기 위해, 미리 얼음이 녹는 날에 대한 계산을 해야 한다. 즉, 1일차에 녹는 얼음, 2일차에 녹는 얼음 ... 이런 식으로 얼음에 번호를 부여하면 가장 마지막에 녹는 얼음을 구할 수 있고, 0일 차부터 마지막 날까지에 대해 이분 탐색을 진행할 수 있다.

 

테스트 케이스로 주어진 맵을 얼음이 녹는 날로 나타내면, 다음과 같다.

빈 공간과 백조는 0, 나머지는 순서대로 증가해 얼음이 녹는 날을 표시하도록 한다. 이 맵을 통해 마지막에 녹는 얼음의 날짜를 구할 수 있다.

이 날짜를 이용해, 다음과 같이 이분 탐색을 돌린다.

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>

#define MAX 1501

using namespace std;

int R,C;
char arr[MAX][MAX];
bool visited[MAX][MAX];
int meltingDay[MAX][MAX];
int maxDay = 0; // 얼음이 녹는 데 걸리는 최대 일

int Dx[4] = { -1, 1, 0, 0 };
int Dy[4] = { 0, 0, -1, 1 };

vector<pair<int,int>> swan; // 백조의 좌표

bool canMeetSwan(int day) {
    memset(visited, false, sizeof(visited));
    
    queue<pair<int,int>> Q;
    Q.push(make_pair(swan[0].first, swan[0].second));
    visited[swan[0].first][swan[0].second] = true;

    while (!Q.empty()) {
        int X = Q.front().first;
        int Y = Q.front().second;

        if (swan[1].first == X && swan[1].second == Y) {
            return true;
        }

        Q.pop();

        for (int i=0; i<4; i++) {
            int newX = X + Dx[i];
            int newY = Y + Dy[i];

            if (newX < 0 || newY < 0 || newX > R || newY > C) continue;
            if (visited[newX][newY] || meltingDay[newX][newY] > day) continue;

            Q.push(make_pair(newX, newY));
            visited[newX][newY] = true;
        }
    }
    return false;
}

void meltingIce() {
    memset(meltingDay, -1, sizeof(meltingDay));

    queue<pair<int,int>> Q;

    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (arr[i][j] == '.' || arr[i][j] == 'L') {
                meltingDay[i][j] = 0;
                Q.push(make_pair(i,j));
            }
        }
    }

    while (!Q.empty()) {
        int X = Q.front().first;
        int Y = Q.front().second;

        Q.pop();

        for (int i=0; i<4; i++) {
            int newX = X + Dx[i];
            int newY = Y + Dy[i];

            if (newX < 0 || newY < 0 || newX > R || newY > C) continue;
            if (meltingDay[newX][newY] >= 0) continue;

            Q.push(make_pair(newX,newY));
            meltingDay[newX][newY] = meltingDay[X][Y] + 1;

            if (maxDay < meltingDay[newX][newY]) maxDay = meltingDay[newX][newY];
        }
    }
}

int main() {
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);

    cin >> R >> C;

    for (int i=0; i<R; i++) {
        for (int j=0; j<C; j++) {
            cin >> arr[i][j];

            if (arr[i][j] == 'L') swan.push_back(make_pair(i,j));
        }
    }

    meltingIce();

    int start = 0, end = maxDay;
    while (start <= end) {
        int mid = (start + end) / 2;

        if (canMeetSwan(mid)) end = mid - 1;
        else start = mid + 1;
    }

    cout << start << '\n';

    return 0;
}

 

memset이 들어가는 헤더를 명시하지 않아 컴파일 에러가 났었다.