인프런 커뮤니티 질문&답변
작성한 질문수
3-B 2589 왜틀렸는지 모르겠습니다.
작성
·
10
0
반복문을 통해서 해당 지역을 방문하지 않았으면 BFS를 실행
BFS를 통해 해당 노드와 가장 멀리 떨어진 노드위치를 가져온다.
가장 멀리 떨어진 노드 기준으로 다시 BFS 수행
그러면 해당 그래프에서 가장 멀리 떨어진 두 지점을 구할수 있게 코드를 작성했습니다.
외부에서 중복 방문을 막기위해 visited 변수를 BFS에서 해당 노드들을 순회할때 ture로 설정해 외부 에서 접근하지 못하게 막고
내부에서는 cost를 통해 중복방문을 막도록 설계했습니다.
가장 멀리 떨어진 두 지점을 구하는 로직을 푸는 DFS,BFS문제를 푼 기억이 있어 그걸 토대로 여기다가 응용을 했는데 막상 제출하니까 틀리네요.
답변 1
0
안녕하세요, 인프런 AI 인턴입니다. 카카누님.
질문해주신 문제는 BFS/DFS 알고리즘을 이용하여 그래프 내에서 가장 멀리 있는 두 지점을 찾는 문제로 보입니다. 이 문제에서는 주로 “최장 거리”에 관한 로직을 처리하는 데 오류가 있어 틀린 결과가 나올 수 있습니다. 이를 해결하기 위해 몇 가지 검토할 부분을 알려드리겠습니다.
올바른 초기화 및 방문 처리: BFS/DFS를 통해 방문하는 노드에 대한 방문 처리, 즉
visited배열의 설정과 초기화가 올바르게 이루어졌는지 확인해보세요.최장 거리 계산 과정: BFS는 너비 우선 탐색으로, 최종 목적지에 도달했을 때의 거리 정보를 올바르게 업데이트하고 있는지 확인할 필요가 있습니다. 가장 멀리 떨어진 노드까지의 길이를 추적하고 있으신지 확인해주세요.
최장 경로의 시작점 설정: 문제에서 요구하는 최장 경로의 시작과 끝점을 제대로 설정하고 이동 경로를 기록하는지 살펴보세요. 최장 경로를 구하는 과정에서 두 번의 BFS를 수행하며, 두 번째 BFS는 첫 번째 BFS에서 얻은 가장 먼 노드부터 시작해야 합니다.
관련 질문 및 답변을 참고하실 수 있는 링크는 아래와 같습니다:
- 3-B BFS 기반 최장 경로 탐색 문제: BFS를 기반으로 최장 경로 탐색 문제를 해결한 다른 유사 질문입니다. BFS를 활용한 방법이 자세히 설명되어 있습니다.
코드 자체의 문제점이나 로직의 오류를 보다 세부적으로 분석하기 위해서는 작성하신 코드 자체를 자세히 검토하는 것이 가장 좋습니다. 이와 관련하여 위의 참고 자료 등을 활용해보시면 도움이 될 것입니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.