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

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

문제

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

풀이/후기

ArrayList안에 ArrayList를 넣어서 풀이했다.

입력 받을 때 상위, 하위 노드에 대한 구분 없이 그냥 받는거라서

x.add(y), y.add(x)로 양쪽에 넣어두고 bfs를 이용해서 풀면 된다.

visited를 이용해 이미 탐색한 노드는 고려하지 않고,

parent에 현재 노드를 대입하면 부모 노드를 찾아낼 수 있다.

소스코드로 보는 것이 더 이해가 빠를 것 같다.

 

난 처음에 x.add(y)이렇게 한 방향으로만 넣어서 풀려다 실패했다(당연한 결과,,^^;)

코드

package GraphTheory;

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

public class Problem11725 {
	
	static int N;
	static ArrayList<Integer>[] arr;
	static Queue<Integer> q = new LinkedList<>();
	static boolean[] visited;
	static int[] parent;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer str;
		StringBuilder sb = new StringBuilder();
		
		N = Integer.parseInt(br.readLine());
		
		arr = new ArrayList[N+1];
		for (int i=1; i<N+1; i++) {
			arr[i] = new ArrayList<>();
		}
		
		visited = new boolean[N+1];
		parent = new int[N+1];
		
		for (int i=0; i<N-1; i++) {
			str = new StringTokenizer(br.readLine(), " ");
			int x = Integer.parseInt(str.nextToken());
			int y = Integer.parseInt(str.nextToken());
			arr[x].add(y);
			arr[y].add(x);
		}
		
		bfsFn(1);
		
		for (int i=2; i<N+1; i++) {
			sb.append(parent[i]).append("\n");
		}
		System.out.println(sb);
	}
	
	static void bfsFn(int x) {
		q.add(x);
		visited[x] = true;
		
		while(!q.isEmpty()) {
			int t = q.poll();
			
			for (int temp : arr[t]) {
				if (!visited[temp]) {
					parent[temp] = t;
					visited[temp] = true;
					q.add(temp);
				}
				
			}
		}
	}

}

Commit

https://github.com/allrightDJ0108/CodingTestStudy/commit/081be5fa0d3d8a579b76978fa70f5c6a4aaec6ec

참고