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

문제

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

입력

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

출력

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

---

테스트 케이스

 

입력 1

7
1 6
6 3
3 5
4 1
2 4
4 7

출력 1

4
6
1
3
1
4

 

입력 2

12
1 2
1 3
2 4
3 5
3 6
4 7
4 8
5 9
5 10
6 11
6 12

출력 2

1
1
2
3
3
4
4
5
5
6
6

 

입력 3

5
1 4
2 3
4 5
1 2

출력 3

1

2

1

4

 

 

---

접근

1. n을 입력 받음

2. n만큼 관계를 입력 받음

3.dfs를 이용해서 1부터 입력받은 관계들을 이용해 부모 자식관계를 설정합니다.

4. 부모 배열을 출력해줍니다.

 

3번 과정을 더 자세히 설명하자면,

노드 1부터 시작해서, 1과 연결된 노드들을 사용합니다.

예를 들어 1에 4,6이 연결되어 있다면 부모 배열[4]과 부모 배열[6]을 1로 설정하는 것입니다.(4번 노드와 6번 노드의 부모가 1이라는 뜻의 데이터)

그리고 다시 dfs(4), dfs(6)을 호출하는 방식으로 작동합니다.

이러면 1 3, 3 1 같이 관계가 중복되는 경우가 생기는데, 이는 visit배열을 이용해서 방문하지 않은 곳만 부모 배열 값을 바꿀 수 있게 허용하면 됩니다.

---

코드

 

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

class Main {
	
	static int n;
	static ArrayList<Integer>[] list;
	static int parent[];
	static boolean visit[];
	
	static void dfs(int start) {
		visit[start] = true;
		
		for(int i=0; i<list[start].size(); i++) {
			int temp = list[start].get(i);
			//방문 안했으면 부모로 지정.
			if(visit[temp] == false) {
				parent[temp] = start;
				dfs(temp);
			}
		}
	}
    public static void main(String args[]) throws IOException {
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    	
    	n = Integer.parseInt(br.readLine());
    	list = new ArrayList[n+1];
    	visit = new boolean[n+1];
    	parent = new int[n+1];
    	for(int i=1; i<=n; i++) {
    		list[i] = new ArrayList<>();
    	}
    	for(int i=0; i<n-1; i++) {
    		StringTokenizer st = new StringTokenizer(br.readLine());
    		int temp1 = Integer.parseInt(st.nextToken());
    		int temp2 = Integer.parseInt(st.nextToken());
    		list[temp1].add(temp2);
    		list[temp2].add(temp1);
    	}
    	dfs(1);
    	for(int i=2; i<=n; i++) {
    		bw.write(String.valueOf(parent[i]+"\n"));
    	}
    	br.close();
    	bw.flush();
    	bw.close();
    }
}

---

주의

x