11725 트리의 부모 찾기 (자바)

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


public class Main {
	
	static boolean check [];
	static int parents []; 
	static ArrayList<ArrayList<Integer>> list;
    public static void main(String args[]) throws IOException{
    
 
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		check = new boolean [N+1];
		parents = new int[N+1];		
		list = new ArrayList<ArrayList<Integer>>();
		
		for(int i = 0; i<=N; i++) {
			list.add(new ArrayList<Integer>());
		}
		
		int M = N;
		
		while(M-->1) {
		
			StringTokenizer st = new StringTokenizer(br.readLine(), " " );
		
			int one =  Integer.parseInt(st.nextToken());
			int two =  Integer.parseInt(st.nextToken());
		
			list.get(one).add(two);
			list.get(two).add(one);
		
		}
		
		dfs(1);
		
		for(int i = 2; i<=N; i++) {
			System.out.println(parents[i]);
			
		}	
    }
    
    public static void dfs(int a) {
    	
    	if(check[a]) {
    		return;
    	}
    	
    	check[a] = true;
    	
    	for(int b : list.get(a)) {
    		if(!check[b]) {
    			parents[b] = a;
    			dfs(b);
    		}
    	}
    }
}

 

 

# 트리

 

트리 구조를 만들 때,

리스트<리스트> 형식을 사용했다.

 

예시에 나온 값으로

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

 

 

만들어진 트리 구조를 보면,

위와 같은 구조인데, 실제로 이클립스에서 

예시로 주어진 

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

이 값들로 리스트 형식 트리(list)를 만들면

 

	while(M-->1) {
		
			StringTokenizer st = new StringTokenizer(br.readLine(), " " );
		
			int one =  Integer.parseInt(st.nextToken());
			int two =  Integer.parseInt(st.nextToken());
		
			list.get(one).add(two);
			list.get(two).add(one);
		
		}

이런 식으로

앞의 값 1은 one 으로, 뒤의 값 6은 two 로 받아서 

리스트 형식의 트리 구조에 잘 넣어줘서 완성했다.

 

리스트 형식으로 만든 트리(list)를 찍어보면

 

 

이런 형식으로 나온다.

 

즉, 트리의 인덱스 0 에는 아무 값도 넣지 않는 것으로 하고,

 

예시에 이렇게 나온 것처럼 

트리 노드 1은 노드 4,6 과 연결되고,

노드 2는 4와

노드 3은 6,5 와 연결됨을 알 수 있다.

 

#dfs

 

1) dfs 메서드 설명

dfs 코드를 살펴보면 아래와 같다.

 

    public static void dfs(int a) {
    	
    	if(check[a]) {
    		return;
    	}
    	
    	check[a] = true;
    	
    	for(int b : list.get(a)) {
    		if(!check[b]) {
    			parents[b] = a;
    			dfs(b);
    		}
    	}
    }

main 메서드에서 dfs(1) 을 실행하도록 했는데,

dfs 메서드 내의

 

    	for(int b : list.get(a)) {
    		if(!check[b]) {
    			parents[b] = a;
    			dfs(b);
    		}
    	}

이 코드를 통해서,

1의 자식 노드인 4,6 에 대해서

parents 배열의 값을 1로 만들었다.

 

즉, parents[4] = parents[6] = 1 이다.

 

그런 다음,

dfs(b) 를 재귀적으로 실행하도록 하여

4와 6의 자식 노드에 대해서도 dfs 를 진행하면서

parents 배열에 값을 채워넣었다.

 

그리고 boolean 형 check 배열을 만들어서 한 번 지나온 노드들은 true 표시해서

parents 배열에 값이 한 번 채워지고 난 다음에는 반복적으로 값을 채워 넣지 않도록 했다.

 

 

2) dfs 메서드 진행 순서

 

dfs 메서드 바로 아래, a 값을 찍어보도록 코드를 만들었다.

 

   public static void dfs(int a) {
    	
    	System.out.println("순서 : "+ a);

그랬더니 그 결과로

 

이렇게 나왔다.

즉, 1 6 3 5 4 2 7 순서로 dfs가 이뤄졌음을 알 수 있다.

 

 

이 그림에서 알 수 있듯이

맨 위의 노드 1에서부터 시작해서 오른쪽의 노드 6으로 가서 맨 아래 5까지 갔다가

다시 올라온 뒤 왼쪽 4, 또 왼쪽 2, 오른쪽 7로 이동하면서 진행된 것이다.

 

# 주의점

꼭 알아야 할 부분이 있다.

코드에서 보면 

 

		int M = N;
		
		while(M-->1)

이 부분이 있다.

이때, N 은 7이였고, M 역시 처음에는 7이 된다.

그런데 while 문을 M --> 1 조건으로 다 돌고 나면 M 은 0이 된다.

 

이것을 꼭 주의하자!

 

참고 자료 :  

https://log-laboratory.tistory.com/65

[백준] 11725번 트리의 부모노드 찾기