부모가 2개 이상일경우 질문

Question

3번 정점처럼 부모가 0이랑 1이 있을경우 최단거리는 0에서 1을 지나 3을 가는것이 최단거리인데 부모를 찾을때 0으로 찾게 되는데 부모를 vector> parent(6, vector(6, -1));처럼 사용해서 여러명의 부모를 찾는것이랑 영상처럼 하나의 부모를 찾는것이랑은 차이가 있나요? 그리고 최단거리의 부모를 찾는것은 큰 의미가 없을까요?

Rookiss · Answer

당연히 최단거리의 부모가 중요합니다. 처음 발견한 부모가 best case가 아니었다면, 뒤늦게 최단거리를 찾게 될 때 부모를 덮어쓰게(??) 됩니다.

communityai8509 · Answer

안녕하세요, 인프런 AI 인턴입니다. kamdabin3님이 올려주신 질문에 대해 답변드립니다. 질문의 핵심은 특정 노드(정점)의 다수의 부모가 있을 때, 최단 경로를 찾는 경우와 관련된 것입니다. 시작점을 중심으로 다익스트라(Dijkstra) 등의 알고리즘을 사용할 때, 최단 거리로 부모(이전 경로)를 기록하게 됩니다. 질문자님이 언급하신 대로 parent 배열을 사용하여 각 노드의 이전 노드를 저장하는 방법을 많이 사용합니다. 이때, 일반적으로 최단 거리를 구성하는 경로 중 하나만 선택하게 됩니다. 여러 부모를 기록하는 방법 vs. 하나의 부모를 기록하는 방법: 하나의 부모 : 대부분의 최단 거리 알고리즘은 경로의 효율성을 위해 하나의 최단 경로를 빠르게 저장합니다. 이렇게 하면 메모리나 계산이 단순해지고 시간 복잡도에 유리합니다. 여러 부모 기록 : 만약 여러 경로를 저장하고 싶다면, 말씀하신 것처럼 벡터 리스트를 사용하여 여러 부모를 저장할 수 있습니다. 하지만 이는 메모리 사용량을 증가시키고, 후속 계산이 조금 더 복잡해질 수 있다는 단점이 있습니다. 최단거리의 부모를 찾는 의미: 경로 추적 : 여러 경로가 있는 경우, 최단 거리를 이루는 특성 때문에 어떤 경로를 선택했는지 추적할 수 있습니다. 사용자 목적 : 만약 시스템에서 여러 경로가 허락된다면, 이 정보를 통해 대체 경로나 특정 조건에 맞춘 경로 선택이 가능해집니다. 관련해서 다익스트라 알고리즘이나 BFS를 이용한 경로를 다루는 게시글을 참고하시어 이해를 돕는 것이 좋을 것 같습니다. 제가 찾은 관련된 질문들은 다음과 같습니다: 최단거리 경우의수에 관하여 여기서는 BFS로 최단거리를 찾을 때의 다양한 경로에 관한 논의가 이루어졌습니다. 14분 30초 부근 질문 있습니다 이 질문은 경로 추적시에 객체 비교를 다루는 내용입니다. 저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다. 현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏 추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.