안녕하세요 3-G 질문 있습니다!

안녕하세요 잼코님 ㅎㅎ

대부분은 정말 잘짜셨는데요. calc나 0, 1 처리 등 괜찮지만..

이 코드에는 몇가지 문제점이 있고 그 때문에 메모리 초과가 발생한 거 같습니다.

이 메모리초과는 메모리를 많이 설정해서 발생하는게 아니라 제가 생각했을 때 이건 UB입니다. 불필요한, 이상한 코드 때문에 내가 의도한 대로 코드가 구동되지 않아 메모리 초과 등 예상치 못한 상황, unexpected behavior이 발생하는 것입니다.

자 그러면 코드를 좀 지적해볼게요 ㅎㅎ

        for (int i = 0; i < 3; i++) {
            int next = max(0, calc(i, n));

이 코드요.

범위 자체가 0이상이기 때문에 max를 한 것은 알겠지만 음수일 경우 continue를 해야하는거아닐까요? 예를 들어 0지점에서 -1이 떠서 -1로 이동하는 경우 해당 경우의 수를 완전히 "제외"해야 하지만 이 코드는 그 경우의 수를 0인 경우의 수로 만들어서 "포함"시킵니다.

            if (next == k) {
                res = min(res, visited[n]);

visited를 잘 활용하지 못합니다. BFS는 visited라는 최단거리 배열을 만들고 "단 한번의 탐색"으로 최단거리를 추출하는 로직입니다. 이 코드는 res를 갱신시켜가며 visited중에 가장 작은 것을 뽑는데 그렇게 할 필요가 없습니다.

        int n = q.front(); q.pop();

        for (int i = 0; i < 3; i++) {
            int next = max(0, calc(i, n));
            
            if (next == k) {
                res = min(res, visited[n]);
                mp[visited[n]]++;
                break;
            }

visited는 next를 기반으로 체크해야 합니다. 물론 q.front()를 기반으로 체크해도 되죠. 무슨 말이냐면 만약 next == k를 저 if문을 통해 체크하고 visited[n]을 확인할거면 저 int n = ... 아래에 놓아야 한다는 것입니다.

내가 이지점에서 ~~ 다른 지점으로 갈 때의 visited를 만들고 >> visited를 체크.

내가 이지점에서 만들어진 visited를 체크하던가 해야 합니다.

즉, 이런코드가 더 적합합니다.

            if (next == k) {
                res = min(res, visited[next]);
                mp[visited[next]]++;
                break;
            }

            if (next == k) {
                res = min(res, visited[n]);
                mp[visited[n]]++;
                break;
            }

            if (next > 100000 || visited[next] > res) continue;
            visited[next] = visited[n] + 1;
            q.push(next);

이 로직이 가장 이상한데요. visited[next] > res면 continue를 하게 되어있습니다.

예를 들어 1 - 2 - 3 이렇게 있고 3지점을 3분만에 방문했습니다. 근데 5라는 지점에서 3지점을 3분만에 방문하는 경우가 있습니다. 그 때 res는 설정되어 있지 않다면? res = 0이겠죠? 그 때! visited[next] > res가 되게 됩니다. 즉, 해당 경우의 수를 체크하지 못하게 됩니다. 5라는 지점에서 부터 시작해 3지점을 거쳐 >> 결국 목적지인 k지점에 다다라도 5라는 지점에서의 경우의 수를 체크하지 못하기 때문에 틀린 코드가 됩니다.

해당부분들을 수정해주시면 될 것 같습니다. 그리고 이 문제의 경우 수빈이가 20만까지 갈 수 있기 때문에 10만으로 하는게 아니라 20만 이상으로 배열을 설정해주어야 합니다. 우리가 어딘가로 갈경우 또는 탐색할경우 등의 경우의 수를 담는 것이 최단거리 배열 visited이기 때문에 해당 경우의 수를 체크하기 위해서는 해당 "가는 경우" 에 대한 인덱스를 참조할 수 있게 만들어주어야 합니다.

감사합니다.

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