Study/Baekjoon

Baekjoon11725: 트리의 부모, 숏코딩

devyoseph 2022. 1. 18. 18:39

트리의 부모 찾기

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