인프런 영문 브랜드 로고
인프런 영문 브랜드 로고

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

rlgus4531님의 프로필 이미지

작성한 질문수

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

14. 그래프 최단거리(BFS)

그래프 최단거리(BFS) 질문이 있습니다.

작성

·

49

0

두 번째로 푸는 방법에서 이해가 확실히 가지 않는 부분이 있습니다.

정점을 방문할 때 ch[] 배열에 방문했다 표시를 하고 dis[] 배열에 값을 집어넣는다는 건 지금 이 정점을 방문했다는 건 무조건 최단거리이다라고 확신하고 넣는거라고 이해했는데 왜 그렇게 되는지 이해가 잘 가지 않습니다.

처음 설명으로 이해하자면 레벨 관점에서 이미 전 레벨에서 해당 정점을 방문 했기 때문에(ex. 4번 정점을 방문했는데 지금이 2레벨이고 전 레벨인 1에서 4를 방문했을 때 ch[] 배열에 체크돼있음)라고 생각하면 되는걸까요?

답변 2

0

김태원님의 프로필 이미지
김태원
지식공유자

안녕하세요^^

두 번째 방법도 큐를 이용해 레벨탐색으로 최단거리를 찾는 논리로 첫 번째와 동일합니다. 다만 최단 거리를 배열에다 저장해 놓는 것 뿐입니다.

0

인프런 AI 인턴님의 프로필 이미지

안녕하세요, 인프런 AI 인턴입니다.

그래프 최단거리(BFS)에 대한 질문을 주셨군요. BFS는 특정 시작점에서 다른 모든 노드까지의 최단 거리를 구하는 데 매우 유용한 알고리즘입니다. 여기서는 큐(Queue)의 동작 원리를 이해하는 것이 중요합니다. BFS는 너비 우선 탐색으로, 레벨별로 그래프를 탐색하는 방식입니다.

  1. 왜 방문 표시와 동시에 최단거리임을 확신할 수 있는가?

    • BFS의 본질적인 특성 덕분에 가능합니다. 큐를 이용해 각 노드를 레벨별로 탐색하게 되는데, 이 말은 바로 다음 레벨의 노드를 방문하기 전에 현재 레벨의 모든 노드를 방문한다는 것을 의미합니다. 따라서 한 번 방문한 노드는 그 시점에서의 최단 거리로 확신할 수 있습니다. 이후에 방문하게 될 동일한 노드는 현재보다 더 길어진 경로를 통해서만 방문할 수 있게 되어 있기 때문입니다.
  2. 레벨 관점에서의 이해:

    • 각 레벨에서 방문하는 모든 정점은 해당 레벨에 도달하기까지의 최단 거리에 있는 정점들입니다. 따라서 현재 레벨에서 어떤 정점을 방문하지 않았다면, 이는 아직 갈 수 있는 다른 최단 경로가 존재하지 않는다는 것을 의미합니다. 이전 레벨에서 해당 정점을 방문했다면(정점 방문 시 ch[] 배열에 방문 표시를 남기는 이유), 이미 가장 빠른 길을 통해 도달했기 때문입니다.

관련 질문과 답변이 있습니다. 아래 링크를 통해 확인해 보세요:

이해를 돕기 위해 질문하신 내용에 비슷한 상황과 해결 방법을 설명한 댓글들을 참고하면 도움이 될 것입니다.

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