[백준, 11725번] 트리의 부모 찾기 (DFS, 트리, Java)

문제설명

입력 & 출력

나의 풀이

문제 접근 방법

"백준 - 트리의 부모 찾기" 문제는 트리의 부모 노드를 찾는 문제입니다. 트리의 루트 노드는 항상 1이며, 루트 노드를 기준으로 2번 노드부터각 노드의 부모를 출력해야 합니다.

 

트리의 특징은 간선이  N-1개로 주어지며, 이는 사이클이 없고 모든 노드가 연결된 그래프를 뜻합니다.

하나의 그래프에서 루트를 기준으로 트리를 구성하는 방법은 여러 가지가 존재할 수 있습니다. 저는 문제를 이해하기 위해 다음과 같은 트리 형태를 그려보았습니다.

---

 

DFS 알고리즘을 사용하여 루트 1번부터 순회를 한다면, 1→6→3→5 순으로 내려가고, 다시 1로 돌아와서 4→2, 4→7 로 진행이 됩니다.

 

문제 접근

1. 트리 구성 : 연결정보는 방향성이 없이 주어지기 때문에 양방향 연결을 위한 ArrayList[]를 사용하여 각 노드의 연결 정보를 저장
2. DFS로 부모-자식 관계 파악: 루트(1번)부터 시작해서 연결된 노드를 자식으로 지정

알고리즘 동작

• DFS는 루트(1번)부터 시작하여:  1→6→3→5 순으로 깊이 우선 탐색
• 다시 1로 돌아와서 4→2, 4→7 순으로 진행
• 방문하지 않은 노드를 만나면 현재 노드를 그 노드의 부모로 지정

구현 순서

1. 트리 구성: 각 노드의 연결 정보 저장
2. DFS로 부모 지정: 연결된 미방문 노드 발견 시 부모로 지정
3. 결과 출력: 2번 노드부터 순서대로 부모 노드 출력

전체 코드

 

DFS 알고리즘을 알고있다면 어렵지 않게 풀이할 수 있습니다.

 

문제의 핵심은 트리를 구성하는 것인데, 방향성이 존재하지 않기때문에 양방향 연결을 위한 ArrayList를 사용해줍니다.

 

또한, 노드는 1부터이기 때문에 좀 더 직관적인 풀이를 위하여 1-based 로 설정해줍니다.

7
1 6
6 3
3 5
4 1
2 4
4 7

null
[6, 4]
[4]
[6, 5]
[1, 2, 7]
[3]
[1, 3]
[4]

 

리스트 배열에 양방향 연결을 해준다면, 위와 같이 각 인덱스에 연결된 노드들이 저장됩니다.

 

그리고, dfs함수를 호출하여 1번 노드(루트)부터 시작해 방문하지 않은 노드를 만나면 현재 노드를 그 노드의 부모로 지정하고 dfs()함수를 재귀적으로 호출하여 깊이 우선 탐색을 수행합니다. 최종적으로 다음과 같은 부모 노드 정보가 저장됩니다.

[0, 0, 4, 6, 1, 3, 1, 4]