트리의 부모 찾기
1 초 | 256 MB | 31941 | 13730 | 10044 | 42.516% |
문제
루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.
출력
첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.
풀이
예제 풀이1: 1번 문제를 그림으로 표현하면 다음과 같습니다.
1번 노드는 트리의 루트이므로 2번 노드부터 출력합니다.
연결관계
루트가 1로 주어졌으므로 1과 연결된 숫자들은 모두 1보다 하위의 노드임을 알 수 있습니다.
어떻게 정보를 저장할까 생각해보면 2가지를 생각할 수 있습니다.
1) 이 숫자가 현재 몇 번째 상위 노드인지 기록하기
→ 1은 0, 1과 연결된 6과 4는 1...
2) 현재 노드의 상위 노드를 기록하기
→ 1과 연결된 6과 4의 상위 노드는 1이므로 1을 입력 → 반복
문제가 원하는 답을 내기에 2)가 더 적절해 보입니다.
풀이1: 메모리 초과 - 배열 사용 금지
배열 기록 + BFS/DFS + 상위 노드 기록
import java.util.*;
public class Main {
static boolean[][] tree;
static int[] check;
static int N;
static void bfs() {
Queue<Integer> queue = new LinkedList<Integer>();
queue.add(1);
while(!queue.isEmpty()) {
int now = queue.poll();
for(int i=2;i<=N;i++) {
if(tree[now][i] && check[i]==0) {
check[i]=now;
queue.add(i);
}
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
int T = N-1;
tree = new boolean[N+1][N+1];
check = new int[N+1];
while(T-->0) {
int start = sc.nextInt();
int last = sc.nextInt();
tree[start][last]=true;
tree[last][start]=true;
}
bfs();
for(int i=2;i<N+1;i++) {
System.out.println(check[i]);
}
}}
import java.util.*;
public class Main {
static boolean[][] tree;
static int[] check;
static int N;
static void dfs(int n) {
for(int i=2;i<=N;i++) {
if(tree[n][i] && check[i]==0) {
check[i]=n;
dfs(i);
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
int T = N-1;
tree = new boolean[N+1][N+1];
check = new int[N+1];
while(T-->0) {
int start = sc.nextInt();
int last = sc.nextInt();
tree[start][last]=true;
tree[last][start]=true;
}
dfs(1);
for(int i=2;i<N+1;i++) {
System.out.println(check[i]);
}
}}
* 노드의 개수가 많아지면서 메모리를 초과합니다.
풀이2: ArrayList 사용
배열은 빈 공간이 너무 많기 때문에 ArrayList 를 사용한다.
import java.util.*;
public class Main {
static ArrayList<Integer>[] tree;
static int[] check;
static int N;
static void dfs(int n, int parent) {
check[n]=parent;
for(int i=0;i<tree[n].size();i++) {
if(check[tree[n].get(i)]==0) {
dfs(tree[n].get(i),n);
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
int T = N-1;
tree = new ArrayList[N+1];
check = new int[N+1];
for(int i=0;i<N+1;i++) {
tree[i]=new ArrayList<Integer>();
}
while(T-->0) {
int start = sc.nextInt();
int last = sc.nextInt();
tree[start].add(last);
tree[last].add(start);
}
dfs(1,1);
for(int i=2;i<N+1;i++) {
System.out.println(check[i]);
}
}}
'Study > Baekjoon' 카테고리의 다른 글
[Java] Baekjoon5639: 이진 검색 트리 (0) | 2022.01.20 |
---|---|
Baekjoon1991: 트리 순회 (0) | 2022.01.19 |
Baekjoon1707: 이분 그래프 (0) | 2022.01.17 |
Baekjoon2206: 벽 부수고 이동하기 (0) | 2022.01.16 |
Baekjoon1697: 숨바꼭질 (0) | 2022.01.15 |