[JAVA] BOJ 백준 2250번 - 트리의 높이와 너비

목차

• 문제
• 내가 푼 방법
• 자바 코드
• 결과 및 회고

---

1. 문제

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

2250번: 트리의 높이와 너비

---

2. 내가 푼 방법

탐색하는 규칙이 존재하는 DFS 문제이다.

 

루트 노드에서 시작해 각 노드가 위치한 가로 인덱스를 구하기 위해 왼쪽 -> 위 -> 오른쪽  순서로 노드를 탐색한다. 이때 standard 매개변수는 현재 노드보다 더 왼쪽에 위치한 노드의 개수를 의미한다. 따라서 왼쪽 자식 노드를 탐색할 땐 이전에 받은 standard를 그대로 넘겨주고, 오른쪽을 탐색할 땐 왼쪽 자식 노드에서 카운팅 된 총 노드 개수 + 1 (자기 자신)을 해줘야 한다. 탐색이 끝나면, width 배열에 저장해 둔 레벨 별 최대, 최소 가로 인덱스를 이용해 가장 긴 가로폭을 찾아내면 된다.

 

(※ 이 문제를 풀 때는 루트 노드는 고정된 값이 아니라는 것을 주의해야 한다!)

static int N;
static int[][] child; // 자식 노드

static int[] count; // 가로 인덱스
static int[][] width; // 깊이 별 최소, 최대 인덱스
static int root;
static int maxDepth;
static int resultIdx, resultWidth;

public static void solution() {
    dfs(root, 0, 1);

    for (int i = 1; i <= maxDepth; i++) {
        int len = width[i][1] - width[i][0] + 1;

        if (resultWidth < len) {
            resultWidth = len;
            resultIdx = i;
        }
    }
}

public static int dfs(int v, int standard, int depth) {
    if (v == -1) return standard;

    count[v] = dfs(child[v][0], standard, depth + 1); // 왼쪽

    maxDepth = Math.max(depth, maxDepth);
    width[depth][0] = Math.min(width[depth][0], count[v]);
    width[depth][1] = Math.max(width[depth][1], count[v]);

    return dfs(child[v][1] , count[v] + 1, depth + 1); // 오른쪽
}

---

3. 자바 코드

깃허브 풀이 주소 : https://github.com/geujeog/BOJ/blob/main/B2250.java

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

class Main {
    static int N;
    static int[][] child;

    static int[] count; // 인덱스
    static int[][] width; // 깊이 별 최소, 최대 인덱스
    static int root;
    static int maxDepth;
    static int resultIdx, resultWidth;

    public static void main (String[] args) throws IOException {
        input();
        solution();
        output();
    }

    public static void solution() {
        dfs(root, 0, 1);

        for (int i = 1; i <= maxDepth; i++) {
            int len = width[i][1] - width[i][0] + 1;

            if (resultWidth < len) {
                resultWidth = len;
                resultIdx = i;
            }
        }
    }

    public static int dfs(int v, int standard, int depth) {
        if (v == -1) return standard;

        count[v] = dfs(child[v][0], standard, depth + 1); // 왼쪽

        maxDepth = Math.max(depth, maxDepth);
        width[depth][0] = Math.min(width[depth][0], count[v]);
        width[depth][1] = Math.max(width[depth][1], count[v]);

        return dfs(child[v][1] , count[v] + 1, depth + 1); // 오른쪽
    }

    public static void output() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        bw.write(resultIdx+" "+resultWidth);

        bw.flush();
        bw.close();
    }

    public static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());
        child = new int[N+1][2];
        count = new int[N+1];
        width = new int[N+1][2];

        boolean[] isRoot = new boolean[N+1];
        Arrays.fill(isRoot, true);

        for (int i = 1; i <= N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int v = Integer.parseInt(st.nextToken());
            child[v][0] = Integer.parseInt(st.nextToken());
            child[v][1] = Integer.parseInt(st.nextToken());

            width[i][0] = Integer.MAX_VALUE;
            if (child[v][0] >= 1) isRoot[child[v][0]] = false;
            if (child[v][1] >= 1) isRoot[child[v][1]] = false;
        }

        for (int i = 1; i <= N; i++) {
            if (isRoot[i]) {
                root = i;
                break;
            }
        }

        br.close();
    }
}

---

4. 결과 및 회고

요즘에는 아예 모르는 알고리즘이 아닌 이상 결국 풀 수 있다고 믿고ㅎㅎ 최대한 혼자 풀려고 노력하는 중이다.

이 문제도 처음 문제를 봤을 때 풀기 싫어서 미루다가,, 두어 시간 잡고 구현해 낼 수 있었다!