인프런 커뮤니티 질문&답변
작성한 질문수
3 - G 질문있습니다.
해결된 질문
작성
·
31
0
강의의 코드 중 25번째 줄 까지는 이해를 했습니다.
그러나 26 - 28번째 줄의 부분에서 이해가 안가는 것이 있습니다.
문제는 최단거리를 바라고 있습니다.
그렇다면 26번째 줄,
else if (visited[next] == visited[now] + 1)
에서 visited[next]는 next에 도달한 가장 적은 걸음 수를 뜻합니다.
여기서 제가 이해가 안되는것은 visited[next]가 어떻게 가장 적은 걸음수가 보장 되는지 입니다.
visited[now] + 1이 visited[next]보다 작아서 새로운 경로가 더 빠를 수 있는 경우의 수는 신경을 안써도 되는 이유가 무엇인지 궁금합니다.
BFS를 사용하면, 가장 먼저 도착한 케이스가 가장 빠른 케이스다 라는 경험과 느낌은 있지만, 이번에는 가중치가 동일하지 않은 상황에서, 특히 뒤로도 갈 수 있는 상황에서 이렇게 생각하고 넘어가기에는 찝찝함이 있어 질문해봅니다.
답변 2
0
안녕하세요 ㅎㅎ
visited[now] + 1이 visited[next]보다 작아서 새로운 경로가 더 빠를 수 있는 경우의 수는 신경을 안써도 되는 이유가 무엇인지 궁금합니다.
-> visited[now] + 1 < visited[next] 이런 경우의 수는 없냐 이거 말씀하시는거죠?
먼저 그 이전의 코드를 보시면 now, next에 대한 방문 배열이 만들어져있을 때 해당 if문으로 들어가게 됩니다. (즉, 방문배열이 이미 완성되어있는 상태입니다.)
if (0 <= next && next <= MAX) {
if (!visited[next]) {자 그러면 예를 들어볼게요.
예를 들어
a -> b -> c라는 경로에서 최단거리 배열을 만들면
1 -> 2 -> 3 이런 경로가 나오고
그 담에
a -> d -> c 이 때의
d 에서 c로 갈 때의 카운팅하는 상황을 찾는 코드입니다.
그렇다면, visited[now] + 1 < visited[next] 이런 경우의 수가 있을까요?
예를 들어.
a -> b -> c -> d
a -> b -> d 라고 할 때
d에는 3이 들어가 있고 c에서 d를 바라보았을 때 c는 3이고 d는 3입니다.
왜냐하면 BFS로 탐색하게 되면 먼저 a -> b -> d 순으로 최단거리가 먼저 쌓이게 때문입니다.
이 때 now가 c고 next가 d라고 했을 때
visited[now] + 1 < visited[next]를 보면
3 + 1 < 3
이렇게 되서 해당 부등호는 틀리게 됩니다.
따라서, 해당 경우의 수는 존재하지 않습니다.
또 질문 있으시면 언제든지 질문 부탁드립니다.
좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)
감사합니다.
강사 큰돌 올림.
0
안녕하세요, 인프런 AI 인턴입니다. kimmistral님의 질문에 대한 답변을 드리겠습니다.
우선 Breadth-First Search(BFS) 알고리즘의 특성에 대해 이해해야 합니다. BFS는 동일한 가중치를 가진 경우 즉, 각 이동마다 비용이 같은 경우 최단 경로를 찾는 데 유용하며, 각 노드를 한 번씩 방문하면 해당 노드까지의 최단 거리도 결정됩니다. 이는 큐(Queue)를 활용하여 레벨별로 탐색을 진행하기 때문입니다.
질문하신 부분은 최단거리를 효율적으로 추적하는 데 사용되는 패턴 중 하나입니다:
else if (visited[next] == visited[now] + 1)
BFS 특성과 동일 가중치: BFS는 모든 간선의 가중치가 동일하다는 전제 하에 최단 경로를 찾습니다. 즉, 각 단계의 이동은 동일한 시간(또는 거리) 단위로 이루어진다고 가정합니다. 그래서 visited 배열에 ‘가장 처음 방문했을 때의 거리’가 저장됩니다.
최단거리 보장: BFS의 첫 번째 방문이 최단거리인 이유는, 먼저 발견된 경로는 동일한 조건에서 다른 길과 비교할 때도 동일하게 최단거리가 보장된다는 것입니다. 다음 노드를 방문할 때, 만약 visited[next]가 지금까지 누적된 거리인 visited[now] + 1과 같다면, 이는 대체 경로로서 또 다른 최단 경로임을 의미합니다.
가중치가 상이한 경우: 만약 각 간선의 가중치가 다르다면 Dijkstra 알고리즘 같은 가중치가 있는 최단거리 알고리즘을 사용해야 맞습니다. BFS는 동일한 가중치를 가정합니다.
따라서 next가 이미 한 번 확인된 후, 다른 경로로의 방문에서 동일한 거리를 갖게 되었다면, 이는 순환적인 최단 경로 계산에서 중복적인 경로를 찾는 상황이며, 이는 다양한 경로 수를 고려할 때 유용합니다.
더욱 자세한 문제 해결을 원하실 경우 3-G 관련 유사 질문과 답변을 참고하시길 추천드립니다. 탐색 알고리즘의 이론적인 부분을 깊게 이해하면 더 명확해질 것입니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.