3-H 시간초과

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

3-H

해결된 질문

23.11.13 14:37 작성

283

https://www.acmicpc.net/source/share/71ef58daaf4144a5bf9ab254f862398a

3-H 숨바꼭질4 문제에서 정점을 방문하면서 방문한 정점을 벡터에 담고 그 벡터를 큐로 넘겨주어서 k에 도착했을때 벡터를 출력하도록 로직을 짰습니다.

하지만 시간초과가 나오는데 원인을 잘 모르겠어서 질문드립니다.

그리고 추가로 c++에서는 벡터나 배열의 일부분을 잘라서 이용하는 로직은 잘 사용하지 않는지 궁금합니다.

JS로 알고리즘을 풀때는 splice 나 slice등으로 배열을 자르고 복사하는 방식을 자주 사용했었는데 지금까지 큰돌님의 강의를 들으면서 그 와 같은 방식은 잘 못 본 것 같아서 질문드립니다.

c++코딩-테스트

답변 2

김상민

질문자

2023. 11. 15. 14:29

답변 감사합니다.
큰돌님 풀이대로 해서 다시 풀어봤고 저런 방식을 사용하는게 아직은 익숙하진 않지만 좋은 것 같습니다. 연습해볼게요~

큰돌

지식공유자

2023. 11. 15. 08:18

안녕하세요 상민님 ㅎㅎ

3-H 숨바꼭질4 문제에서 정점을 방문하면서 방문한 정점을 벡터에 담고 그 벡터를 큐로 넘겨주어서 k에 도착했을때 벡터를 출력하도록 로직을 짰습니다.

>> 이부분이 시간초과의 원인인듯 싶습니다.

        for(int there : {here + 1, here - 1, here * 2}) {
            if(there <= 200000 && there >=0) {
                if(visited[there] == 0) {
                    visited[there] = visited[here] + 1;
                    v.push_back(there);

이렇게 되면 경우의 수 모두 vector에다가 여러번 담기게 됩니다.

예를 들어1부터 100 까지 간다고 하면

1 2

1 2 3

1 2 3 4

...

이런 값들이 vector에 담기게 되고 해당 부분에 대한 코스트가 시간초과로 이어지는 것 같습니다.

다른부분의 로직은 괜찮습니다.

제 해설 코드 - prev를 기반으로 해보시는건 어떨까요?

parent나 prev라는 변수명을 써도 되구요.

이런식으로 말이죠.

void bfs(int n) {
    queue<int> q;
    q.push(n);
    visited[n] = 1;
    parent[n] = -1;  
    while(!q.empty()) {
        int here = q.front();
        q.pop();

        for(int there : {here + 1, here - 1, here * 2}) {
            if(there <= 200000 && there >= 0 && visited[there] == 0) {
                visited[there] = visited[here] + 1;
                parent[there] = here;  
                q.push(there);
                if(there == k) return;  
            }
        }
    }
}

그리고 추가로 c++에서는 벡터나 배열의 일부분을 잘라서 이용하는 로직은 잘 사용하지 않는지 궁금합니다.

>> 음... 배열 내부로부터 sub배열을 추출하는 로직말씀이시죠? 필요하면 쓸 것 같습니다. 잘 사용하지 않는게 아니라 필요하면 사용할 것 같습니다.

C++에서는 잘 사용하지 않는다 = 아닙니다.

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

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

감사합니다.

강사 큰돌 올림.

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

3-H 시간초과