3-K 시간초과 질문

작성한 질문수 2

0

안녕하세요 ㅎㅎ

swan 위치를 두 개 모두 큐에 넣어

>> 2개의 지점을 넣어서 만들 수도 있습니다만 그렇게 되면 복잡해지니 1개지점을 기반으로 탐색하는게 좋을 거 같습니다.

수강생님 코드를 살펴보면요 ㅎㅎ

            if (ny < 0 || ny >= r || nx < 0 || nx >= c || swanVisited[ny][nx]) continue;

이부분에서 먼저 백조를 방문했기 때문에 계속해서 continue가 되기 때문에

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

앞의 코드 지점까지 가지 못하는 것 같습니다.

그래서 계속해서 while루프가 돌아서 안되는 것 같습니다.

디버깅코드는 다음과 같습니다.

#include <bits/stdc++.h>

#define pii pair<int, int>

using namespace std;

const int dy[4] = {-1, 0, 1, 0};
const int dx[4] = {0, 1, 0, -1};

const double PI = 2.0 * acos(0.0);

void fastIO() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
}

int r, c;
string s;
char a[1500][1500];
int waterVisited[1500][1500];
int swanVisited[1500][1500];
queue<pii> waterQ, swanQ;
queue<pii> waterQ_temp, swanQ_temp;
int dayCount;
int y, x;

void clearQ(queue<pii>& q) {
    queue<pii> empty;
    swap(q, empty);
}

bool isSwanMet() {
    while (swanQ.size()) {
        tie(y, x) = swanQ.front();
        cout << "S : " << y << " : " << x << '\n';
        swanQ.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 || swanVisited[ny][nx]) continue;
            swanVisited[ny][nx] = 1;
            if (a[ny][nx] == '.') swanQ.push({ny, nx});
            else if (a[ny][nx] == 'X') swanQ_temp.push({ny, nx});
            else if (a[ny][nx] == 'L') return true;
        }
    }
    return false;
}

void waterMelt() {
    while (waterQ.size()) {
        tie(y, x) = waterQ.front();
        waterQ.pop();
        cout << "W : " << y << " : " << x << '\n';
        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 || waterVisited[ny][nx]) continue;
            if (a[ny][nx] == 'X') {
                waterVisited[ny][nx] = 1;
                waterQ_temp.push({ny, nx});
                a[ny][nx] = '.';
            }
        }
    }
}

int main() {
    fastIO();

    // input
    cin >> r >> c;
    for (int i = 0; i < r; i++) {
        cin >> s;
        for (int j = 0; j < c; j++) {
            a[i][j] = s[j];
            if (a[i][j] == 'L') {
                swanVisited[i][j] = 1;
                swanQ.push({i, j});
            }
            if (a[i][j] == '.' || a[i][j] == 'L') {
                waterVisited[i][j] = 1;
                waterQ.push({i, j});
            }
        }
    }

    // solve
    while (true) {
        if (isSwanMet()) break;
        waterMelt();
        swanQ = swanQ_temp;
        waterQ = waterQ_temp;
        clearQ(swanQ_temp);
        clearQ(waterQ_temp);
        dayCount++;
        cout << 1 << '\n';
    }

    // output
    cout << dayCount;

    return 0;
}

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

0

헉 질문 올리자마자 잘못된 부분이 보이네요

swan 위치를 두 개 모두 큐에 넣어

isSwanMet 함수에서 동시에 BFS를 도니

시간초과가 나는 거죠?