[BaekJoon] 14725 개미굴 (Java)

1.  문제 링크

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

2.  문제

요약

• 로봇 개미는 센서가 있어 개미굴의 각 층에 먹이가 있는 방을 따라 내려가다 더 이상 내려갈 수 없다면 그 자리에서 움직이지 않고 신호를 보냅니다.
• 이 신호로 로봇 개미는 개미굴 각 층을 따라 내려오면서 알게 된 각 방에 저장된 먹이 정보를 윤수에게 알려줄 수 있습니다.
• 개미굴 탐사를 앞두고 로봇 개미를 테스트 해보기 위해 어떠한 개미굴에 로봇 개미를 투입하였습니다. 로봇 개미의 수는 각 개미굴의 저장소를 모두 확인할 수 있을만큼 넣습니다.
• 윤수는 로봇 개미들이 보내준 정보를 바탕으로 개미굴의 구조를 손으로 그립니다.
• 개미굴에 대한 정보가 주어질 때, 개미굴의 시각화된 구조를 구하는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 1,000보다 작거나 같은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N이 주어지고 두 번째 줄부터 N개의 줄에 개미굴에 대한 정보가 주어집니다. 해당 정보의 시작은 1보다 크거나 같고 15보다 작거나 같은 로봇 개미 한마리가 보내준 먹이 정보 개수 K가 주어지고 이후에는 로봇 개미가 왼쪽부터 순서대로 각 층마다 지나온 먹이 정보가 주어집니다. 먹이 정보는 K개의 먹이 이름으로 이루어져있고 먹이 이름의 길이 t는 1보다 크거나 같고 15보다 작거나 같습니다.
• 출력: 개미굴의 시각화된 구조를 출력합니다. 개미굴의 각 층을 "--"로 구분하고, 같은 층에 여러 개의 방이 있을 때에는 사전 순서가 앞서는 먹이 정보가 먼저 나옵니다.

3.  소스코드

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;
    static Node root;

    static void input() {
        Reader scanner = new Reader();

        N = scanner.nextInt();
        root = new Node();

        for(int idx = 0; idx < N; idx++) {
            int infoNum = scanner.nextInt();
            Node curNode = root;

            for(int infos = 0; infos < infoNum; infos++) {
                String info = scanner.next();

                if(!curNode.children.containsKey(info))
                    curNode.children.put(info, new Node());
                curNode = curNode.children.get(info);
            }
        }
    }

    static void solution() {
        printAntTunnel(root, "");
    }

    static void printAntTunnel(Node root, String level) {
        Object[] keyArr = root.children.keySet().toArray();
        Arrays.sort(keyArr);

        for(Object key : keyArr) {
            System.out.println(level + key);
            printAntTunnel(root.children.get(key), level + "--");
        }
    }

    static class Node {
        HashMap<String, Node> children;

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

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch(IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

4.  접근

• 개미굴의 각 층을 나타내기 위해 Node 클래스를 정의합니다.
  • 현재 층에 존재하는 먹이 이름을 key로 하고, 해당 먹이가 있는 방의 아래 층을 나타내는 Node를 value로 하는 HashMap을 멤버로 가집니다.

• root라는 Node 객체를 생성합니다.
• N개의 먹이 정보들을 받아 각 정보들을 이용해 Node 객체의 멤버 변수의 값을 채워나갑니다.
  • curNode라는 Node 객체를 생성하여 root 값으로 초기화합니다.
  • t개의 먹이 정보를 처음 정보부터 마지막 정보까지 순회하며 각 층에 있는 먹이 정보들을 채웁니다.
    • 해당 먹이 정보가 현재 curNode의 멤버 변수에 키로 존재하는지, 즉, 이전에 입력으로 받아 알맞은 층의 Node 객체의 멤버 변수에 추가해줬는지 확인하여, 만약 존재하지 않는다면 해당 층의 Node 객체의 멤버 변수에 해당 먹이 정보를 추가해줍니다.
      • 아래 층으로 내려가야하기 때문에 curNode의 값을 현재 먹이 정보를 key로 하는 value 값으로 변경해줍니다.

• 입력 과정에서 Tree와 같은 형태로 만들어주었기 때문에 재귀를 통해 출력 형태에 맞게 출력합니다.
  • 현재 인자로 주어진 Node 객체의 모든 key 값들을 가져와 keyArr라는 배열에 넣습니다.
  • 같은 층에 여러 개의 방이 있을 때에는 사전 순서가 앞서는 먹이 정보가 먼저 나와야하므로 keyArr를 정렬해줍니다.
  • 각 키를 순회하면서 다음 작업을 진행합니다.
    • 현재 층에서 출력되어야 하는 "--"들을 level이라는 인자를 통해 전달하고 있으므로 level과 현재 키를 출력합니다.
      • 현재 키의 아래층으로 재귀를 통해 이동하여 이 작업을 반복합니다.