[백준] 트리의 부모 찾기(11725)

gaeunek·2021년 6월 9일
0

algorithm

목록 보기
11/20

문제

[백준] 트리의 부모 찾기

루트 없는 트리가 주어진다. 이때, 트리의 루트를 1이라고 정했을 때, 각 노드의 부모를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 노드의 개수 N (2 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 트리 상에서 연결된 두 정점이 주어진다.

출력

첫째 줄부터 N-1개의 줄에 각 노드의 부모 노드 번호를 2번 노드부터 순서대로 출력한다.

해설

DFS와 BFS 두 가지로 풀이해보았고, 앞으로의 응용문제들을 위한 기초문제라고 느껴졌다.

메모리는 BFS < DFS, 시간은 BFS > DFS.

풀이

DFS

import java.util.*;
import java.io.*;

public class Main {
	static int N;
	static int[] parent;
	static boolean[] visited;
	static ArrayList<Integer>[] graph;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		N = Integer.parseInt(br.readLine());
	
		parent = new int[N+1];
		visited = new boolean[N+1];
		graph = new ArrayList[N+1];
		
		for (int i = 0; i <= N; i++) {
			graph[i] = new ArrayList<>();
		}
		
		for (int i = 0; i < N-1; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			
			int v = Integer.parseInt(st.nextToken());
			int u = Integer.parseInt(st.nextToken());
			
			graph[v].add(u);
			graph[u].add(v);
		}
		
		visited[1] = true;
		
		dfs(1);
		
		StringBuilder sb = new StringBuilder();
		
		for(int i = 2; i <= N; i++) {
			sb.append(parent[i]).append("\n");
		}
		
		System.out.println(sb.toString());
	}
	
	public static void dfs(int u) {
		for(int v : graph[u]) {
			if(!visited[v]) {
				parent[v] = u;
				visited[v] = true;
				dfs(v);
			}
		}
	}
}

BFS

import java.util.*;
import java.io.*;

public class Main {
	static int N;
	static ArrayList<Integer>[] graph;
	static Queue<Integer> queue;
	static boolean[] visited;
	static int[] parent;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		N = Integer.parseInt(br.readLine());

		graph = new ArrayList[N + 1];
		queue = new LinkedList<>();
		visited = new boolean[N + 1];
		parent = new int[N + 1];
		
		for (int i = 0; i <= N; i++) {
			graph[i] = new ArrayList<>();
		}

		for (int i = 0; i < N - 1; i++) {
			st = new StringTokenizer(br.readLine(), " ");

			int v = Integer.parseInt(st.nextToken());
			int u = Integer.parseInt(st.nextToken());

			graph[v].add(u);
			graph[u].add(v);
		}

		queue.add(1);

		while (!queue.isEmpty()) {
			int u = queue.poll();

			for (int v : graph[u]) {
				if (!visited[v]) {
					visited[v] = true;
					parent[v] = u;
					queue.add(v);
				}
			}
		}
		
		StringBuilder sb = new StringBuilder();
		
		for(int i = 2; i <= N; i++) {
			sb.append(parent[i]).append("\n");
		}
		
		System.out.println(sb.toString());
	}
}
profile
능력있는 개발자를 꿈꾸는 작은아이

0개의 댓글