시간초과

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트

4-D

작성

154

안녕하세요, 시간초과로 통과하지 못해서 질문드립니다.

http://boj.kr/c89e043975f349bbb7a4066422235fc0

이전에 단순히 dfs만 써서 풀었을 때와 로직은 동일합니다. 다만 이번엔 visited를 2차원 벡터가 아닌 int형 변수 하나로 처리했고 방문하는 경우엔 | 연산으로 비트를 켜줬고 방문을 마치고 나선 & ~(1<<idx) 와 같이 비트를 꺼줬습니다.

선생님의 코드와 제 코드의 함수 호출을 비교해보니 예제의 경우에선 함수 호출 횟수도 동일했습니다. 그런데 시간초과가 생기는 이유는 무엇일까요?

c++코딩-테스트

답변 1

큰돌

지식공유자

안녕하세요 Marcu님 ㅎㅎ

이부분은 call by reference로 해야 하는 부분인데요.


void dfs(vector<vector<char>> & v, int visit, int r, int c, int num)

이렇게 바꿔보시겠어요?

해당부분은 교안내의 다음 부분을 참고 부탁드립니다.

참조에 의한 호출로 넘겨야 할 때

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

int dr[4] = { 0,1,0,-1 };
int dc[4] = { -1,0,1,0 };
int ans = 0;
int R, C, tmp;

void dfs(vector<vector<char>> & v, int visit, int r, int c, int num)
{ 

    if (num > ans) ans = num;
    for (int i = 0; i < 4; ++i)
    {
        int nr = r + dr[i];
        int nc = c + dc[i];
        if (nr < 0 || nc < 0 || nr >= R || nc >= C) continue;
        if (visit & (1 << (int)v[nr][nc] - 'A')) continue;
        visit |= (1 << (int)v[nr][nc] - 'A');
        dfs(v, visit, nr, nc, num + 1);
        visit &= ~(1 << (int)v[nr][nc] - 'A');
    } 

}

int main()
{ 
    cin >> R >> C;

    string str;
    vector<vector<char>> v;
    for (int i = 0; i < R; ++i)
    {
        cin >> str;
        v.push_back(vector<char>());
        for (int k = 0; k < C; ++k)
        {
            v[i].push_back(str[k]);
        }
    }

    int visit = 0;

    visit |= (1 << (int)v[0][0] - 'A');
    dfs(v, visit, 0, 0, 1);
    cout << ans;
}

그리고 제가 좀 다듬어봤습니다.

참고부탁드립니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

Maruche

질문자

아하.. 2차원 배열을 계속해서 복사 시키니까 오버헤드가 발생했다는 거군요. 그렇게 따지고 보니까 비트마스킹을 쓰지 않고 dfs만 썼을 때는 2차원 벡터를 레퍼런스로 전달했었네요.

사실 처음에 call-by-value로 작성을 했던게, visit을 원상복구 해주는 부분없이 단순히 재귀 dfs로도 예제를 통과하기에 그렇게 제출을 했던건데 앞으로 시간초과 문제가 있을 수 있으니 큰 자료구조는 레퍼런스로 보내고 원복을 시켜야겠습니다.

그리고 교안에서 궁금한게, 주차별 이론 강의는 큰돌님 블로그에 올라와있고 교안에 대한 수업은 몇몇 부분만 올라와있던데 이건 따로 숙지하고 강의를 병행하면 되는걸까요?

감사합니다.

큰돌

지식공유자

>> 네 맞습니다. 0주차강의+ 교안숙지 >> 1주차강의부터는 블로그에 개재되어있는 것 + 강의 이렇게 공부해주시면 됩니다. ㅎㅎ

감사합니다.

인프런 커뮤니티 질문&답변

시간초과

참조에 의한 호출로 넘겨야 할 때