글 읽기 - 시간초과 질문있습니다.

dirtkguddn 2년 전 0

저는 이차원 배열로 map과 copy 한 smap을 만들어서 map[i][j] 1이 있을때 하나씩 0으로 바꿔주고 bfs를 각각 돌려서 최소 시간을 찾는 코드를 짜봤는데 왜 시간초과가 날까요? 어떻게 고치면 좋을지 궁금합니다.

질문에 있는 반례들은 다 확인해봤는데 이상 없었습니다!

#include<iostream>
#include<queue>
#include<string.h>
using namespace std;

queue<pair<int, int>> q;
int dx[] = { 0,0,1,-1 }, dy[] = { 1,-1,0,0 };
int map[1010][1010];
int smap[1010][1010];
int check[1010][1010];
int N, M;

int BFS() {
    q.push(make_pair(0, 0));
    check[0][0] = 1;
    while (!q.empty()) {
        int y = q.front().first;
        int x = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int ny = y + dy[i];
            int nx = x + dx[i];
            if (ny < 0 || ny >= N || nx < 0 || nx >= M || (map[ny][nx] == 1 && check[ny][nx] ==0) || check[ny][nx]) continue;
            
            map[ny][nx] = map[y][x] + 1;
            if (ny == N - 1 && nx == M - 1) return map[y][x]+2;
            check[ny][nx]=1;
            q.push(make_pair(ny, nx));
        }
    }
    return 0;
}
void make() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            map[i][j] = smap[i][j];
        }
    }

}

int main() {
    int first = 0;
    int wallbreak = 1000000;
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            scanf("%1d", &map[i][j]);
            smap[i][j] = map[i][j];
        }
    }       
 if (N == 1 && M == 1) {
        cout << 1;
        return 0;
    }// 예외조건


    first = BFS();
    while (!q.empty()) {
        q.pop();
    }

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {

            if (smap[i][j] == 1) {
                make();
                map[i][j] = 0;
                memset(check, 0, sizeof(check));
                while (!q.empty()) {
                    q.pop();
                }

                int t = BFS();

                if (t != 0 && wallbreak > t) wallbreak = t;
            }
        }
    }
    if (first == 0 && wallbreak == 1000000) cout << -1;
    else cout << wallbreak;
}

drash99 2년 전 0

모든 벽을 부셔서 최단거리를 계속 구해보는 알고리즘으로는 이 문제를 풀 수 없어요.

dirtkguddn 2년 전 0

이유가 뭔지 알 수 있을까요??

0000000000 2년 전 1

시간이 (BFS의 기본 시간) * (부술 수 있는 벽의 수) 만큼 걸리고 부술 수 있는 벽의 수가 최대 1000*1000이기 때문에 시간제한에 걸립니다. 다른 방법을 생각해 보세요.

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

문제

문제

출처

ICPC

시간초과 질문있습니다.

dirtkguddn 2년 전 0

drash99 2년 전 0

dirtkguddn 2년 전 0

0000000000 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말