26441 (c++) DFS 2644번: 촌수계산 https://www.acmicpc.net/problem/2644 문제 개요 dfs(깊이 우선 탐색) 응용 문제 내 방식대로 풀었기에 다른 사람과 약간 다를 수 있다. 부모가 하나로 고정되어있는 트리 형태의 문제로, 주어진 두 사람에 대해서 촌수를 계산하면 된다. 아이디어는 아래와 같다. 기존 트리 구조처럼 위에서 아래로 내려오는 구조로 만들게 되면 입력에서 주어진 사람들 찾는데 어려움이 있다.그래서 반대로 자식을 트리의 윗부분으로 오게 하고, 아랫 부분에 부모 하나를 넣어두었다. 첫 번째 사람에 대해서 루트 노드까지 각 촌수를 저장하여 올라간다.여기서 부모 노드 중 두 번째 사람이 있다면 멈추고 정답을 출력한다. 두 번째 사람에 대해서 부모 노드로 올라가면서 똑같이 촌수를 저장하되,촌수가 이미 기.. 2025. 9. 12. 이전 1 다음