109. 개미굴 (백준 14725) [JAVA]

문제

문제 링크 : https://www.acmicpc.net/problem/14725

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) 이다.

출력

개미굴의 시각화된 구조를 출력하여라.

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

풀이

문제가 길고 복잡하지만, 해결은 간단하게 할 수 있었다.

각각의 입력에서 같은 부분끼리 묶어주면 되기 때문이다. (트리 구조 만들기)

문자열을 빠르게 처리하기 위해서 HashMap을 사용하였고, 각 문자열을 입력받을때 검사하여 만약 존재하는 노드라면 다음 노드로 이어지게 했다.

출력을 할 경우에는 HashMap의 키값을 정렬해주고 출력함으로써 문제를 해결할 수 있었다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {

    static int N;

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

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

            for(int j=0; j<size; j++){
                String s = st.nextToken();

                if(!cur.childs.containsKey(s)){
                    cur.childs.put(s, new Node());
                }
                cur = cur.childs.get(s);
            }
        }
        print(root, "");
    }

    public static void print(Node root, String bar){
        Object[] key = root.childs.keySet().toArray();
        Arrays.sort(key);

        for (Object s : key){
            System.out.println(bar+s);
            print(root.childs.get(s),bar+"--");
        }
    }

}

class Node{
    HashMap<String, Node> childs = new HashMap<>();
}

결과