[백준] 22856번 : 트리 순회 - 자바(Java)
Problem 🔒
문제
https://www.acmicpc.net/problem/22856
노드가 N개인 이진 트리가 있다. 트리를 중위 순회와 유사하게 순회하려고 한다. 이를 유사 중위 순회라고 하자.
순회의 시작은 트리의 루트이고 순회의 끝은 중위 순회할 때 마지막 노드이다. 이때 루트 노드는 항상 1번 노드이다.
유사 중위 순회는 루트 노드에서 시작하며, 다음과 같이 진행된다.
- 현재 위치한 노드의 왼쪽 자식 노드가 존재하고 아직 방문하지 않았다면, 왼쪽 자식 노드로 이동한다.
- 그렇지 않고 현재 위치한 노드의 오른쪽 자식 노드가 존재하고 아직 방문하지 않았다면, 오른쪽 자식 노드로 이동한다.
- 그렇지 않고 현재 노드가 유사 중위 순회의 끝이라면, 유사 중위 순회를 종료한다.
- 그렇지 않고 부모 노드가 존재한다면, 부모 노드로 이동한다.
- 유사 중위 순회를 종료할 때까지 1 ~ 4를 반복한다.
위 그림에 있는 트리에서 중위 순회를 한다면 4→2→5→1→6→3→7 순으로 순회를 한다.
따라서, 유사 중위 순회의 끝은 노드 7이 된다.
유사 중위 순회는 위 그림과 같이 루트인 노드 1에서 시작하여 노드 7에서 끝나고 1→2→4→2→5→2→1→3→6→3→7 이와 같은 순서로 순회를 진행한다. 유사 중위 순회를 진행하면서 총 10번 이동하였다.
여기서 이동이라는 것은 하나의 노드에서 다른 노드로 한번 움직이는 것을 의미한다. 예를 들면, 노드 1에서 노드 2로 가는 것을 한번 이동하였다고 한다.
유사 중위 순회를 하면서 이동한 횟수를 구하려고 한다.
입력
첫 번째 줄에 트리를 구성하는 노드의 개수 N이 주어진다.
두 번째 줄부터 N+1번째 줄까지 현재 노드 a, 현재 노드의 왼쪽 자식 노드 b, 현재 노드의 오른쪽 자식 노드 c가 공백으로 구분되어 주어진다. 만약 자식 노드의 번호가 -1인 경우 자식 노드가 없다는 것을 의미한다.
출력
유사 중위 순회를 하면서 이동한 총 횟수를 출력한다.
제한
- 1≤N≤100,000
- 1≤a,b≤N
예제 입력 1
7
1 2 3
2 4 5
3 6 7
4 -1 -1
5 -1 -1
6 -1 -1
7 -1 -1예제 출력 1
101→2→4→2→5→2→1→3→6→3→7
예제 입력 2
1
1 -1 -1예제 출력 2
0이진 트리란?🌲
각 노드가 자식 노드를 최대 2개까지만 가질 수 있는 트리이다.
- 포화 이진 트리
- 모든 레벨에 노드가 자식 노드 2개로 가득 차 있는 이진 트리를 말한다.
- 높이가 h일 때, $ (2^{h+1}-1)$개의 노드를 가진 이진 트리이다.
- 완전 이진 트리
- 노드의 왼쪽 자식부터 빈틈없이 채워진 이진 트리를 말한다.
- 편향 이진 트리
- 높이가 h일 때, 최소 개수의 노드를 가지면서 한쪽 방향의 자식 노드만을 가진 이진 트리를 말한다.
Approach 1 ⭕ - 중위 순회
첫 번째 방법은 중위 순회를 직접 돌려본 경우이다.
- 왼쪽 자식 노드 방문
- 왼쪽 자식이 있다면, 이동 횟수 cnt +1
- 자식 노드 방문(재귀)
- 다시 부모 노드로 돌아오는 이동 횟수 cnt +1
- 부모 노드 방문
- 왼쪽 자식 방문한 후, 부모 노드 방문 횟수 v +1
- 방문 횟수 v가 노드의 개수 N과 동일하다면, 모든 노드를 방문한 경우이므로 현재까지의 이동 횟수 cnt를 res에 저장한다.
- 오른쪽 자식 노드 방문
- 오른쪽 자식이 있다면, 이동 횟수 cnt +1
- 자식 노드 방문(재귀)
- 다시 부모 노드로 돌아오는 이동 횟수 cnt +1
- 리프 노드 방문
- 더이상 자식이 없다면 방문 횟수 v +1
- 방문 횟수 v가 노드의 개수 N과 동일하다면, 모든 노드를 방문한 경우이므로 현재까지의 이동 횟수 cnt를 res에 저장한다.
Approach 2 ⭕ - 수식 사용
- 총 이동 횟수는 간선 개수 * 2
- 간선 하나 당 이동 횟수가 2번이므로, 트리의 간선 개수 * 2가 총 이동 횟수이다.
- 유사 중위 순회의 총 이동 횟수 = 총 이동 횟수 - 오른쪽 자식 수
- 유사 중위 순회의 끝은 다시 루트 노드로 돌아오는 것이 아니다.
- 유사 중위 순회의 끝은 중위 순회할 때 마지막 노드이다.
- 따라서, 루트 노드에서 오른쪽 자식 노드만을 따라가면서 1씩 감소시켜야 한다.
- 문제의 예시로 보면, 10 = 6개(트리의 간선 개수) * 2 - 2개(오른쪽 자식 수 : 노드 3, 노드 7)이다.
Solution 💡
중위 순회
import java.util.ArrayList;
import java.util.Scanner;
public class 트리순회2 {
static int N, a, b, c, cnt=0, v=0, res=0;
static ArrayList<ArrayList<Integer>> list = new ArrayList<>();
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
for(int i=0; i<N+1; i++){list.add(new ArrayList<>());}
for(int i=0; i<N; i++){
a=sc.nextInt(); b=sc.nextInt(); c=sc.nextInt();
list.get(a).add(b);
list.get(a).add(c);
}
Inorder(1);
System.out.println(res);
}
public static void Inorder(int node){
int left = list.get(node).get(0);
int right = list.get(node).get(1);
if(left==-1 && right==-1){
v++;
if(v==N){res = cnt;}
return;
}
// 왼쪽 자식 노드 방문
if(left!=-1){
cnt++;
Inorder(left);
cnt++;
}
// 부모 노드 방문
v++;
if(v==N){res = cnt;} // 노드에 자식이 2개 아닌 경우
// 오른쪽 자식 노드 방문
if(right!=-1){
cnt++;
Inorder(right);
cnt++;
}
}
}
수식 활용
import java.util.ArrayList;
import java.util.Scanner;
public class 트리순회2 {
static int N, a, b, c, res=0, level=0;
static ArrayList<ArrayList<Integer>> list = new ArrayList<>();
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
for(int i=0; i<N+1; i++){list.add(new ArrayList<>());}
for(int i=0; i<N; i++){
a=sc.nextInt(); b=sc.nextInt(); c=sc.nextInt();
list.get(a).add(b);
list.get(a).add(c);
if(b!=-1) res+=2;
if(c!=-1) res+=2;
}
Left(1);
System.out.println(res-level);
}
public static void Left(int node){
int left = list.get(node).get(1);
if(left!=-1){level++; Left(left);}
}
}
불필요한 코드 삭제 ⚠️
- 중위 순회 시 방문 배열 삭제
- 중위 순회는 재귀적으로 왼쪽 자식 → 부모 → 오른쪽 자식 순서로 호출한다.
- 이진 트리에서 각 노드로의 경로는 유일하기 때문에, 이미 방문한 노드를 다시 방문하지 않는다. (순환 구조가 아님)