[백준_14725] 개미굴

문제

백준 14725번
https://www.acmicpc.net/problem/14725

개미는(뚠뚠) 오늘도(뚠뚠) 열심히(뚠뚠) 일을 하네
개미는 아무말도 하지 않지만 땀을 뻘뻘 흘리면서 매일 매일을 살길 위해서 열심히 일을 하네.
한 치 앞도(뚠뚠) 모르는(뚠뚠) 험한 이 세상(뚠뚠) 그렇지만(뚠뚠) 오늘도 행복한 개미들!
우리의 천재 공학자 윤수는 이 개미들이 왜 행복한지 궁금해졌다.
행복의 비결이 개미가 사는 개미굴에 있다고 생각한 윤수는 개미굴의 구조를 알아보기 위해 로봇 개미를 만들었다.
로봇 개미는 센서가 있어 개미굴의 각 층에 먹이가 있는 방을 따라 내려가다 더 이상 내려갈 수 없으면 그 자리에서 움직이지 않고 신호를 보낸다.
이 신호로 로봇 개미는 개미굴 각 층을 따라 내려오면서 알게 된 각 방에 저장된 먹이 정보를 윤수한테 알려줄 수 있다.

로봇 개미 개발을 완료한 윤수는 개미굴 탐사를 앞두고 로봇 개미를 테스트 해보기 위해 위 그림의 개미굴에 로봇 개미를 투입했다. (로봇 개미의 수는 각 개미굴의 저장소를 모두 확인할 수 있을 만큼 넣는다.)
다음은 로봇 개미들이 윤수에게 보내준 정보다.

• KIWI BANANA
• KIWI APPLE
• APPLE APPLE
• APPLE BANANA KIWI

(공백을 기준으로 왼쪽부터 순서대로 로봇 개미가 각 층마다 지나온 방에 있는 먹이 이름을 뜻한다.)
윤수는 로봇 개미들이 보내준 정보를 바탕으로 다음과 같이 개미굴의 구조를 손으로 그려봤다.

APPLE
--APPLE
--BANANA
----KIWI
KIWI
--APPLE
--BANANA

(개미굴의 각 층은 "--" 로 구분을 하였다. 또 같은 층에 여러 개의 방이 있을 때에는 사전 순서가 앞서는 먹이 정보가 먼저 나온다.)
우리의 천재 공학자 윤수는 복잡한 개미굴들을 일일이 손으로 그리기 힘들어 우리에게 그려달라고 부탁했다.
한치 앞도 모르는 험한 이세상 그렇지만 오늘도 행복한 개미들!
행복의 비결을 알기 위해 윤수를 도와 개미굴이 어떤 구조인지 확인해보자.

첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N개가 주어진다. (1 ≤ N ≤ 1000)
두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이 정보 개수 K가 주어진다. (1 ≤ K ≤ 15)
다음 K개의 입력은 로봇 개미가 왼쪽부터 순서대로 각 층마다 지나온 방에 있는 먹이 정보이며 먹이 이름 길이 t는 (1 ≤ t ≤ 15) 이다.

개미굴의 시각화된 구조를 출력하여라.
개미굴의 각 층을 "--" 로 구분하며, 같은 층에 여러개의 방이 있을 때에는 사전 순서가 앞서는 먹이 정보가 먼저 나온다.

• 생각해보기

Code

• Trie(트라이)를 구성한다.
• 구성할 때 방문한 곳에 대해서는 출력하지 않아야 하기 때문에 isVisited을 통해 확인한다.
• 실질적으로 필요한 부분은 insert(삽입), getResult(결과출력) 부분만 필요하기 때문에 두 가지만 구현한다.
• insert(삽입) 부분은 문자열에서 " "부분을 기준으로 나누어 넣어주고 방문 여부를 false로 초기화한다.
• Main에서 StringBuilder를 통해 첫 문자열은 그냥 넣어주고 그 뒤를 따르는 문자열에 대해서는 한 칸씩 내려갈 때마다 "--"도 추가로 앞에 붙여 함께 넣는다.
• 그리고 trie에 insert를 해준다.
• 또한, 결과 출력을 위해 arr(String 배열)도 만들어 같이 넣어준다.
• 결과 출력에 있어 사전순으로 출력되어야 하기 때문에 Arrays.sort를 통해 정렬한다.
• 모든 문자열을 담고 있는 arr을 getResult를 통해 각 문자열에 대해 " "부분을 기준으로 나누어 trie에 cur(현재 노드)의 child key에 해당하는지 파악한다.
• 현재 노드의 child의 key로 해당하는 경우에만 isVisited(방문 여부)를 통해 방문한 적이 없다면 결과를 출력할 StringBuilder에 넣어주고 방문 여부를 true로 바꾸어준다.
• arr의 모든 위치를 돌고 난 후 StringBuilder를 String으로 변환하여 출력한다.

Java

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

class Node { // 트라이에 구성할 Node
    HashMap<String, Node> child = new HashMap<>();
    boolean isVisited = false; // 방문 여부
}

class Trie { // 트라이 구성
    Node root = new Node();

    // 삽입
    public void insert(String str) {
        Node cur = this.root;

        for(String s: str.split(" ")) {
            // 현재 cur에 s가 포함되어 있지 않을 경우
            if (!cur.child.containsKey(s)) {
                cur.child.put(s, new Node());
            }
            cur = cur.child.get(s);
            cur.isVisited = false;
        }
    }

    // 결과 반환
    public void getResult(String[] arr) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < arr.length; i++) {
            String str = arr[i];
            Node cur = root;

            for (String s : str.split(" ")) {
                // 문자열이 Trie cur.child에 key로 포함된 경우
                if (cur.child.containsKey(s)) {
                    cur = cur.child.get(s);
                    // 이전에 방문했었을 경우
                    if (cur.isVisited) {
                        continue;
                    }
                    // sb에 결과를 담고 방문했음을 표시
                    sb.append(s).append("\n");
                    cur.isVisited = true;
                }
            }
        }
        System.out.println(sb.toString());
    }
}

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        Trie trie = new Trie();
        String[] arr = new String[N]; // 먹이 정보를 담을 배열

        int idx = 0;
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            StringBuilder sb = new StringBuilder();
            int K = Integer.parseInt(st.nextToken());
            for (int j = 0; j < K; j++) {
                String s = st.nextToken();
                // 처음에는 그냥 입력한 값 등록
                if (j == 0) {
                    sb.append(s).append(" ");
                } else {
                    // 그 외 경우에는 한 층씩 내려갈 때마다 "--"를 앞에 추가
                    for (int k = 0; k < j; k++) {
                        sb.append("--");
                    }
                    sb.append(s).append(" ");
                }
            }
            // 트라이에 삽입
            trie.insert(sb.toString());
            // arr 배열에도 삽입
            arr[idx++] = sb.toString();
        }
        // 사전 순서로 나와야하기 때문에 정렬
        Arrays.sort(arr);
        // 결과 출력
        trie.getResult(arr);
    }
}