글 읽기 - 시간 초과가 떴는데 어느 부분을 고쳐야 할까요..?

specimen 5년 전 0

일단 제가 생각한 방식은

불이 이동한 거리보다 사람이 벽에 이동하는 거리가 작을 경우 사람은 탈출이 가능하다 입니다.

그래서 불이 벽에 도달하는 거리와 사람이 벽에 도달하는 거리에 대한 최소값의 경우를 모두 구한 후에 비교하고

사람이 벽에 도달하는 거리가 불이 벽에 도달하는 거리보다 작았을 경우 탈출 가능이라고 짰습니다.

그리고 만약 사람과 벽이 둘다 시작할 때 벽에 존재하는 경우에는 사람이 탈출할 수 있다고 예외처리를 했습니다.

그런데 시간 초과가 떠서 ㅠㅠ 어느 부분을 고쳐야할지 모르겠습니다....

#include <iostream>
#include <queue>
#include <utility>
#include <string.h>
#include <algorithm>
using namespace std;
const int dy[4] = {-1, 1, 0, 0};
const int dx[4] = {0, 0, -1, 1};
int checkfire[1001][1001];
int checkperson[1001][1001];
char map[1001][1001];

int fire(int sy, int sx, int m, int n){
    memset(checkfire, 0, sizeof(checkfire)); // 불이 여러개 있을 경우 초기화
    queue<pair<int, int>> fq;
    fq.push(make_pair(sy, sx));
    checkfire[sy][sx] = 1;
    while(!fq.empty()){
        int y = fq.front().first;
        int x = fq.front().second;
        fq.pop();
        if(y == 0 || x == 0 || y == m - 1 || x == n - 1){
            return checkfire[y][x];
        }
        for(int i = 0; i < 4; i++){
            int yy = y + dy[i];
            int xx = x + dx[i];
            if(yy >= 0 && yy < m && xx >= 0 && xx < n){
                if(map[yy][xx] == '.' && checkfire[yy][xx] == 0){
                    checkfire[yy][xx] = checkfire[y][x] + 1;
                    fq.push(make_pair(yy, xx));
                }
            }
        }
    }
    return 1e9; // 불이 벽에 도달하지 못하면 큰 값을 반환
}

int person(int sy, int sx, int m, int n){
    memset(checkperson, 0, sizeof(checkperson));
    queue<pair<int, int>> pq;
    pq.push(make_pair(sy, sx));
    checkperson[sy][sx] = 1;
    while(!pq.empty()){
        int y = pq.front().first;
        int x = pq.front().second;
        pq.pop();
        if(y == 0 || x == 0 || y == m - 1 || x == n - 1){
            return checkperson[y][x];
        }
        for(int i = 0; i < 4; i++){
            int yy = y + dy[i];
            int xx = x + dx[i];
            if(yy >= 0 && yy < m && xx >= 0 && xx < n){
                if(map[yy][xx] == '.' && checkperson[yy][xx] == 0){
                    checkperson[yy][xx] = checkperson[y][x] + 1;
                    pq.push(make_pair(yy, xx));
                }
            }
        }
    }
    return 1e9; // 사람이 도달하지 못하는 경우 큰 값을 반환
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t, m, n;
    cin >> t;
    while(t--){
        int n, m;
        int mf = 1e9, mp = 1e9;
        cin >> n >> m;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                cin >> map[i][j];
            }
        }

        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(map[i][j] == '*'){//mf는 불이 이동한 최소 거리 
                    mf = min(mf, fire(i, j, m, n));
                }
                if(map[i][j] == '@'){//mp는 사람이 이동한 최소 거리
                    mp = min(mp, person(i, j, m, n));
                }
            }
        }
        if(mf <= mp)
            if(mf == 1 && mp == 1){ // 불과 사람이 벽에서 시작한 경우 예외처리
                cout << mp << '\n';
            }else{
                cout << "IMPOSSIBLE" << '\n';
            }
        else
            cout << mp << '\n';
    }
}

seico75 5년 전 0

1
10 10
####.#####
#........#
#........#
#........#
#........#
#........#
#........#
#........#
#***@****#
##########

위와 같은 맵을 1000 1000 으로 확장하면 약 30초 정도가 걸립니다.

그 경우 불이 약 997개 정도 있을 텐데 각각이 어떻게 번지는지를 다 계산을 해야하기 때문에 연산량이 많은데

어짜피 불이 있는 곳에 또 불이 못간다는 것을 적용하면 휠씬 빨리 처리가 가능합니다.

위에서 queue 를 전역을 빼서 모든 불이 있는 곳을 다 push 하고 한번에 처리하면 될 것 같습니다.

" 불이 이동한 거리보다 사람이 벽에 이동하는 거리가 작을 경우 사람은 탈출이 가능하다 입니다."

이 로직에 예외가 없을지 저도 궁금하네요..

specimen 5년 전 0

어차피 불이 있는 곳에 또 불이 못간다는 의미가

제 코드는 불 주변에 불 밖에 없는 상황일 때도 함수를 호출하여 계산하기 때문에 연산량이 많아진다는 의미인가요?

제가 이해가 안되는 부분이 예를 들어, 최솟값이 아닌 불이 처음에 queue에 들어가서 벽까지의 거리를 계산을 하고 check를 해버리면

이후에 최솟값이 될 수 있는 불은 계산이 안되지 않을까(check가 이미 전에 됬기 때문) 라는게 제 생각입니다. ㅠㅠ

어렵네요..

specimen 5년 전 0

아 그리고 queue에 넣기 전에 우선 bool함수를 선언하여 주변에 .이 없으면 bfs에 들어갈 수 없도록 해놨는데도 틀렸습니다.라고 나오네요.

