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

목차

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

---

1. 문제

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

---

2. 내가 푼 방법

메모리 초과가 관건이었다. 무조건 배열을 선언하더라도 사용할 만큼만 선언해 주었다.

• 이진트리를 저장하기 위해 선언한 arr 배열
• 루트 노드를 찾기 위해 선언해 준 isRoot 배열
• depth 당 최소, 최대 열을 저장해 주기 위한 square 배열

주의할 점은 arr 배열과 squre 배열은 반드시 필요하다고 생각했기 때문에, 루트를 찾기 위한 isRoot 배열을 int 형으로 선언해 주면 바로 메모리 초과가 걸린다는 것이다. boolean 형으로 선언해 주는 것이 중요하다고 느꼈다.

(근데 어쩌면 square 배열에서 N+1로 무조건 선언하는게 아닌 depth를 확인해서 선언해 줄인다면 가능할수도?)

int N = Integer.parseInt(br.readLine());
int[][] arr = new int[N+1][2];
boolean[] isRoot = new boolean[N+1];

for (int i = 0; i < N; i++) {
    StringTokenizer st = new StringTokenizer(br.readLine());

    int v = Integer.parseInt(st.nextToken());
    int left = Integer.parseInt(st.nextToken());
    int right = Integer.parseInt(st.nextToken());

    if (left != -1) {
        arr[v][0] = left;
        isRoot[left] = true;
    }

    if (right != -1) {
        arr[v][1] = right;
        isRoot[right] = true;
    }
}

int rootIdx = 0;
for (int i = 1; i <= N; i++) {
    if (!isRoot[i]) rootIdx = i;
}

 

이제 depth 별로 최소 열, 최대 열을 구하는 것이다.

각 노드 당 몇 번째 열인지 카운팅하는 방법은 중위 순회로 방문하면서 전역 변수 cnt를 카운팅해주는 것이다.

// 전역 변수 : static int cnt = 1;

public static void dfs (int[][] square, int[][] arr, int v, int depth) {
    if (arr[v][0] != 0) {
        dfs(square, arr, arr[v][0], depth+1);
    }

    if (square[depth][0] == 0) square[depth][0] = cnt;
    square[depth][1] = cnt++;

    if (arr[v][1] != 0){
        dfs(square, arr, arr[v][1], depth+1);
    }

    depthMax = Math.max(depthMax, depth);
}

---

3. 자바 코드

깃허브 풀이 주소

https://github.com/geujeog/BOJ/blob/main/B2250.java

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

class Main {
    static int cnt = 1;
    static int depthMax = 0;

    public static void main (String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        int[][] arr = new int[N+1][2];
        boolean[] isRoot = new boolean[N+1];

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());

            int v = Integer.parseInt(st.nextToken());
            int left = Integer.parseInt(st.nextToken());
            int right = Integer.parseInt(st.nextToken());

            if (left != -1) {
                arr[v][0] = left;
                isRoot[left] = true;
            }

            if (right != -1) {
                arr[v][1] = right;
                isRoot[right] = true;
            }
        }

        int rootIdx = 0;
        for (int i = 1; i <= N; i++) {
            if (!isRoot[i]) rootIdx = i;
        }

        int[][] square = new int[N][2];
        dfs(square, arr, rootIdx, 0);

        int width = 0;
        int widthLine = 0;

        for (int i = 0; i <= depthMax; i++) {
            int minus = square[i][1] - square[i][0] + 1;

            if (width < minus) {
                width = minus;
                widthLine = i + 1;
            }
        }

        bw.write(widthLine+" "+width);

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

    public static void dfs (int[][] square, int[][] arr, int v, int depth) {
        if (arr[v][0] != 0) {
            dfs(square, arr, arr[v][0], depth+1);
        }

        if (square[depth][0] == 0) square[depth][0] = cnt;
        square[depth][1] = cnt++;

        if (arr[v][1] != 0){
            dfs(square, arr, arr[v][1], depth+1);
        }

        depthMax = Math.max(depthMax, depth);
    }
}

---

4. 결과 및 회고

첨엔 조금 어려워 보였는데, 문제를 제대로 읽고 나니 어떻게 풀어야 할지 생각해 낼 수 있었다.

근데 메모리 초과에서 조금 당황하긴 했는데, 불필요한 메모리를 줄이고 나니 해결됐다. ㅎㅎ