[문제] 백준 11725번 트리의 부모 찾기

www.acmicpc.net/problem/11725

11725번: 트리의 부모 찾기

 

 

풀이

 

1. BFS

public class BOJ_11725 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int N = Integer.parseInt(in.readLine());
		
        // 인접리스트 만들기
		ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
		int [] parents = new int[N+1];	//i번째 노드의  부모노드를 담는 배열
		parents[1] = 1;	//root
		
		for(int i=0;i<=N+1;i++) {
			list.add(new ArrayList<Integer>());	//init
		}
		//노드 간 연결
		for(int i=1;i<N;i++) {
			st = new StringTokenizer(in.readLine(), " ");
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			list.get(a).add(b);
			list.get(b).add(a);
		}
		
		//bfs
		LinkedList<Integer> queue = new LinkedList<>();
		queue.offer(1);
		
		while(!queue.isEmpty()) {
			int parent = queue.poll();
			
			for(int item:list.get(parent)) {	// parent의 자식들
				if(parents[item] == 0) {
					parents[item] = parent;
					queue.offer(item);
				}
			}
		}
		//2번붜 N번까지 노드의 부모노드 출력
		for(int i=2;i<=N;i++) {
			System.out.println(parents[i]);
		}
	}
}

2. DFS

public class BOJ_11725_2 {
	static int N;
	static ArrayList<Integer>[] list;
	static boolean[] visited;
	static int [] parents;
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		N = Integer.parseInt(in.readLine());
		
		// init
		list = new ArrayList[N+1];
		for(int i=1;i<=N;i++) {
			list[i] = new ArrayList<>();
		}
		visited = new boolean[N+1];
		parents = new int[N+1];	//i번째 노드의  부모노드를 담는 배열
		parents[1] = 1;	//root
	
		//노드 간 연결
		for(int i=1;i<N;i++) {
			st = new StringTokenizer(in.readLine(), " ");
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			list[a].add(b);
			list[b].add(a);
		}
		
		dfs(1);
		for(int i=2;i<=N;i++) {
			System.out.println(parents[i]);
		}
	}
	
	static void dfs(int v) {
		visited[v] = true;	// v번째 노드 방문
		
		for(int i: list[v]) {	// v번째 노드의 자식에 대하여
			if(!visited[i]) {
				parents[i] = v;	// 자식의 부모 노드 설정
				dfs(i);	//i번째 노드의 자식노드 찾기
			}
		}
	}
	
	

}