인프런 커뮤니티 질문&답변
작성한 질문수
연결되어 있고 아직 방문하지 않은 노드에 대한 방문 순서 관련
해결된 질문
작성
·
182
1
제가 경험이 부족해서 그런 것 같은데요, 이 문제는 'x < y'라는 조건이 없다면 DFS로 풀 수 있는 문제가 아닌 것 같다는 생각이 들었습니다.
https://www.acmicpc.net/problem/2644
에서 '입력' 파트를 보면, '번호 x는 뒤에 나오는 정수 y의 부모 번호를 나타낸다.'라고만 나와있습니다. 즉, 'x < y'라는 조건이 주어져 있지 않습니다. 부모 노드 번호가 자식 노드 번호보다 작다는 조건이 주어져 있지 않는 것입니다.
그래서 저는 이 문제가 DFS로 풀리는 문제가 아닐 것 같다고 생각했었습니다.
위 그림에서는 노드2의 부모가 1이지만, 2보다 값이 큰 3이 될 수도, 4가 될 수도 있을 것이라 생각했습니다. 따라서 노드2를 방문한 이후에, 노드2와 연결된 노드 중 아직 방문하지 않은 노드들 중 어떻게 부모 노드를 찾아야하지? '부모 노드 번호 < 자식 노드 번호'라는 조건이 없으면, 부모 노드를 찾을 수 없을 것 같은데?하는 생각이 들었습니다.
문제에서 x<y라는 조건이 없는 것 같은데, 어떻게 '나와 연결되어 있고 아직 방문하지 않은 노드 중 번호가 가장 작은 노드를 방문해야겠다'는 생각을 하신 것인지 궁금합니다..
답변 1
2
제가 질문의 요점을 잘못 잡은 걸 수도 있는데, 노드 번호가 커지거나 작아지는 것은 부모인지 아닌지의 여부와 큰 상관이 없을 것 같습니다!
예를 들어 예시에서 2번과 7번이 바뀌어있었다면 1 -> 7 -> 2 순서로 방문을 할 것이고, 그러면 7번의 부모는 1번이 되고, 2번의 부모는 7번이 되어서 부모의 번호가 더 커도 부모의 정보를 담는 것에는 문제가 없을 것 같아요. 이 문제의 핵심은 "start 사람과 end 사람 간의 거리가 얼마인지"를 계산하는 문제였기 때문에, 꼭 부모인지 자식인지를 알아야지만 풀 수 있었던 문제는 아니었어요.
다만 그 둘 간의 거리 (간선의 개수)가 얼마인지만 계산할 수 있으면 정답을 잘 구할 수 있었고, 그래서 별도의 x와 y 간의 조건은 제공되지 않은 것으로 이해됩니다!
혹시 제가 질문을 잘못 이해한 것이라면 다시 한번 설명해주세요~!
제가 잘못 생각했었어요,,
답변 주셔서 정말 감사합니다!