[백준] 2250 트리의 높이와 너비 - Tree(트리) + DFS(깊이우선탐색) JAVA

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

2250번: 트리의 높이와 너비

코드설명

Tree(트리) + DFS(깊이우선탐색) 을 활용하는 문제입니다.

 

문제에서 유의해야할점은 다음과 같습니다.

1. 트리의 루트노드는 항상 1이 아니다. 그러므로 Node에 parent 필드를 넣어서 갱신했을때 parent값이 여전히 -1 이라면 그 값은 최상단 노드이므로 root로 선정한다.

2. 트리의 열의 위치는 중위순회(inOrder)로 알 수 있다. 

 

위의 2가지만 유의하면 풀어낼 수 있습니다.

 

문제 로직에 대해 더 설명해보면,

1. 입력 처리:
   
   • 각 노드의 정보를 담을 Node 클래스를 정의하고, 각 노드의 부모(parent), 왼쪽 자식(left), 오른쪽 자식(right) 노드, 열번호(colNum)을 저장합니다.
   • 이진 트리를 구성하는 노드들은 배열 nodeArr에 저장되며, 노드의 번호에 따라 인덱스가 매핑됩니다.
   • 또한, 레벨별로 열 번호의 범위를 저장할 levelArr 리스트를 생성합니다.
2. 트리 구성:
   • 이진 트리를 구성합니다.
   • 각 노드의 부모, 왼쪽 자식, 오른쪽 자식 노드의 정보를 이용하여 트리를 구성합니다.
   • 부모 노드와 자식 노드 간의 연결을 설정합니다.
3. 루트 노드 찾기:
   • 루트 노드를 찾기 위해 모든 노드를 순회하며 부모가 없는 (parent가 -1인) 노드를 찾아 root에 저장합니다.
4. Inorder 탐색 및 열 번호 부여:
   • inorder 방식으로 트리를 탐색하면서 각 노드에 열 번호를 부여합니다.
   • inOrder 메서드에서는 왼쪽 자식 노드를 먼저 방문한 후 현재 노드에 열 번호를 부여하고, 오른쪽 자식 노드를 방문합니다.
5. 깊이 우선 탐색 (DFS) 및 레벨별 열 번호 범위 저장:
   • DFS를 사용하여 각 노드를 레벨별로 순회하면서 레벨에 해당하는 리스트에 해당 노드의 열 번호를 저장합니다.
   • dfs 메서드에서는 현재 노드의 레벨과 왼쪽, 오른쪽 자식 노드에 대해 재귀 호출을 수행합니다.
6. 너비가 가장 넓은 레벨 찾기:
   • 각 레벨에 속한 노드들의 열 번호 중에서 가장 왼쪽과 가장 오른쪽에 위치한 노드의 열 번호를 확인하여 너비를 계산합니다.
   • 너비가 가장 큰 레벨과 그 레벨의 너비를 찾아 출력합니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
	
	public static int N, M;
	public static long answer = 0;
	public static int[] arr;
	public static int[][] map;
	public static Node root;
	public static Node[] nodeArr;
	public static int colNumIdx = 1;
	public static ArrayList<ArrayList<Integer>> levelArr = new ArrayList<ArrayList<Integer>>();
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer(br.readLine());
 
    	N = Integer.parseInt(st.nextToken());
    	nodeArr = new Node[N+1];
    	for(int i=0;i<=10001;i++) {
    		levelArr.add(new ArrayList<Integer>());
    	}
    	
    	for(int i=1; i<=N;i++) {
    		nodeArr[i] = new Node(i, null, null);
    	}
    	
    	for(int i=1;i<=N;i++) {
    		st = new StringTokenizer(br.readLine());
    		int nodeNum = Integer.parseInt(st.nextToken());
    		int left = Integer.parseInt(st.nextToken());
    		int right = Integer.parseInt(st.nextToken());
    		
    		if(left > 0) {
    			nodeArr[nodeNum].left = nodeArr[left];
    			nodeArr[left].parent = nodeNum;
    		}
    			
    		if(right > 0) {
    			nodeArr[nodeNum].right = nodeArr[right];
        		nodeArr[right].parent = nodeNum;	
    		}
    		
    	}
    	
    	for(int i=1; i<=N;i++) {
    		if(nodeArr[i].parent == -1) {
    			root = nodeArr[i];
    		}
    	}
    	
    	inOrder(root);
    	
    	dfs(1, root);
    	
    	int maxIdx = 0;
    	int maxAnswer = 0;
    	for(int i=1; i<10001; i++) {
    		if(levelArr.get(i).size() > 0) {
    			int left = levelArr.get(i).get(0);
        		int right = levelArr.get(i).get(levelArr.get(i).size() - 1);
        		
        		if(maxAnswer < right - left + 1) {
        			maxIdx = i;
        			maxAnswer = right - left + 1;
        		}	
    		}
    		
    	}
    	
    	System.out.println(maxIdx+" "+maxAnswer);
	}
	
	public static void dfs(int level, Node start) {
		if(start == null) return ;
		levelArr.get(level).add(start.colNum);
		
		//왼쪽 자식 노드로 이동.
		dfs(level + 1, start.left);
		
		//오른쪽 자식 노드로 이동.
		dfs(level + 1, start.right);
	}
	
	public static void inOrder(Node start) {
		if(start == null) return ;
		inOrder(start.left);
		start.colNum = colNumIdx++;
		inOrder(start.right);
	}
}
 
 
 
class Node{
	int nodeNum;
	int parent = -1; 
	int colNum;
	Node left;
	Node right;
	public Node(int nodeNum, Node left, Node right) {
		this.nodeNum = nodeNum;
		this.left = left;
		this.right = right;
	}
}