[BaekJoon] 2250 트리의 높이와 너비 (java)

🔗 문제 링크

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

📝 문제 풀이 방법

이번 문제는 문제 풀이 방법을 생각하는데 여러가지 방법으로 생각을 해봐도 해결법을 도출하지 못하여 문제 풀이 영상에서 힌트를 얻은 후 풀게 되었다.

일단 이번 문제의 경우는 tree순회방법인 inorder방법을 사용하여 풀어야한다.
inorder는 순회를 left child node -> parent node -> right child node순으로 순회를 하는 방법으로 해당 순회 방법을 이용하여 순회 결과를 출력하면 아래의 그래프의 각각의 x좌표에 있는 node순서대로 출력이 된다.

그래프 상에서 각각의 node들의 x좌표를 알게 되었으면 이제 depth별로 너비를 구하면 된다.
너비는 inorder순회를 하며 각각의 depth별로 arrayList를 만들어 node들을 각각 해당하는 depth의 list에 추가를 하여줬다.

위와 같이 Depth별로 node id가 들어간 List를 생성한 후 Depth별로 첫번째와 마지막에 위치한 node들의 x좌표를 이용하여 Depth별 최종 너비를 구하고 그 후에 가장 넓은 Depth의 정보를 출력해주면 됩니다.

👨🏻‍💻 작성한 코드

import java.io.*;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.StringTokenizer;


class Node {
	int nodeId;
	int leftNode;
	int rightNode;
	int parent = -1;
	int depth = -1;
	
	public Node(int nodeId) {
		this.nodeId = nodeId;
	}
}

public class Main {
	static ArrayList<Integer> explore = new ArrayList<>();
	static HashMap<Integer, ArrayList<Integer>> depthNode = new HashMap<>();
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		ArrayList<Node> treeInfo = new ArrayList<>();
		int n = Integer.parseInt(br.readLine());
		
		for (int i=0; i<= n; i++) {
			treeInfo.add(new Node(i));
		}
		
		
		StringTokenizer st;
		for (int i=0; i<n; i++) {
			st = new StringTokenizer(br.readLine());
			int nodeId = Integer.parseInt(st.nextToken());
			int leftNode = Integer.parseInt(st.nextToken());
			int rightNode = Integer.parseInt(st.nextToken());
			treeInfo.get(nodeId).leftNode = leftNode;
			treeInfo.get(nodeId).rightNode = rightNode;
			
			if (leftNode != -1) treeInfo.get(leftNode).parent = nodeId;
			if (rightNode != -1) treeInfo.get(rightNode).parent = nodeId;
		}
		
		int rootNode = -1;
		for (int i=1; i<=n; i++) {
			if (treeInfo.get(i).parent == -1) {
				rootNode = i;
			}
		}
		

		inOrder(treeInfo, rootNode, 0);
		
		int maxDepth = -1;
		int maxLen = -1;
		for (int i=1; i<=depthNode.size(); i++) {
			int len = findWidth(i);

			if (len > maxLen) {
				maxDepth = i;
				maxLen = len;
			}
		}
		
		System.out.println(maxDepth+ " "+ maxLen);

	}
	static void inOrder(ArrayList<Node> treeInfo, int parent, int parentDepth) {
		int left = treeInfo.get(parent).leftNode;
		int right = treeInfo.get(parent).rightNode;
		
		if (treeInfo.get(parent).depth == -1) treeInfo.get(parent).depth = parentDepth+1;
		
		if (depthNode.containsKey(parentDepth+1)) {
			depthNode.get(parentDepth+1).add(parent);
		}
		else {
			ArrayList<Integer> temp = new ArrayList<>();
			temp.add(parent);
			depthNode.put(parentDepth+1, temp);
		}
		
		
		if (left != -1) inOrder(treeInfo, left, parentDepth+1);
		explore.add(parent);
		if (right != -1) inOrder(treeInfo, right, parentDepth+1);
		

	}
	
	static int findWidth(int depth) {
		ArrayList<Integer> depthList = depthNode.get(depth);
		int start = depthList.get(0);
		int end = depthList.get(depthList.size()-1);
		
		return explore.indexOf(end) - explore.indexOf(start) + 1; 
	}
	

}