백준 2250 - 트리의 높이와 너비 (자바 - 그래프(트리) 탐색)

백준 2250 - 트리의 높이와 너비 (자바 - 그래프(트리) 탐색)

해설이나 다른 사람의 설명을 듣지 않고 처음으로 혼자 풀어낸 골드 티어 문제(골드 2)

아래와 같은 규칙에 따라 행과 열에 번호가 붙어있는 격자 모양의 틀 속에 이진 트리를 그린다고 할 때, 해당 이진트리의 너비를 구해야 하는 문제이다.

1. 이진 트리에서 같은 레벨(level) 에 있는 노드는 같은 행에 위치한다.

2. 한 열에는 한 노드만 존재한다.

3. 임의의 노드의 왼쪽 부트리(left subtree) 에 있는 노드들은 해당 노드보다 왼쪽의 열에 위치하고, 오른쪽 부트리(right subtree) 에 있는 노드들은 해당 노드보다 오른쪽의 열에 위치한다.

5. 노드가 배치된 가장 왼쪽 열과 오른쪽 열 사이엔 아무 노드도 없이 비어있는 열은 없다.

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

이 문제의 해결에 대한 아이디어는 다음과 같다.

1. 입력으로 들어온 노드 값들 중에 트리의 루트 노드를 찾아준다.(부모 노드값으로 들어온 데이터 중에서 한번도 왼쪽, 오른쪽 노드 정보로 입력되지 않은 노드가 바로 트리의 루트 노드이다.)

2. 입력으로 들어온 트리를 중위 순회(inorder - 왼쪽 노드 -> 부모 노드 -> 오른쪽 노드 순으로 탐색)로 탐색하면 해당 탐색 순서가 바로 각 노드별 너비 값에 해당된다.

3. 중위 순회를 통해 각 노드별로 너비 값을 계산해줌과 동시에, 각 높이별로 어떤 노드들이 있는지에 대한 정보를 해시맵에 담아둔다.

4. 각 높이별로 너비의 최대값과 최소값을 구한뒤 (최대값 - 최소값 + 1) 연산을 통해 나온 결과값을 너비 리스트에 담아준다.

5. 최종적으로 너비 리스트에 담겨있는 값들 중에서 최대값이 바로 이 트리의 최대 너비가 된다.

아래는 소스 코드이다.

- Main.java

import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.HashMap; import java.util.List; import java.util.StringTokenizer; public class Main { static HashMap tree = new HashMap(); static HashMap> rank = new HashMap>(); static int width = 1; static int rankNumber = 1; public static void main(String[] args) throws NumberFormatException, IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); HashMap rootCheck = new HashMap(); int nodeCount = Integer.parseInt(br.readLine()); StringTokenizer st = null; for(int i = 0; i < nodeCount; i++) { st = new StringTokenizer(br.readLine(), " "); int value = Integer.parseInt(st.nextToken()); int leftValue = Integer.parseInt(st.nextToken()); int rightValue = Integer.parseInt(st.nextToken()); BNode node = new BNode(value); BNode[] childArray = new BNode[2]; if(leftValue != -1) { BNode leftNode = new BNode(leftValue); childArray[0] = leftNode; } if(rightValue != -1) { BNode rightNode = new BNode(rightValue); childArray[1] = rightNode; } rootCheck.put(leftValue, 0); rootCheck.put(rightValue, 0); tree.put(node.getValue(), childArray); } // 중위 순회를 하되, 트리의 가장 왼쪽부터 너비 값을 1씩 증가시켜간다.(그냥 중위 순회 순서대로 너비값 주면 됨) // 그와 동시에 해당 노드의 레벨 값을 rank 해시맵에 넣어줘야 한다. // 루트가 1이 아닐수도 있기 때문에 무작정 정렬을 할게 아니라 일련의 과정을 통해 루트 노드를 찾아야 한다. // 부모 노드로 입력 받은 값들 중에 왼쪽 노드, 오른쪽 노드로 한번도 들어가본적이 없는 노드가 곧 루트 노드이다. int rootNumber = 0; Object[] keyArray = tree.keySet().toArray(); for(int i = 0; i < keyArray.length; i++) { if(!rootCheck.containsKey((int)keyArray[i])) { rootNumber = (int)keyArray[i]; break; } } inorder(rootNumber, rankNumber); // 각 높이 별로 너비 최소값과 최대값 간의 차이를 구한 후, 해당 값이 전체 너비 기준 최대값인지 판별한다. Object[] rankKey = rank.keySet().toArray(); Arrays.sort(rankKey); List widthList = new ArrayList(); for(int i = 0; i < rankKey.length; i++) { List list = rank.get((int)rankKey[i]); int min = Collections.min(list).getWidth(); int max = Collections.max(list).getWidth(); widthList.add(max-min+1); } int maxWidth = Collections.max(widthList); int index = widthList.indexOf(maxWidth) + 1; bw.write(index + " " + maxWidth + "

"); bw.flush(); bw.close(); } private static void inorder(int node, int rankNumber) { BNode[] childArray = tree.get(node); if(childArray[0] != null) inorder(childArray[0].getValue(), rankNumber+1); if(rank.containsKey(rankNumber)) { List list = rank.get(rankNumber); BNode bnode = new BNode(node); bnode.setWidth(width); list.add(bnode); rank.replace(rankNumber, list); } else { List list = new ArrayList(); BNode bnode = new BNode(node); bnode.setWidth(width); list.add(bnode); rank.put(rankNumber, list); } width++; if(childArray[1] != null) inorder(childArray[1].getValue(), rankNumber+1); } } class BNode implements Comparable{ private int value; private int width; public BNode(int value) { this.value = value; } public int getValue() { return value; } public int getWidth() { return width; } public void setWidth(int width) { this.width = width; } @Override public int compareTo(BNode o) { return this.width - o.getWidth(); } }

from http://evan-development.tistory.com/152 by ccl(A) rewrite - 2021-12-26 18:26:39