BOJ 3197 백조의 호수

www.acmicpc.net/problem/3197

3197번: 백조의 호수

 

처음 문제를 봤을 때 맵의 크기가 1500*1500 이길래 BFS두 개를 배열 초기화를 해가면서 사용해도

1초 안에 돌아갈까? 생각해서 구현해봤지만 TLE가 났다.

정 모르겠어서 찾아봤는데 물에 대해서 큐에 집어 넣어주고, nextQ에 넣어준 뒤에

Q = nextQ 를 통해서 복사가 가능했다..!

그리고 백조에 대해서 BFS를 해줘야 하는데 중간에 다른 백조가 있다면 BFS의 반환 값을

참으로 반환해준다.

 

 

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
 
queue<pair<int, int>> q, sq, nsq;
vector<pair<int, int>> swan;
char a[1501][1501];
bool vis[1501][1501];
int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
int n, m, ans;
 
bool bfs() {
    while (!sq.empty()) {
        auto cur = sq.front(); sq.pop();
        if (cur.first == swan[1].first && cur.second == swan[1].second) return true;
        for (int i = 0; i < 4; ++i) {
            int nx = cur.first + dx[i];
            int ny = cur.second + dy[i];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m || vis[nx][ny]) continue;
            if (a[nx][ny] == 'X') nsq.push({ nx,ny });
            else sq.push({ nx,ny });
            vis[nx][ny] = true;
        }
    }
    sq = nsq;
    return false;
}
 
void melt() {
    int sz = q.size();
    while (sz--) {
        auto cur = q.front(); q.pop();
        for (int i = 0; i < 4; ++i) {
            int nx = cur.first + dx[i];
            int ny = cur.second + dy[i];
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (a[nx][ny] == 'X') {
                a[nx][ny] = '.';
                q.push({ nx,ny });
            }
        }
    }
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
 
    cin >> n >> m;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j) {
            cin >> a[i][j];
            if (a[i][j] == 'L') swan.push_back({ i,j });
            if (a[i][j] == 'L' || a[i][j] == '.') q.push({ i,j });
        }
 
    sq.push({ swan[0].first,swan[0].second });
    vis[swan[0].first][swan[0].second] = true;
 
    while (1) {
        if (bfs()) break;    
        melt();
        ++ans;
    }
 
    cout << ans << endl;
 
    return 0;
}

 

구현할 때 조심할 점은 백조가 있는 구간도 물이라는 점이다. 따라서 55번 줄에서 백조가 있는 부분도 

물 Q에 포함시켜줘야 하고 반복문 61 ~ 64번 부분은

백조에 대해서 BFS를 해주고 만났다면 종료, 만나지 않았다면 물에 대해서 빙산을 녹이는 작업을 해주면 된다.

 

내가 작성한 코드는 950ms로 매우 간당간당한데 다른 사람의 코드와 딱히 다른 로직이 없는데도 시간 차이가

많이 나는 부분은 좀 의아하다