3-G 최단거리 개수

작성한 질문수 7

1

안녕하세요 태승님 ㅎㅎ

전반적으로 잘 구축하셨지만

코드를 보면 bfs라고 하기에는 좀 아쉬운 부분이 있습니다.

            if(nxt==K) {
                v.push_back(arr[cur]+1);
                res = min(res, arr[cur]+1);
            }

앞의 코드를 보면 nxt = K를 기반으로 최단거리 배열 arr[cur] + 1 중에서 최소값을 담고 있죠?

 arr[nxt] = arr[cur] + 1;

이렇게 만들어진 배열을 기반으로요.

근데 최단거리 배열은 BFS로 만들어질 때 이미 최단거리라는게 자명합니다. 따라서 min 로직은 불필요합니다.

            if(arr[nxt] != -1) continue;

이 로직을 보면 만약 해당지점을 방문했다면 그 경우의 수를 확인하지 않고 continue를 걸고 있습니다.

이렇게 되면.

이런 반례가 있어요.

예를 들어

3지점까지 5초안에 왔습니다. 그리고 4지점이 도착지점이라고 했을 때 3 - > 4 이렇게 되겠죠?

자 근데 여기서 3지점까지 5초안에 오는 또 다른 경우의 수가 있을 수 있습니다. 근데 이미 3지점은 방문처리가 되어 continue를 하게 되어서 해당 부분의 경우의 수는 확인하지 못하게 되는 것이죠.

그래서 다음코드같은 로직이 필요합니다.

                if (!visited[next]) {
                    q.push(next); 
                    visited[next] = visited[now] + 1;
                    cnt[next] += cnt[now];
                } else if (visited[next] == visited[now] + 1) {
                    cnt[next] += cnt[now];
                }

감사합니다.