seico75 5년 전 0

1
10 10
####.#####
#........#
#........#
#........#
#........#
#........#
#........#
#........#
#a**@b***#
##########

a 라는 위치에서 번지기 시작한 불은 전체 영역을 걸쳐서 출구까지 갈꺼고..
작성하신 코드에서는 b라는 위치에서 번기지 시작한 불도 같은 영역을 퍼져서 최소값을 구할 것입니다.
결국 저 영역을 a도. b도 ..... 전부다 퍼지는 것을 계산할 것인데...
만약 저 불들이 동시에 퍼져간다면 전체 영역을 한번에 퍼져나갈 것 같습니다.
글로써 설명이 쉽지는 않은데...
fq 에 들어가는 양을 비교해서 생각하시면 어떨까 하네요.

저는 이렇게 수정하면 어떨까 했습니다.

https://ideone.com/VtPkbj

그런데 그냥 누가 더 빨리 닿는지만 보니까 틀렸습니다가 뜨네요.

seico75 5년 전 1

1
11 4
##.########
#.........#
#*.......@#
######.####

꼭 출구가 하나라는 이야긴 없는 것 같은데..

specimen 5년 전 0

답변 감사드립니다. ㅠㅠ 그래서 다시 짜봤는데도 틀렸네요.. 후...

seico75 5년 전 0

다시 짠 소스도 공개해주시거나 올려주시면 같이 볼 수 있을 것 같네요.

specimen 5년 전 0

이렇게 바꿨습니다.

불이 먼저 움직이고 사람이 움직이도록 하였습니다.

계속 틀리길래 불이 먼저 움직일때 '.'말고 '@'도 만나면 불이 붙도록 해야된다는 피드백을 받아서 고쳐서 했더니

틀렸습니다.가 나옵니다.

#include <iostream>
#include <queue>
#include <algorithm>
#include <utility>
#include <string.h>
using namespace std;
const int dy[4] = {0, 0, -1, 1};
const int dx[4] = {-1, 1, 0, 0};
int check[1010][1010]; // person
bool ch[1010][1010]; // fire
char map[1010][1010];
queue<pair<int, int>> fq; // fire
queue<pair<int, int>> sq; // person
int main(){
    int T;
    cin >> T;
    while(T--){
        int N = 0, M = 0, nn = 1;
        memset(check, 0, sizeof(check));
        memset(ch, false, sizeof(ch));
        while(!fq.empty()) fq.pop();
        while(!sq.empty()) sq.pop();
        bool out = false;
        cin >> N >> M;
        for(int i = 0; i < M; i++){
            for(int j = 0; j < N; j++){
                cin >> map[i][j];
            }
        }
        for(int i = 0; i < M; i++){
            for(int j = 0; j < N; j++){
                if(map[i][j] == '*' && ch[i][j] == 0){
                    fq.push(make_pair(i, j)); //fire queue
                    ch[i][j] = true;
                }
                if(map[i][j] == '@' && check[i][j] == 0){
                    sq.push(make_pair(i, j)); //person queue
                }
            }
        }
        while(1){
            int fqs = fq.size();
            int sqs = sq.size();
            if(sqs == 0 && fqs == 0) break;
            while(fqs--){
                int y = fq.front().first;
                int x = fq.front().second;
                ch[y][x] = true;
                fq.pop();
                for(int i = 0; i < 4; i++){
                    int yy = y + dy[i];
                    int xx = x + dx[i];
                    if(yy >= 0 && yy < M && xx >= 0 && xx < N){
                        if((map[yy][xx] == '.') && !ch[yy][xx]){
                            fq.push({yy,xx});
                            map[yy][xx] = '*';
                            ch[yy][xx] = true;
                        }else if((map[yy][xx] == '@' && !ch[yy][xx])){
                            fq.push({yy,xx});
                            map[yy][xx] = '*';
                            ch[yy][xx] = true;
                        }
                    }
                }
            }
            while(sqs--){
                int y = sq.front().first;
                int x = sq.front().second;
                sq.pop();
                if(y == M - 1 || y == 0 || x == N - 1 || x == 0){
                    out = true;
                    nn = check[y][x];
                    break;
                }
                for(int i = 0; i < 4; i++){
                    int yy = y + dy[i];
                    int xx = x + dx[i];
                    if(yy >= 0 && yy < M && xx >= 0 && xx < N){
                        if(map[yy][xx] == '.' && check[yy][xx] == 0){
                            sq.push({yy,xx});
                            check[yy][xx] = check[y][x] + 1;
                            map[yy][xx] = '@';
                        }
                    }
                }
            }
        }
        if(out){
            cout << nn + 1<< '\n';
        }else{
            cout << "IMPOSSIBLE" << '\n';
        }
    }
}

seico75 5년 전 0

1
11 7
#########.#
#.......#.#
#.......#.#
#.......#.#
#....####.#
#*...##..@#
#######.###

종료 조건이 문제가 있는 것 같습니다.

44라인만 고쳐도 통과합니다.

그리고 통과해도 잘 만드신 분들의 소스를 참고하시면 도움이 많이 될 것 같습니다.

specimen 5년 전 0

넵 시간 내주셔서 정말정말정말 감사합니다.

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

문제

문제

출처

ICPC

시간 초과가 떴는데 어느 부분을 고쳐야 할까요..?

specimen 5년 전 0

seico75 5년 전 0

specimen 5년 전 0

specimen 5년 전 0

seico75 5년 전 0

seico75 5년 전 1

specimen 5년 전 0

seico75 5년 전 0

specimen 5년 전 0

seico75 5년 전 0

specimen 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말