글 읽기 - 가장 큰 입력도 빠르게 처리하는데 시간초과가 납니다.

y_ht 3년 전 1

20 * 20 크기의 입력도 제대로 처리하는 것을 확인했습니다.

그런데 시간초과가 나옵니다.. 왜 그런지 이유를 모르겠어요

소스코드에 구현 내용에 관한 주석을 첨부했습니다.

하단에 TC로 적어둔 내용은 제대로 정답이 나오는지 확인한 테스트케이스 모음입니다.

#include <bits/stdc++.h>
using namespace std;

// 상하좌우 이동용 배열
int dr[] = {0, 1, 0, -1};
int dc[] = {1, 0, -1, 0};

/* 전역변수
 * @ board : 입력받은 문자를 아스키코드값으로 저장함
 * @ v   : 키는 아스키코드, 밸류는 0 또는 1로 저장해서 방문여부 체크하는 맵
 * @ R ,C  : 문제에서 주어진 R과 C
 */
int board[30][30];
map<int, int> v;
int R, C;

/* dfs 함수
 * @ r, c : dfs함수가 현재 방문한 행과 열의 위치를 r, c로 받음
 * @ ret  : dfs함수가 리턴하는 값. 리턴값에 1을 더해주면 정답이 되도록 구현함
 */
int dfs(int r, int c) {
    int ret = 0;
    
    // 맨 처음 출발시에는 map에 체크해줌
    // 그 외의 경우에는 아래 for 루프에서 dfs호출과 동시에 map에 체크함
    if (v[board[r][c]] == 0) v[board[r][c]] = 1;

    // 4방향으로 호출 시작
    // if문에서는 다음 위치를 나타내는 nr, nc가 게임판을 벗어나는지 먼저
    // 체크하고 마지막 조건으로 해당 위치 게임판의 문자가 맵 v에서 0인지
    // 아닌지를 검사한다. (0이면 미방문)
    for (int i = 0; i < 4; i++) {
        int nr = r + dr[i], nc = c + dc[i];
        if (0 <= nr && nr < R && 0 <= nc && nc < C && v[board[nr][nc]] == 0) {
            v[board[nr][nc]] = 1;
            ret = max(ret, dfs(nr, nc) + 1);
            v[board[nr][nc]] = 0;
        }
    }
    return ret;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> R >> C;
    string input;
    for (int i = 0; i < R; i++) {
        cin >> input;
        for (int j = 0; j < C; j++) {
            board[i][j] = input[j];
            v[input[j]] = 0;
        }
    }
    cout << dfs(0, 0) + 1 << '\n';
}

/* TC
5 5
IEFCJ
FHFKC
FFALF
HFGCF
HMCHH

20 20
POIUYTREWQBWKALSLDLG
LKJHGFDSAMASFBMBOSOZ
NMBVCXZAKPAISJLBMROW
CEVTBFNIMLASNCVKNDKX
VPQLBKENMSAHBBLFOWPQ
ZLSKJJBNBEASZNFDGHHN
GPBMDLQDALAASBBXCEGA
APQIKBMROIBANPOBLMKS
ASKSKVJRPORHNOXZKSPN
LSNVOEOOOKAKANLGKOAX
AKVMBOTOWPQOJBSMSPEP
BLLBKWPEPBKNMROSALLP
BNQLDNBMKOVMEMELSLMA
RLEPQQPVKJRNBITNBSAS
ZXMCOITRPWKLPGKHNGMS
QOBKRPPPZSLEMPNKSPPR
OQJDNZNANDWKQKVJEOGJ
QUYVOIUYWERLKJHASDFV
ZCVWRETPOIUHJKLVBMAS
QWERZCVUIAFDKHSDFHSA

3 4
ABCD
BCDA
CDEF

2 4
CAAB
ADCB

*/

julysky 3년 전 2

안녕하세요, 제가 해당 코드를 요리조리 조금씩 수정해서 제출해봤는데,

결론만 말하면

map<int, int> v ; 가 매우 느립니다.

이부분만 int v[256]; 으로 바꿔주셔도 아주 빨라져요.

map<int, int> 이 느린 이유는 map은 key 값을 이용해 value에 접근하는게 배열의 인덱스와 달리 O(log n) 이 걸리기 때문입니다. (배열의 인덱스를 이용한 접근은 O(1))

map<int, int> v 를 굳이 살리면서 통과하려면

dfs 함수내에서 코드를 조금 손 볼 필요가 있습니다. 예를들어서

if (v[board[r][c]] == 0) v[board[r][c]] = 1; 해당 부분은 맨 처음에만 true이고 그외엔 전부 false 이기 때문에 쓸데 없이 매번 조건비교를 하면서 시간낭비를 합니다.

이부분을 아예 dfs 밖으로 빼도 아슬아슬하게 통과하네요.

y_ht 3년 전 1

@julysky

자세한 설명 너무 감사합니다! 저는 map<int, int>가 처음 생성할때 O(logN)이고, 그 이후부터는 O(1)으로 접근한다고 잘못 알고있었네요... 그래서 set을 쓰다가 map으로 바꿔준건데 map도 O(logN)인건 처음 알았어요.

if문도 수행시간에 거의 영향을 안끼칠거라 생각하고 작성한건데 다 시간을 잡아먹었군요.. 많이 배워갑니다 감사합니다!

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

문제

문제

출처

ICPC

가장 큰 입력도 빠르게 처리하는데 시간초과가 납니다.

y_ht 3년 전 1

julysky 3년 전 2

y_ht 3년 전 1

@julysky

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말