문제
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를 만족한다. 먹이 정보는 알파벳 대문자로만 이루어져 있다.
출력
개미굴의 시각화된 구조를 출력하여라.
개미굴의 각 층을 "--" 로 구분하며, 같은 층에 여러개의 방이 있을 때에는 사전 순서가 앞서는 먹이 정보가 먼저 나온다.
최상위 굴을 포함하여 하나의 굴에서 개미굴이 여러개로 나뉠 때 먹이 종류별로 최대 한 번만 나올 수 있다.
제한
1 ≤ N ≤ 1000
예제 입력 1
3
2 B A
4 A B C D
2 A C
예제 출력 1
A
--B
----C
------D
--C
B
--A
예제 입력 2
4
2 KIWI BANANA
2 KIWI APPLE
2 APPLE APPLE
3 APPLE BANANA KIWI
예제 출력 2
APPLE
--APPLE
--BANANA
----KIWI
KIWI
--APPLE
--BANANA
접근
기본적으로 개미굴이 트리 구조로 이루어져 있기 때문에 트리만 잘 만들면 그 이후에는 어렵지 않겠다고 생각했다.
각 입력이 맨 윗층부터 1층씩 내려가면서, 즉 트리의 깊이를 1씩 증가시키면서 하나씩 주어지기 때문에 트리를 타고 한 층씩 내려가면서 현재 층, 즉 현재 깊이에 입력으로 주어진 이름의 개미굴이 있는지 확인하고, 없으면 추가하는 동작을 반복하면 트리가 완성된다.
나는 이 문제를 풀 때 Node라는 객체 내 TreeMap<String, Node> 타입의 childrenNodes 필드에 자식 노드들을 저장했다. 단순 리스트가 아니라 트리맵을 사용한 이유는 크게 두 가지이다.
1. 현재 층에 어떤 먹이 이름을 가진 개미굴이 있는지 확인하려면 Node 객체 내 String 필드에 개미굴 먹이 이름을 저장한 후 현재 층에 있는 모든 Node들의 해당 필드 값을 확인해야 했다. 그런데 Node는 여러 필드 값을 가지는 객체이기 때문에 단순히 리스트에 자식 노드를 저장하면 리스트 내 모든 객체를 하나씩 순회하며 까보면서 String 필드 값을 확인해야 한다. 반면 Map을 사용하면 .containsKey() 메서드를 사용해서 key 값 존재 여부를 바로 확인할 수 있어 편리하다.
2. 문제에서 '같은 층에 여러 개의 방이 있을 때에는 사전 순서가 앞서는 먹이 정보가 먼저 나온다'고 했다.
TreeMap을 사용하면 key 값 기준으로 정렬된 상태가 유지되므로 그냥 저장하기만 하면 자동으로 문제 조건에 맞게 정렬이 된다.
이렇게 트리를 완성했다면 리프 노드를 만날 때까지 트리를 DFS로 순회하며 출력해주면 된다.
트리가 어려운 자료 구조도 아닌데 솔직히 왜 이렇게까지 티어가 높은지 잘 이해가 안 됐던... 문제였다.
구현
import java.io.*;
import java.util.*;
class Main {
static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
Node root = new Node("root");
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
int K = Integer.parseInt(st.nextToken());
Node curr = root;
for (int j = 0; j < K; j++) {
String foodName = st.nextToken();
// 입력으로 주어진 이름의 개미굴이 현재 층에 존재하지 않으면 새롭게 추가
if (!curr.childrenNodes.containsKey(foodName)) {
curr.childrenNodes.put(foodName, new Node(foodName));
}
// 한 층 내려가기
curr = curr.childrenNodes.get(foodName);
}
}
buildStructure(root, -1);
System.out.print(sb.toString());
}
private static void buildStructure(Node node, int depth) {
// 리프 노드까지 모두 순회했으면 종료
if (node.childrenNodes.isEmpty()) {
return;
}
// depth * 2만큼의 '-'를 추가 후 현재 굴의 먹이 정보 추가 -> 자식 노드(아래 층)으로 이동
for (Node child : node.childrenNodes.values()) {
for (int cnt = 0; cnt <= (depth << 1) + 1; cnt++) {
sb.append('-');
}
sb.append(child.food).append('\n');
buildStructure(child, depth + 1);
}
}
static class Node {
String food;
Map<String, Node> childrenNodes;
Node (String food) {
this.food = food;
childrenNodes = new TreeMap<>(); // TreeMap을 사용해 key 값인 먹이 이름 순으로 정렬 유지
}
}
}
