[백준/자바] 11725번: 트리의 부모 찾기

문제

https://www.acmicpc.net/problem/11725

풀이

• 루트 없는 트리
• 트리의 루트를 1이라 가정했을 때 각 노드의 부모 출력

부모를 찾는 가장 간단한 그래프 탐색 문제입니다.
BFS와 DFS를 사용해 풀 수 있는데, 저는 BFS를 사용해 문제를 풀었습니다.

		graph = new ArrayList<>();
		for (int i = 0; i <= n; i++) graph.add(new ArrayList<>());

		for (int i = 1; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			graph.get(a).add(b);
			graph.get(b).add(a);
  		}

• 인접 리스트를 사용했습니다.

	private static void bfs() {
		Queue<Integer> queue = new ArrayDeque<>();
		queue.add(1); // 루트를 1번이라 가정하고 탐색
		
		while (!queue.isEmpty()) {
			int cur = queue.poll();
			
			for (int nxt : graph.get(cur)) { // 인접한 노드 탐색
				if (visited[nxt] != 0) continue; // 이미 부모를 찾았다면 탐색을 진행하지 않음
				
				queue.add(nxt); // 다음 노드 탐색을 위해 큐에 추가
				visited[nxt] = cur; // 부모 처리
			}
		}
	}

• 인접한 노드를 탐색해서 이동이 가능하다면, 현재 노드가 인접한 노드의 부모임을 알 수 있습니다.

코드

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

public class Main {
	static int n;
	static int[] visited;
	static List<ArrayList<Integer>> graph;
	static StringBuilder sb = new StringBuilder();
	
	private static void bfs() {
		Queue<Integer> queue = new ArrayDeque<>();
		queue.add(1);
		
		while (!queue.isEmpty()) {
			int cur = queue.poll();
			
			for (int nxt : graph.get(cur)) {
				if (visited[nxt] != 0) continue;
				
				queue.add(nxt);
				visited[nxt] = cur;
			}
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		
		graph = new ArrayList<>();
		for (int i = 0; i <= n; i++) graph.add(new ArrayList<>());

		for (int i = 1; i < n; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			graph.get(a).add(b);
			graph.get(b).add(a);
  		}
		
		visited = new int[n+1];
		bfs();
		
		for (int i = 2; i <= n; i++) {
			sb.append(visited[i]).append('\n');
		}
		System.out.println(sb.toString());
	}

}