[백준] 14725: 개미굴 (트리) - JAVA

class 6

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

 

 

 

# 문제

# 필요개념

이 문제는 결론적으로 노드들의 깊이를 오름차순으로 도출해야하는 문제이기 때문에 dfs를 사용하였다. 평소 그래프 문제를 풀 때에는 이중 리스트를 만들어 풀었지만, 이 문제는 이름이 같은 노드가 존재할 수 있고, 깊이라는 개념이 도입되기 때문에 이중리스트로 풀지 않았다. 

 

A노드의 자식노드인 B노드에게 C라는 자식노드가 존재한다고 가정할 때, A노드에게 C라는 자식노드가 있을 수 있다. 이 두 노드는 이름만 같을 뿐, 아예 다른 노드이기 때문에 그래프문제처럼 풀면 안 된다.

 

Node라는 클래스를 만들고, 여기에 자신의 값과 children을 넣어주었다. children에 값을 추가하는 것은 별도의 메소드 (addChild)을 만들었다.

 

가장 위에 루트노드가 있고, 처음 나오는 값들은 root의 자식이 된다. 따라서 입력을 받기 전에 root라는 값을 갖는 노드를 만들고, 여기에 채워나가기 시작했다. 이렇게 하면 리스트나 배열을 따로 사용하지 않아도 Node 객체 안에 자식들이 담기는 구조가 만들어진다!

 

입력을 담은 별도의 리스트가 없기 때문에, 부모 노드에 자식을 담을 때에는 객체의 children필드에서 직접 노드를 찾아와야 한다.

current.addChild(name);
for (Node ch : current.children) {
    if (ch.value.equals(name)) current = ch;
}

 

이름이 같은 노드를 직접 찾아온다. 층을 구분하는 "--"는 상단에 PLACE라는 이름의 String 객체로 고정시켜두었다. 이는 dfs에서 파라미터로 넘겨받은 floor 만큼 문자열 앞에 붙어 출력된다.

 

 

✅ String.compareTo(String o)

이전에는 String을 오름차순 정렬할 때, 아스키코드를 이용하기 위해 charAt으로 한개한개 비교했는데, String의 compareTo() 라는 메소드를 쓰면 알아서 비교해준다는 걸 알게 되었다.............. 불편함을 느끼긴 했지만 찾아볼 생각은 안 했었는데 이제서야 알게된 나 자신을 반성하고있다. 자바 개념부터 다시 해야할 듯

String.compareTo()

 

# Code

import java.io.*;
import java.util.*;
public class Main {
    static final String SPACE = "--";
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        Node node = new Node("root");

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int depth = Integer.parseInt(st.nextToken());
            Node current = node;
            for (int j = 0; j < depth; j++) {
                String name = st.nextToken();
                current.addChild(name);
                for (Node ch : current.children) {
                    if (ch.value.equals(name)) current = ch;
                }
            }
        }
        dfs(node,-1);
        System.out.println(sb);
    }

    private static void dfs(Node node, int floor) {
        if (!node.value.equals("root")) {
            for (int i = 0 ; i < floor ; i++) {
                sb.append(SPACE);
            }
            sb.append(node.value + "\n");
        }


        Collections.sort(node.children);
        for (Node ch : node.children) {
            dfs(ch, floor + 1);
        }
    }
}
class Node implements Comparable<Node> {
    String value;
    List<Node> children = new ArrayList<>();

    public Node(String n) {
        this.value = n;
    }

    void addChild(String str) {
        for (Node child : children) {
            if (str.equals(child.value)) return;
        }
        children.add(new Node(str));
    }

    @Override
    public int compareTo(Node o) {
        return this.value.compareTo(o.value);
    }
}

 

# 결과