작성한 질문수 15

0

안녕하세요^^

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

0

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

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

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

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

2. 레벨 관점에서의 이해:

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

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

• 숙제 코드 리뷰 부탁드립니다.
  
• 숙제검사
  

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

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