글 읽기 - [ c++ ] 왜 속도가 많이 느린지 잘 모르겠습니다..

seonbi_g 3년 전 0

안녕하세요, 이번 연구소 문제와 관련해 여쭤볼 게 있어 질문 남깁니다.

먼저, 문제 풀이 방법은 아래와 같습니다.

1. 벽 3개를 세우는 경우의 수에 대해서 dfs 수행

2. 벽을 3개 세우면 bfs 수행

3. 안전 구역의 수를 비교

이런 식으로 구현을 했고 정답은 맞았지만 시간이 252ms 가 나왔습니다.

어느 부분에서 시간이 이렇게 많이 걸리는 걸까요?

전역변수 사용이 문제가 되는건지, 아니면 dfs, bfs를 동시에 안쓰고 풀 수 있는 방법이 있는건지...

고수님들 조언 부탁드립니다 ! 감사합니다 :-)

#include<iostream>
#include<vector>
#include<queue>
using namespace std;


// 바이러스의 좌표를 저장하기 위한 구조체
typedef struct Pair {
    int x;
    int y;
} p;

// ans : 정답용 변수
// n   : 가로길이
// m   : 세로길이
// osa : 처음 지도를 입력받았을 때 0의 수
int ans, n, m, osa;

// dt  : 방향 이동용 델타 배열
int dt[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

// mo   : dfs용 지도
// cm   : bfs용 지도
int om[8][8], cm[8][8];

// pq   : 바이러스 위치를 가지고 있는 원본 큐
queue<p> oq;

// 좌표가 범위내에 있는지 확인
bool isInRange(const p& cp) {
    return 0 <= cp.x && cp.x < n && 0 <= cp.y && cp.y < m;
}

// dfs를 돌고나서 벽을 3개 세운 뒤 bfs를 할 때 사용할 배열 초기화
void copyMap() {
    for(int i = 0; i < n; ++i)
        for(int j = 0; j < m; ++j)
            cm[i][j] = om[i][j];
}

// bfs 함수
void bfs() {

    // bfs용 큐
    queue<p> q(oq);
    
    // 감염된 지역의 수
    int infected = 0;

    // 감염 가능 구역이 없을 때 까지 반복
    while(q.size() > 0) {
        // 현재 위치
        p c = q.front();
        q.pop();

        for(int i = 0; i < 4; ++i) {
            // 다음 위치
            p tc = {c.x + dt[i][0], c.y + dt[i][1]};
            // 범위 확인 후 감염가능 지역인 경우
            if(isInRange(tc) && cm[tc.x][tc.y] == 0) {
                // 감염 및 해당 좌표 큐에 넣기
                q.push(tc);
                cm[tc.x][tc.y] = 2;
                infected++;
            }
        }
    }

    // 원본 구역 - 감염 구역
    int saveArea = osa - infected;
    // 지금까지 컸던 값과 비교
    ans = ans < saveArea ? saveArea : ans;
}

void dfs(int depth)
{
    // 벽을 3개를 다 세웠으면 
    if (depth == 3)
    {
        // bfs용 맵 초기화
        copyMap();
        // bfs 수행
        bfs();
    }
    else
    {
        // 벽을 세울 수 있는 모든 경우의 수 체크
        for (int i = 0; i < n; ++i)
        {
            for (int j = 0; j < m; ++j)
            {
                if (om[i][j] == 0)
                {
                    om[i][j] = 1;
                    dfs(depth + 1);
                    om[i][j] = 0;
                }
            }
        }
    }
}

int main() {

    // 가로, 세로 입력
    scanf("%d %d", &n, &m);

    // 원본 크기 갱신
    osa = n * m - 3;

    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            scanf("%d", &om[i][j]);
            // 안전 구역 수 갱신 및 좌표 저장
            if(om[i][j] > 0) osa--;
            if(om[i][j] == 2) oq.push({i,j});
        }
    }

    // 모든 좌표에 대해서 벽 세우기 시작
    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < m; ++j) {
            if(om[i][j] == 0) {
                om[i][j] = 1;
                dfs(1);
                om[i][j] = 0;
            }
        }
    }

    printf("%d\n", ans);

    return 0;
}

glflakcm 3년 전 0

답변 달기에는 저도 초보지만 제가 짠 것을 기준으로 생각해보면 dfs 와 bfs 를 둘다 사용할 필요가 있을까 싶어요. 저 같은 경우에는 벽을 세울 수 있는 모든 경우의 수는 next_permutation 라이브러리 함수를 사용했습니다. dfs 는 바이러스가 퍼져나가는 용도로만 사용했구요. https://github.com/ronick-gram...

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

문제

문제

출처

ICPC

[ c++ ] 왜 속도가 많이 느린지 잘 모르겠습니다..

seonbi_g 3년 전 0

glflakcm 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말