[백준(Baekjoon)][자바(java)] 11725 : 트리의 부모 찾기 / 트리

 

www.acmicpc.net/problem/11725

11725번: 트리의 부모 찾기

 

문제 풀이

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
import java.util.StringTokenizer;

public class Main {	 // 부모 노드 체크 - 인접 리스트

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader( new InputStreamReader(System.in) );
		int n = Integer.parseInt( br.readLine() ), v1, v2, i;  // num, vertex1, vertex2
		List<List<Integer>> e = new ArrayList<>();  // edge
		for( i = 0; i < n; i++ )
			e.add( new ArrayList<>() );
		StringTokenizer st;
		for( i = 0; i < n-1; i++ ) {
			st = new StringTokenizer( br.readLine() );
			v1 = Integer.parseInt( st.nextToken() ) - 1;
			v2 = Integer.parseInt( st.nextToken() ) - 1;
			e.get( v1 ).add( v2 );
			e.get( v2 ).add( v1 );
		}
		br.close();
		
		int a[] = new int[n], p;  // answer ( i : child node, a[i] : parent Node )
		boolean v[] = new boolean[n];  // visited
		Deque<Integer> q = new ArrayDeque<>();  // BFS
		v[0] = true;
		q.add( 0 );
		while( !q.isEmpty() ) {
			p = q.remove();				 // parent
			for( int c : e.get( p ) ) {	 // child
				if( !v[c] ) {
					a[c] = p;
					v[c] = true;
					q.add( c );
				}
			}
		}
		
		StringBuilder sb = new StringBuilder();
		for( i = 1; i < n; i++ )
			sb.append( ( a[i] + 1 ) + "\n" );
		System.out.println( sb.toString() );
		
	}
}

 

*  BFS

-  인접 리스트  ( 인접 행렬은 메모리 초과 )
-  노드 번호 입력 시 1씩 뺌  ( 루트 노드 번호는 0 )
-  트리는 무방향 그래프이므로 간선(edge) 연결 시 v1->v2, v2->v1 양방향으로 연결
-  a[]에 child node에 대한 parent node 번호를 담음
-  큐로 트리를 탐색하며 방문하지 않은 노드에 대해 a[c] = p
-  i(1<=i<n)번 노드부터 차례대로 a[i]의 값을 출력