3-H 시간초과

16 asked

0

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

0

안녕하세요 상민님 ㅎㅎ

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점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.