3-G 질문 있습니다!

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

3-G 와 테스트케이스 팁

작성

111

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.안녕하세요 큰돌님 강의 잘 보고 있습니다! 다름이 아니라 코드 중에 이해가 잘 안되는 부분이 있어서 질문드립니다!

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];
                }

위와 동일하 코드가 있는데 if(!visited[next])코드는 한번도 방문한 정점이 아니라 처음 방문할 때가 해당 정점을 방문할 최소 시간이라는 것이라는 것은 알겠는데,else if (visited[next] == visited[now] + 1) 이 부분이 어떻게 해당 정점에 방문한 최소 시간이 되는 것을 알 수 있고 그걸 문제를 풀면서 어떻게 도출할 수 있는걸까요?

c++코딩-테스트

답변 2

큰돌

지식공유자

안녕하세요 ㅎㅎ

else if (visited[next] == visited[now] + 1) 이 부분이 어떻게 해당 정점에 방문한 최소 시간이 되는 것을 알 수 있고 그걸 문제를 풀면서 어떻게 도출할 수 있는걸까요?

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]; }

이 코드를 해석해볼게요.

BFS로 visited를 만든다 => visited에는 최단거리가 쌓임.

visited[next] = visited[now] + 1;이라는 식을 기반으로 최단거리가 쌓임.

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

>> 만약 이 정점으로부터 그 다음의 정점이 최단거리다?(visited[next] == visited[now] + 1)-> 최단거리의 경우의수를 더한다.

라고 보시면 됩니다.

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

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

감사합니다.

강사 큰돌 올림.

인프런 AI 인턴

안녕하세요, 인프런 AI 인턴입니다. 김라영님의 질문과 관련하여, 3-G번 질문있습니다. 게시글이 비슷한 상황에서의 질문과 답변을 제공하고 있습니다.

질문자가 언급한 코드는 BFS(Breadth-First Search, 너비 우선 탐색)를 이용하여 최단 경로를 찾는 과정에서 사용하는 로직입니다. if (!visited[next]) 부분은 해당 정점을 처음 방문할 때 행하는 조건 처리이며, else if (visited[next] == visited[now] + 1) 조건은 이미 방문한 정점에 대해 현재 경로가 최단 경로와 동일한 경우, 즉 최단 거리를 가지는 다른 경로가 존재하는 경우를 처리합니다. 이렇게 하면 해당 정점까지 도달하는 데에 걸리는 최소 시간과 그 시간에 도달하는 서로 다른 경로의 수를 계산할 수 있습니다.

기존 답변에서는 이 조건문이 왜 최단 거리를 보장하는지, 왜 이러한 조건을 체크하는지에 대해 설명하고 있습니다. 동시에 최단 경로로 도달할 수 있는 다양한 방법의 수를 계산하는 데 있어서 중요한 역할을 한다고 설명하고 있습니다.

따라서 visited[next] == visited[now] + 1 조건은, 현재 정점에서 다음 정점까지 이동한 거리가 이미 저장된 다음 정점까지의 거리(최소 거리)와 같을 경우를 나타냅니다. 이는 추가적인 경로가 있음을 의미하며, 이를 통해 최소 거리를 유지하면서도 경로의 수를 계산할 수 있습니다.

해당 질문과 관련하여 더 깊이 있는 설명이 필요한 경우, 제안된 링크에서 제공되는 답변 및 추가적인 설명을 살펴보시기를 권장드립니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.

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

3-G 질문 있습니다!