[Silver II] 트리의 부모 찾기 - 11725

문제 링크

성능 요약

메모리: 70676 KB, 시간: 1116 ms

분류

그래프 이론, 그래프 탐색, 트리, 너비 우선 탐색, 깊이 우선 탐색

제출 일자

2024년 7월 12일 21:30:13

문제 설명

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

입력

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

출력

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

풀이 (BFS)

DFS로 푸는 풀이가 궁금하다면 [DFS 풀이 블로그]를 참고하면 될 것 같다.

BFS로 푸는 풀이에 대해 알아보자.
먼저 문제 예시 1번의 트리 형태를 가져왔다.

위 형태에서 우리는 루트 노드를 기준으로 Level을 하나씩 높여가면서 탐색한다고 보면 된다.

루트 노드를 처음 Queue에 넣어주고, 노드와 인접한 4,6을 방문한다. 이때 4,6의 부모 노드는 1이라는 것을 인지해줘야 한다.

그리고 4,6이 각각 인접하는 노드로 내려간다. 위 설명과 같이 2,7은 부모 노드가 4고, 3의 경우엔 부모 노드가 6이 된다.

이런 식으로 레벨 단위로 인접하는 노드를 입력해주고 자식 노드를 통해 부모 노드를 찾아낸다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	//bfs 문제
	static boolean[] visited; //방문 여부 확인용
	static int[] parent; //부모 노드 배열
	static ArrayList<Integer>[] tree; //입력 받을 정점 배열
	static int N;
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		N = Integer.parseInt(br.readLine());
		
		tree = new ArrayList[N+1];
		for(int i=1; i<=N; i++) {
			tree[i] = new ArrayList<>();
		}
		visited = new boolean[N+1]; 
		parent = new int[N+1];
		
		for(int i=1; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			int one = Integer.parseInt(st.nextToken());
			int two = Integer.parseInt(st.nextToken());
			
			tree[one].add(two); //각각의 정점을 연결한다.
			tree[two].add(one);
		}
		bfs();
	}
	public static void bfs() {
		Queue<Integer> queue = new LinkedList<Integer>();
		queue.add(1);
		visited[1]=true;
		while(!queue.isEmpty()) {
			int v = queue.remove();
			for(int node : tree[v]) {
				if(visited[node]) {
					continue;
				}
				visited[node]=true;
				queue.add(node);
				parent[node]= v;
			}
		}
		for(int i=2; i<=N; i++) {
			System.out.println(parent[i]);
		}
	}
}