[백준] 3197 백조의호수 풀이 (C/C++)

문제 링크

유형

• BFS

풀이

최소이동 횟수 문제가 아닌 며칠에 만날 수 있는가에 대해 묻고 있으므로, 백조가 첫날 움직일 수 있는 모든 경로를 BFS 탐색한다. 만날 경우, 그대로 끝. 만나지 않을 경우, 백조 혹은 물 근처에 있던 얼음의 위치를 다음 날 백조가 위치할 수 있는 곳으로 판단하고 날짜를 하루 증가시킨다.
만날 때 까지 이를 반복한다.

이 문제는 백조가 만날수 있는지 확인하는 BFS, 백조가 움직일 수 있는 위치를 늘리는 BFS 두개를 이용하여 풀 수 있다. 다만 시간초과에 신경을 써야하므로 방문을 확인하는 것이 필수다.

하나만 사용한다면 그렇게 어렵지 않지만 두개의 BFS를 해야하니 난이도가 조금 있다.

코드

시간 복잡도 O(N^2)

#include <iostream>
#include<string>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;

char map[1501][1501];
int day;
int dy[] = { 1,-1,0,0 };
int dx[] = { 0,0,1,-1 };
int r, c;
bool chk[1501][1501], flag;
pair<int, int> swan;
queue < pair<int, int>> sq, wq, tmpSq, tmpWq;

void SwanBFS() {
    while (!sq.empty()) {
        int y = sq.front().first;
        int x = sq.front().second;
        sq.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 || chk[ny][nx] == 1) continue;
            chk[ny][nx] = 1;
            if (map[ny][nx] == 'X') tmpSq.push({ ny,nx });
            else if (map[ny][nx] == '.') {
                sq.push({ ny,nx });
            }
            else if (map[ny][nx] == 'L') {
                flag = 1;
                break;
            }
        }
    }
}
void WaterBFS() {
    while (!wq.empty()) {
        int y = wq.front().first;
        int x = wq.front().second;
        wq.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) continue;
        
            if (map[ny][nx] == 'X') {
                map[ny][nx] = '.';
                tmpWq.push({ ny,nx });
            }
        }
    }
}

void solve() {
    while (!flag) {
        SwanBFS();
        if (flag) break;
        WaterBFS();
        sq = tmpSq;
        wq = tmpWq;
        while (tmpSq.size()) tmpSq.pop();
        while (tmpWq.size()) tmpWq.pop();
        day++;
    }

    cout << day << '\n';
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    cin >> r >> c;
    for (int i = 0; i < r; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < c; j++) {
            map[i][j] = s[j];
            if (map[i][j] == 'L') {
                swan.first = i;
                swan.second = j;
            }
            if (map[i][j] != 'X') {
                wq.push({ i,j });
            }
        }
    }
    chk[swan.first][swan.second] = 1;
    sq.push(swan);
    solve();
}