글 읽기 - 시간초과입니다 어느부분을 줄여야할까요?

alsgud3229 5년 전 0

우선 인접행렬의 BFS 시간복잡도가 O(|V|^2) 라고 하는데 그럼 이 문제의 경우 (1500*1500)^2의 시간복잡도를 갖는건가요?
저의 로직에서 시간을 어떻게 줄여야할까요?

로직: BFS를 통해 백조가 만날 수 있는지를 판단하여 bool로 반환한다 -> 반환이 false라면 얼음을 녹인다

위 과정을 반복하여 백조가 만나게 되는 최소 날짜를 출력했습니다.

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

using namespace std;

int n,m;
char map[1503][1503];
bool visited[1503][1503];
struct Pair{
    int x,y;
};
Pair swan[2];
int day = 0;
queue<Pair> Q;
int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};
bool melt_candi[1503][1503];


void printAll(){
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cout<<visited[i][j]<<" ";
        }
        cout<<"\n";
    }
    cout<<"\n";
}

bool BFS(){
    while(!Q.empty()){
        int x = Q.front().x;
        int y = Q.front().y;
        Q.pop();
        if(x==swan[1].x && y==swan[1].y){
            return true;
        }
        for(int i=0; i<4; i++){
            int nx = x+dx[i];
            int ny = y+dy[i];
            if(0<=nx && nx<n && 0<=ny && ny<m){
                if(visited[nx][ny]==false && (map[nx][ny]=='.' || map[nx][ny]=='L')){
                    visited[nx][ny]=true;
                    Pair p = {nx,ny};
                    Q.push(p);
                }
            }
        }
    }

    return false;
}


void melt(){
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            if(map[i][j]=='X') {
                for (int k = 0; k < 4; k++) {
                    int nx = dx[k] + i;
                    int ny = dy[k] + j;
                    if (0 <= nx && nx < n && 0 <= ny && ny < m) {
                        if (map[nx][ny]=='.' || map[nx][ny]=='L'){
                            melt_candi[i][j] = true;
                            break;
                        }
                    }
                }
            }
        }
    }

    for(int i=0; i<n ;i++){
        for(int j=0; j<m; j++){
            if(melt_candi[i][j]){
                map[i][j]='.';
            }
        }
    }
}

void init(){
    memset(visited, false, sizeof(visited));
    visited[swan[0].x][swan[0].y] = true;
    while(!Q.empty()){
        Q.pop();
    }
    Q.push(swan[0]);
    memset(melt_candi, false, sizeof(melt_candi));
}

int main(){
    cin>>n>>m;
    int swan_walker = 0;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin>>map[i][j];
            if(map[i][j]=='L'){
                swan[swan_walker++] = {i,j};
            }
        }
    }
    Q.push(swan[0]);
    visited[swan[0].x][swan[0].y] = true;

    while(1){
        if(BFS()){
            break;
        }
        melt();
        day++;
        init(); // Q비우고 첫큐 넣어주고, visited 첫백조만 true, melt candi초기화
    }

    cout<<day;



    return 0;
}

djm03178 5년 전 1

O(|V|^2)이라는 것은 모든 정점에서 모든 정점으로 가는 간선이 있을 수 있을 때 쓰는 말이고, 이 문제에서는 인접 행렬을 만드신 적이 없을 뿐더러 dx와 dy를 통해 각 칸마다 최대 4개의 간선만을 사용하기 때문에 O(4|V|) 정도만을 탐색하면 됩니다.
하지만 이 코드에서는 BFS를 한 번만 돌리는 것이 아니라 얼음이 다 녹을 때까지 돌리고, 이 시간은 최대 O(|V|) 회 반복될 수 있습니다. 그래서 약 세제곱이 도는 것이고, 이 방법으로는 시간 초과를 피할 수 없습니다.

매번 얼음을 녹이고 다시 BFS를 하지 않고, 과정을 진행하면서 얼음을 녹이는 방법을 생각해 보세요. 즉, 전체에서 BFS가 딱 한 번만 돌아야 합니다. 또는 union find 등을 사용할 수도 있습니다.

alsgud3229 5년 전 0

과정을 진행하면서 얼음을 녹이는 방법.

에서 깨달음을 얻었습니다 감사합니다 한번 해볼게요!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

시간초과입니다 어느부분을 줄여야할까요?

alsgud3229 5년 전 0

djm03178 5년 전 1

alsgud3229 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말