3-G 테스트케이스 질문드립니다.

안녕하세요 선생님! 선생님의 해설 잘 들었습니다.

다만 제 코드가 어떤 테스트케이스에서 걸리는지 도저히 모르겠어요. 3시간 넘게 테스트케이스만 만들고 테스트해봤는데 다 잘 되고 있어서..

제 코드는 다음과 같이 구현되어 있어요.

경우의 수는 더하기라는 것을 활용
노드의 level(depth,거리) 단위로 bfs 진행
이를 위해 정적으로 size 활용한 while(size--) 활용
visited, cnt 배열로 각각 최소 거리와 최소 시간을 도출해냄

다만 제 코드의 유의할점은 prevLoopNum과 loopNum을 사용한다는 점이에요. 이는

0 -> 1 ---(더하기 1)--> 2

0 -> 1 ---(곱하기 2)---> 2

와 같은 경우에 서로 다른 경로로 인식되는 경우를 방지하기 위함이에요. 즉,

입력: 0 3
출력: 
3
1

이 나오도록 만들기 위함이에요.

https://www.acmicpc.net/source/share/cc7572065f6146b8850e8ee371089353

안녕하세요 케이님 ㅎㅎ

상당히 잘 짜셨네요 ㅎㅎ 코드가 우아합니다.

와 같은 경우에 서로 다른 경로로 인식되는 경우를 방지하기 위함이에요. 즉,

-> 아닙니다. 그 경우에도 다른 경로로 인식되어야 합니다. 0 3은 2가 되어야 합니다.

cur > MAXPOS

-> 이부분 때문에 틀립니다. 이렇게 되면 cur은 MAXPOS를 참조할 수 있는데 배열 끝을 참조하게 됩니다. 배열을 + 1 또는 + 4로 더 크게 설정해야 합니다.

loopnum

        int prevLoopNum = size - 1;

        while(size--){//이 loop 자체가 위계 (해당 loop 내에서는 동일한 위계, 즉 동일한 거리를 가짐)
            int loopNum = size;

이게 이해가 안가는코드인데요. 저부분은 아마 위쪽과 아래쪽 루프를 구분하고자 함인 것 같은데 -> queue의 사이즈가 같은 순간에는 구분이 안되지 않나요? 그리고 애초에 왜 필요한지 모르겠습니당..

수정된 코드는 다음과 같습니다. 나머지부분은 잘 하셨습니다.

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

const int MAX_POS = 100000;
int n,k; 
int visited[MAX_POS + 1]; //거리(시간)으로도 사용
int cnt[MAX_POS + 1]; //해당 node에 최소시간으로 도달한 경우의 수

void bfs(int start){
    queue<int> q; 
    q.push(start); 
    visited[start] = 1; cnt[start] = 1;

    while(q.size()){
        int size = q.size(); //정적으로 계산
        bool endFlag = false; //최단 거리 찾으면 불필요하게 찾지 않고 탈출
        int prevLoopNum = size - 1;

        while(size--){//이 loop 자체가 위계 (해당 loop 내에서는 동일한 위계, 즉 동일한 거리를 가짐)
            int loopNum = size;
            int prev = q.front(); q.pop(); 
            
            //+1, -1, *2 진행
            for(int i = 0; i < 3; i++){
                int cur;
                switch(i){
                    case 0: 
                        cur = prev + 1;
                        break;
                    case 1: 
                        cur = prev - 1;
                        break;
                    case 2: 
                        cur = prev * 2;
                        break;
                    default:
                        throw runtime_error("도달해서는 안됩니다.");
                }
                
                if(cur < 0 || cur > MAX_POS) continue; 
                if(!visited[cur]){  
                    q.push(cur);
                    cnt[cur] += cnt[prev]; //경우의 수는 더하기!!! (단순하게 cnt[cur]++ 하지말것)
                    visited[cur] = visited[prev] + 1;
                }else if(visited[cur] == visited[prev] +1){ 
                    //루프 번호가 다르다 == 다른 곳에서 온 경우. 
                    //그러나 안티패턴이라 생각. 뜻을 주석 없이는 파악하기 어렵고 버그 유발이 쉬움
                    cnt[cur]+= cnt[prev];
                }
            }

            prevLoopNum = loopNum;
        }

        if(endFlag) return;  
    }
}

int main(){
    cin >> n >> k;
    bfs(n);
    cout << visited[k] - 1 << "\n" << cnt[k] << "\n";
    return 0;
}

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

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

감사합니다.

강사 큰돌 올림.

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