[백준] 14752번: 개미굴 - java

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

public class Main {

    static class Node {
        Map<String, Node> child;

        public Node() {
            child = new HashMap<>();
        }
    }

    static StringBuilder sb;
    static int n;
    static Node root;
    static Node cur;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        sb = new StringBuilder();
        n = Integer.parseInt(br.readLine());

        root = new Node();
        for(int i=0; i<n; i++){
            st = new StringTokenizer(br.readLine());
            int k = Integer.parseInt(st.nextToken());

            cur = root; // cur은 루트
            for(int j=0; j<k; j++){
                add(st.nextToken());
            }
        }

        print(root, 0);

        System.out.println(sb.toString());

    }

    public static void add(String s){
        if (cur.child.get(s) == null){
            cur.child.put(s, new Node());
        }
        cur = cur.child.get(s); // 자식을 cur 로 변경
    }

    public static void print(Node cur, int depth){
        if (cur.child != null){
            List<String> children = new ArrayList<>(cur.child.keySet()); // cur의 자식 key list
            Collections.sort(children); // 사전순대로 정렬하기

            for(String child : children){
                sb.append(getLine(depth)).append(child).append("\n");
                print(cur.child.get(child), depth+1);
            }
        }
    }

    public static String getLine(int depth){
        StringBuilder sb = new StringBuilder("");
        for(int i=0; i<depth*2; i++)
            sb.append("-");
        return sb.toString();
    }

}

 

 

Node 를 이용한 트리구조로 간단히 풀 수 있는 문제이다. 

출력은 자식 node를 부르는 재귀호출을 통한 DFS 을 구현하였다.

 

1. Node

    static class Node {
        Map<String, Node> child;

        public Node() {
            child = new HashMap<>();
        }
    }

한 노드는 여러 자식 노드를 가질 수 있다. 

따라서 자식 노드를 Map으로 구현하여, key값은 자식 노드의 데이터인 String, value값은 자식 노드 객체인 Node 로 두었다.

 

2. 노드 삽입

	for(int i=0; i<n; i++){
            st = new StringTokenizer(br.readLine());
            int k = Integer.parseInt(st.nextToken());

            cur = root; // cur은 루트
            for(int j=0; j<k; j++){
                add(st.nextToken());
            }
        }

로봇개미는 루트노드의 최상단 자식노드부터 깊이우선탐색을 한다.

따라서 항상 시작은 root 로 하여 탐색해야 한다.

로봇개미가 얻은 K개의 먹이정보는 루트부터~리프노드까지의 경로로, 이는 고유하게 1개밖에 존재하지 않는다.

 

public static void add(String s){
        if (cur.child.get(s) == null){
            cur.child.put(s, new Node());
        }
        cur = cur.child.get(s); // 자식을 cur 로 변경
}

cur은 루트부터 시작한다.

만약 cur의 자식노드에, 내가 삽입하려하는 s가 존재하지 않는다면 s를 cur의 자식으로 새로 삽입한다.

그런다음, 삽입한 자식 s를 cur로 변경하여, 다음번에는 cur이 부모가 되어 새로운 자식노드를 삽입하는 것이다.

 

 

3. 출력하기 (DFS)

public static void print(Node cur, int depth){
        if (cur.child != null){
            List<String> children = new ArrayList<>(cur.child.keySet()); // cur의 자식 key list
            Collections.sort(children); // 사전순대로 정렬하기

            for(String child : children){
                sb.append(getLine(depth)).append(child).append("\n");
                print(cur.child.get(child), depth+1);
            }
        }
}

cur은 루트부터 시작한다.

만약 cur의 자식이 존재한다면, 자식들을 list에 담고, 자식들을 사전순대로 정렬한다.

그런 다음, 자식들을 출력하기 위해 depth만큼 "--" 을 출력한 후, 자식의 데이터를 출력한다.

그런다음 자식노드를 부모노드로 하고 깊이를 1 증가시켜, 다시 print() 를 재귀호출하는 방식이다.