3-G 질문 있습니다!

Question

- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 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) 이 부분이 어떻게 해당 정점에 방문한 최소 시간이 되는 것을 알 수 있고 그걸 문제를 풀면서 어떻게 도출할 수 있는걸까요?

큰돌 · Answer

안녕하세요 ㅎㅎ 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 인턴 · Answer

안녕하세요, 인프런 AI 인턴입니다. 김라영님의 질문과 관련하여, 3-G번 질문있습니다. 게시글이 비슷한 상황에서의 질문과 답변을 제공하고 있습니다. 질문자가 언급한 코드는 BFS(Breadth-First Search, 너비 우선 탐색)를 이용하여 최단 경로를 찾는 과정에서 사용하는 로직입니다. if (!visited[next]) 부분은 해당 정점을 처음 방문할 때 행하는 조건 처리이며, else if (visited[next] == visited[now] + 1) 조건은 이미 방문한 정점에 대해 현재 경로가 최단 경로와 동일한 경우, 즉 최단 거리를 가지는 다른 경로가 존재하는 경우를 처리합니다. 이렇게 하면 해당 정점까지 도달하는 데에 걸리는 최소 시간과 그 시간에 도달하는 서로 다른 경로의 수를 계산할 수 있습니다. 기존 답변에서는 이 조건문이 왜 최단 거리를 보장하는지, 왜 이러한 조건을 체크하는지에 대해 설명하고 있습니다. 동시에 최단 경로로 도달할 수 있는 다양한 방법의 수를 계산하는 데 있어서 중요한 역할을 한다고 설명하고 있습니다. 따라서 visited[next] == visited[now] + 1 조건은, 현재 정점에서 다음 정점까지 이동한 거리가 이미 저장된 다음 정점까지의 거리(최소 거리)와 같을 경우를 나타냅니다. 이는 추가적인 경로가 있음을 의미하며, 이를 통해 최소 거리를 유지하면서도 경로의 수를 계산할 수 있습니다. 해당 질문과 관련하여 더 깊이 있는 설명이 필요한 경우, 제안된 링크에서 제공되는 답변 및 추가적인 설명을 살펴보시기를 권장드립니다. 저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.