[백준 3197] 백조의 호수

[백준 3197] 백조의 호수

문제 링크

#include "header.h"
using namespace std;
int R, C, day;
char pond[1501][1501];
int visit[1501][1501];
int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};
vector<pair<int, int>> swan; //백조 위치 저장
queue<pair<int, int>> q;
queue<pair<int, int>> water;
void input() {
    cin >> R >> C;
    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            cin >> pond[i][j];
            if (pond[i][j] == 'L') {
                swan.push_back({i, j});
                pond[i][j] = '.';
            }
            if (pond[i][j] == '.') {
                water.push({i, j});
            }
        }
    }
}

void melt() {
    queue <pair<int, int>> new_water;

    while (!water.empty()) {
        int x = water.front().first;
        int y = water.front().second;
        water.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(pond[nx][ny] == 'X'){
                pond[nx][ny] = '.';
                new_water.push({nx, ny}); //다음에 녹을 애들
            }
        }
    }

    water = new_water;

}
bool move_swan() {
    queue <pair<int, int>> next;
    int dest_x = swan[1].first;
    int dest_y = swan[1].second;
    
    while (!q.empty()) {
        int top_x = q.front().first;
        int top_y = q.front().second;
        q.pop();

        if (top_x == dest_x && top_y == dest_y) return true;
        for (int i = 0; i < 4; i++) {
            int nx = top_x + dx[i];
            int ny = top_y + dy[i];
            if (visit[nx][ny] || nx <= 0 || ny <= 0 || nx > R || ny > C) continue;
            if(pond[nx][ny] != 'X'){
                visit[nx][ny] = 1;
                q.push({nx, ny});
            }else {
                next.push({nx, ny});
                visit[nx][ny] = 1;
            }
        }
    }

    q = next;

    return false;
}

void solve() {

    q.push({swan[0].first, swan[0].second});
    
    while (1) {
        if (move_swan()) {
            cout << day << endl;
            return;
        }
        melt();
        day++;
    }
}
int main() {
    input();
    solve();
    return 0;
}

• bfs 응용 문제.
• 1. 백조를 bfs로 움직인다.
• 1. 만나면 return,
• 1. 아니라면 얼음을 녹인다.
• 맨 처음에는 새로 녹는 얼음들을 2중 반복문으로 pond를 전체 탐색 하여 다시 큐에 넣어주었다. -> 시간초과

• 그 다음에는 새로운 큐를 만들어서 이전 bfs를 돌 때 마다 다음 탐색 할 것을 넣어 주었다. 하지만 visit 배열을 매번 초기화 해 주었다. -> 시간초과

• 얼음을 녹일 때에는 다음에 녹을 애들만 새로운 큐에 넣어주기 때문에 방문 처리가 필요 없다.
• 따라서 visit 배열은 백조가 움직일 때만 사용 해 주었다.
• 백조가 움직일 때에도 새로운 큐를 만들어서 다음에 방문 할 것들을 저장 해 주었다.