[BOJ] 14725 개미굴 - JAVA

1. 문제

14725번: 개미굴

행복의 비결이 개미가 사는 개미굴에 있다고 생각한 윤수는 개미굴의 구조를 알아보기 위해 로봇 개미를 만들었다.
로봇 개미는 센서가 있어 개미굴의 각 층에 먹이가 있는 방을 따라 내려가다 더 이상 내려갈 수 없으면 그 자리에서 움직이지 않고 신호를 보낸다.
이 신호로 로봇 개미는 개미굴 각 층을 따라 내려오면서 알게 된 각 방에 저장된 먹이 정보를 윤수한테 알려줄 수 있다.
로봇 개미 개발을 완료한 윤수는 개미굴 탐사를 앞두고 로봇 개미를 테스트 해보기 위해 위 그림의 개미굴에 로봇 개미를 투입했다. (로봇 개미의 수는 각 개미굴의 저장소를 모두 확인할 수 있을 만큼 넣는다.)
다음은 로봇 개미들이 윤수에게 보내준 정보다.

KIWI BANANA
KIWI APPLE
APPLE APPLE
APPLE BANANA KIWI

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

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

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

---

2. 풀이

Trie 클래스

 자식구조를 저장하기 위해 Map을 사용했다. 새로 정보를 추가할 때 ArrayList로 하나하나 탐색하는 것보다 해싱을 사용하는 Map이 더 낫다고 판단했다.

static class Trie {
   Map<String,Trie> child;
   String info;
   Trie(String info){
      child = new HashMap<>();
      this.info = info;
   }
}

 

Main

1.  StringBuilder를 전역변수로 설정한다. main과 print에서 둘 다 사용하기 위해서다.
2.  head로 삼을 Trie를 하나 만들고 하나씩 탐색하며 추가한다.
3.  만약 node의 child에 새로 추가할 재료가 없다면 put한다.
4.  node를 child.get(info)로 교체하고 다음 재료 탐색을 시작한다.
5.  print(head, -2)를 호출해서 StringBuilder에 문자열을 더한다.
6.  StringBuilder를 출력한다.

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

   Trie head = new Trie("-");

   int M;
   String info;
   Trie node;
   for(int i=0;i<N;i++){
      st = new StringTokenizer(in.readLine());
      M = Integer.parseInt(st.nextToken());
      node = head;
      for(int j=0;j<M;j++){
         info = st.nextToken();
         if(!node.child.containsKey(info)){
            node.child.put(info, new Trie(info));
         }
         node = node.child.get(info);
      }
   }

   print(head,-2);
   System.out.print(sb);
}

 

Print

1.  임의로 설정한 head를 sb에 더하지 않기 위해 hyphen이 0 이상일 때만 현재 노드의 이름을 출력한다.
2.  hyphen의 개수만큼 '-'을 더하고, 그 뒤에 노드의 이름을 추가한다.
3.  자식 노드 맵의 key를 list에 담아서 정렬한다.
4.  정렬된 list의 key값으로 map(child)에 접근해서 print메서드를 재귀호출한다. 이때, hyphen을 2씩 추가한다.

static StringBuilder sb = new StringBuilder();

private static void print(Trie node, int hyphen){
   //1. 현재 노드 이름 출력
   if(hyphen>=0){
      for(int i=0;i<hyphen;i++) sb.append('-');
      sb.append(node.info).append('\n');
   }

   //2. 자식 노드 정렬
   //3. 자식 노드로 재귀호출
   List<String> list = new ArrayList<>(node.child.keySet());
   Collections.sort(list);
   for(String ch:list){
      print(node.child.get(ch),hyphen+2);
   }
}

 

전체 코드

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

public class BOJ_14725_개미굴 {
   static class Trie {
      Map<String,Trie> child;
      String info;
      Trie(String info){
         child = new HashMap<>();
         this.info = info;
      }
   }

   static StringBuilder sb = new StringBuilder();

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

      Trie head = new Trie("-");

      int M;
      String info;
      Trie node;
      for(int i=0;i<N;i++){
         st = new StringTokenizer(in.readLine());
         M = Integer.parseInt(st.nextToken());
         node = head;
         for(int j=0;j<M;j++){
            info = st.nextToken();
            if(!node.child.containsKey(info)){
               node.child.put(info, new Trie(info));
            }
            node = node.child.get(info);
         }
      }

      print(head,-2);
      System.out.print(sb);
   }

   private static void print(Trie node, int hyphen){
      //1. 현재 노드 이름 출력
      if(hyphen>=0){
         for(int i=0;i<hyphen;i++) sb.append('-');
         sb.append(node.info).append('\n');
      }

      //2. 자식 노드 정렬
      //3. 자식 노드로 재귀호출
      List<String> list = new ArrayList<>(node.child.keySet());
      Collections.sort(list);
      for(String ch:list){
         print(node.child.get(ch),hyphen+2);
      }
   }
}

---

3. 결과