트리
- 계층적인 자료구조
- 그래프의 일종
- 사이클이 비순환적 구조이다.
- 최상위 노드를 루트로가 한다.
노드
- 트리를 구성하는 각각의 요소
루트
- 트리의 최상위 노드
부모 노드
- 어떤 노드의 바로 위 노드
자식 노드
- 어떤 노드의 바로 아래 노드
리프
- 자식 노드가 없는 노드
서브 트리
- 트리내 특정노드를 루트로 하는 트리
레벨
- Level 1으로 하였을 때, 각 노드의 깊이
[11725] 트리의 부모 찾기
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
| 1 초 | 256 MB | 99818 | 45469 | 31882 | 43.170% |
문제
루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.
출력
첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.
문제풀이
이 문제는 그래프의 일종인 트리 구조에 대한 문제이다.
계층적 자료구조인 트리는 부모 노드와 자식 노드로 이루어져 있다.
예제 입력1를 시각화 해보자.
- Level 1으로 하였을 때, 각 노드의 깊이
[11725] 트리의 부모 찾기
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
| 1 초 | 256 MB | 99818 | 45469 | 31882 | 43.170% |
문제
루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.
출력
첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.
문제풀이
이 문제는 그래프의 일종인 트리 구조에 대한 문제이다.
계층적 자료구조인 트리는 부모 노드와 자식 노드로 이루어져 있다.
예제 입력1를 시각화 해보자.
예를 들어 위와 같은 이진 트리가 입력되면,
- 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)
- 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)
- 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)
가 된다.
입력
첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파벳 대문자로 매겨지며, 항상 A가 루트 노드가 된다. 자식 노드가 없는 경우에는 .으로 표현한다.
출력
첫째 줄에 전위 순회, 둘째 줄에 중위 순회, 셋째 줄에 후위 순회한 결과를 출력한다. 각 줄에 N개의 알파벳을 공백 없이 출력하면 된다.
문제풀이
이 문제는 그래프 구조 중 하나인 트리 형태로 입력을 받아 출력을 할 때 전위, 중위, 후위 순회 방식으로 출력해야 하는 문제이다.
전위 순회하는 경우 루트 → 왼쪽 자식 → 오른쪽 자식을 출력하면 된다.
만약 자식 아래 자식이 있다면 왼쪽 자식 부터 출력하면된다.
Node 클래스 생성
일단 트리 구조로 저장할 수 있게 Node 클래스를 만들고 안에 value, left, right 프로퍼티들을 선언하였다.
class Node {
char value;
Node left;
Node right;
Node(char value) {
this.value = value;
this.left = null;
this.right = null;
}
}
입력 받기
‘.’을 입력 받으면 값이 없는 경우이다. 문장을 char 배열로 변경한다면 0, 2, 4번째에 char값이 들어간다.
nodes 변수를 Map 타입으로 선언하는데 키는 Character이고 value는 Node가 된다.
String 형태인 input을 입력 받아 각각의 char을 parent, left, right에 저장해주자.
static Map<Character, Node> nodes = new HashMap<>();
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
sc.nextLine();
for(int i = 0; i < n; i++) {
String input = sc.nextLine();
char parent = input.charAt(0);
char left = input.charAt(2);
char right = input.charAt(4);
parentNode에 값 넣기
이제 부모 노드의 값과 왼쪽 자식 노드, 오른쪽 자식 노드를 넣어 주자.
만약 ‘.’이라면 값을 넣어주지 말자.
for(int i = 0; i < n; i++) {
String input = sc.nextLine();
char parent = input.charAt(0);
char left = input.charAt(2);
char right = input.charAt(4);
nodes.putIfAbsent(parent, new Node(parent));
Node parentNode = nodes.get(parent);
if (left != '.') {
nodes.putIfAbsent(left, new Node(left));
parentNode.left = nodes.get(left);
}
if (right != '.') {
nodes.putIfAbsent(right, new Node(right));
parentNode.right = nodes.get(right);
}
}
[15681] 트리와 쿼리
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
| 1 초 | 128 MB | 18882 | 8985 | 6792 | 45.337% |
문제
간선에 가중치와 방향성이 없는 임의의 루트 있는 트리가 주어졌을 때, 아래의 쿼리에 답해보도록 하자.
- 정점 U를 루트로 하는 서브트리에 속한 정점의 수를 출력한다.
만약 이 문제를 해결하는 데에 어려움이 있다면, 하단의 힌트에 첨부한 문서를 참고하자.
입력
트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105)
이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V)
이는 U와 V를 양 끝점으로 하는 간선이 트리에 속함을 의미한다.
이어 Q줄에 걸쳐, 문제에 설명한 U가 하나씩 주어진다. (1 ≤ U ≤ N)
입력으로 주어지는 트리는 항상 올바른 트리임이 보장된다.
출력
Q줄에 걸쳐 각 쿼리의 답을 정수 하나로 출력한다.
문제 풀이
이 문제는 특정 정점 U를 루트로 하는 서브트리에 속한 정점의 수를 출력하는 쿼리를 답하는 문제이다.
조건으로 주어진 트리는 항상 올바른 트리임이 보장된다.
자신의 자식들(서브 트리)에 대한 정점의 수를 구해야 하는 문제이다.
필요한 변수 선언 및 입력 받기
그래프 자료구조의 일종인 tree를 사용하기 위해 선언 하자.
중복 계산을 방지하기 위해 check를 선언 하자.
출력값인 자신의 자식들(서브트리)에 속한 정점의 수 sum을 선언해주자.
static List<Integer>[] tree;
static boolean[] check;
static int[] sum;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), r = sc.nextInt(), q = sc.nextInt();
check = new boolean[n + 1];
sum = new int [n+1];
tree = new ArrayList[n+1];
for (int i = 0; i < tree.length; i++) {
tree[i] = new ArrayList<>();
}
트리 자료구조를 생성하자.
입력 받은 u, v 와 값을 간선을 그려주자.
for (int i = 0; i < n-1; i++) {
int u = sc.nextInt(), v = sc.nextInt();
tree[u].add(v);
tree[v].add(u);
}
서브트리의 노드 수를 구하자.
중복 계산을 방지하기 위해 함수에 들어오면 check값을 true로 변경해주자.
그리고 자식이 있다면 1를 추가해주자.
재귀하며 자식이 있다면 계속 1를 더해주자. 그러면 어떤 노드의 서브트리의 수를 찾을 수 있다.
public static int getSum(int node) {
check[node] = true;
int result = 1;
for(int child: tree[node]) {
if(!check[child]) {
result += getSum(child);
}
}
return sum[node] = result;
}
전체 코드
이 알고리즘의 시간 복잡도는 O(n)이다.
import java.util.*;
class Main {
static List<Integer>[] tree;
static boolean[] check;
static int[] sum;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), r = sc.nextInt(), q = sc.nextInt();
check = new boolean[n + 1];
sum = new int [n+1];
tree = new ArrayList[n+1];
for (int i = 0; i < tree.length; i++) {
tree[i] = new ArrayList<>();
}
for (int i = 0; i < n-1; i++) {
int u = sc.nextInt(), v = sc.nextInt();
tree[u].add(v);
tree[v].add(u);
}
sum[r] = getSum(r);
for (int i = 0; i<q; i++) {
int u = sc.nextInt();
System.out.println(sum[u]);
}
}
public static int getSum(int node) {
check[node] = true;
int result = 1;
for(int child: tree[node]) {
if(!check[child]) {
result += getSum(child);
}
}
return sum[node] = result;
}
}
'알고리즘 > Recursion' 카테고리의 다른 글
| [코딩테스트] [1759] 암호 만들기 & [10971] 외판원 순회 2 & [14888] 연산자 끼워넣기 (2) | 2025.02.19 |
|---|---|
| [코딩테스트] [1182] 부분수열의 합 & [2758] 로또 & [1208] 부분 수열의 합2 (0) | 2025.02.12 |
| [코딩테스트] [14267] 회사 문화 1 & [1068] 트리 & [5639] 이진 검색 트리 (0) | 2025.02.12 |
| [코딩테스트] 재귀함수 & [15654~15657] N과M (1) | 2025.02.07 |