글 읽기 - 어떻게 시간을 줄일 수 있을까요?

cokcjswo 7년 전 0

제가한 방식은

얼음이 아무리 많아도 시간이 3000초 이내에 모든 얼음이 다 녹으니까 (1500*1.414...)

시간 0부터 3000까지 loop 돌렸습니다...

매 loop 마다 BFS 돌렸구요...

이게 아무생각없이 짜면 시간복잡도가 3000 * 1500*1500이니까 (1500*1500은 개별 BFS 시간복잡도)

70억 정도 되길래

시작점과 목적점이 있는 것을 이용해서 양방향 탐색까지 이용해줬는데... 어떻게 시간을 더 줄일 수 있을까요?

매 시간마다 melt 함수에서 물과 이웃한 얼음들은 다 녹여줬구요...

ㅠㅠㅠㅠㅠㅠㅠㅠ

BOJ 3055 탈출 문제 처럼 풀려고 그랬는데...

정답률은 더 높아도 이게 훨씬 어려운 문제같네요....

코드는 보기 편하시라고 solve 부분만 올립니다...

void solve() {
    int t=0;
    bool Fflag = false;
    for(;t<5000;t++) {
        memset(discovered,0,sizeof(discovered));
        queue<points> q;
        q.push(init[0]);
        q.push(init[1]);
        discovered[init[0].y][init[0].x] = 1;
        discovered[init[1].y][init[1].x] = -1;

        while(!q.empty()) {
            points here = q.front();
            q.pop();

            for(int i=0;i<4;i++) {
                int nexty = here.y+dy[i], nextx = here.x+dx[i];
                if(ok(nexty,nextx) && discovered[nexty][nextx] != discovered[here.y][here.x] && m[nexty][nextx] != 'X') {
                    if(discovered[nexty][nextx] == -discovered[here.y][here.x]) {
                        Fflag = true;
                        break;
                    }
                    discovered[nexty][nextx] = discovered[here.y][here.x];
                    q.push(points(nexty,nextx));
                }
            }
            if(Fflag)
                break;
        }
        if(Fflag)
            break;
        melt();
    }
    printf("%d\n",t);
}

zlzmsrhak 7년 전 0

0. 코드는 전체를 올려주세요. 코드가 부분만 있으면 실행을 시켜볼 수가 없어서 더 불편합니다.

1. 저기서 시간을 더 줄이기 위해서는 단순히 BFS를 구현하는 것 이상의 생각을 해야 합니다.

모든 칸의 빙하가 없어지는 시간을 1500*1500에 계산할 수 있고, 이 정보를 이용하여 두 백조가 물로 연결되는 최소 시간을 구할 수 있습니다.

cokcjswo 7년 전 0

네 감사합니다. 고민해보겠습니다. 코드 전문은 여기 있습니다.

#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
 
struct points {
    int y, x;
    points() {}
    points(int y, int x) : y(y), x(x) {}
    bool operator == (points a) {
        return y==a.y && x==a.x;
    }
};
 
int r,c;
int dy[4] = {-1,0,1,0}, dx[4] = {0,1,0,-1};
char m[1505][1505];
int discovered[1505][1505];
vector<points> init;
 
bool ok(int y, int x) {
    return y>=0 && y<r && x>=0 && x<c;
}
 
void melt() {
    for(int i=0;i<r;i++) 
        for(int j=0;j<c;j++)
            if(m[i][j] == '.') 
                for(int l=0;l<4;l++) 
                    if(ok(i+dy[l],j+dx[l]) && m[i+dy[l]][j+dx[l]]=='X')
                        m[i+dy[l]][j+dx[l]] = 'N';
     
    for(int i=0;i<r;i++)
        for(int j=0;j<c;j++)
            if(m[i][j] == 'N')
                m[i][j] = '.';
}
 
 
void solve() {
    int t=0;
    bool Fflag = false;
    for(;t<5000;t++) {
        memset(discovered,0,sizeof(discovered));
        queue<points> q;
        q.push(init[0]);
        q.push(init[1]);
        discovered[init[0].y][init[0].x] = 1;
        discovered[init[1].y][init[1].x] = -1;
 
        while(!q.empty()) {
            points here = q.front();
            q.pop();
 
            for(int i=0;i<4;i++) {
                int nexty = here.y+dy[i], nextx = here.x+dx[i];
                if(ok(nexty,nextx) && discovered[nexty][nextx] != discovered[here.y][here.x] && m[nexty][nextx] != 'X') {
                    if(discovered[nexty][nextx] == -discovered[here.y][here.x]) {
                        Fflag = true;
                        break;
                    }
                    discovered[nexty][nextx] = discovered[here.y][here.x];
                    q.push(points(nexty,nextx));
                }
            }
            if(Fflag)
                break;
        }
 
        if(Fflag)
            break;
        melt();
    }
    printf("%d\n",t);
}
 
int main () {
    scanf("%d %d",&r,&c);
    for(int i=0;i<r;i++) {
        scanf("\n");
        for(int j=0;j<c;j++) {
            scanf("%c",&m[i][j]);
            if(m[i][j] == 'L')
                init.push_back(points(i,j));
        }
    }
    solve();
}

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

문제

문제

출처

ICPC

어떻게 시간을 줄일 수 있을까요?

cokcjswo 7년 전 0

zlzmsrhak 7년 전 0

cokcjswo 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말