백준 개미굴(14725)

개미굴

1. 힌트

1) 명시되지는 않았지만 주어진 그래프는 트리입니다.

2) 자식들에 대한 참조를 가지고 있는 노드를 정의하고, 우선순위 큐를 사용하여 자식들을 오름차순으로 유지하게 할 수 있습니다.

3) $K$개의 먹이 정보들을 토대로 트리에 삽입합니다. 문제에 명시되지는 않았지만 어떤 노드의 자식들간에는 이름이 중복되는 경우가 없습니다. $S[i]$번째 먹이 정보가 이미 존재하면 해당 노드로 이동하고 그렇지 않다면 새로운 노드를 생성합니다.

2. 접근

1) 트리

문제에 명시되지는 않았지만 로봇 개미는 무조건 내려가기만 한다는 점에서 개미굴이 트리 형태임을 짐작할 수 있습니다.
로봇 개미들이 보내준 정보를 토대로 트리를 만들어야하므로 트리를 구현해줍시다. 트리는 각 자식노드들에 대한 참조를 가지고 있는 노드로 구현하면 간편합니다.

2) 트리의 출력

노드에서 단순한 리스트로 자식들에 대한 참조를 지니고 있어도 되지만, 같은 층에 여러개의 방이 있을 때에는 오름차순으로 출력해야하므로 우선순위큐를 자식들을 저장해서 간편하게 구현해줍시다.

3) 트리의 삽입

$K$개의 먹이 정보가 주어졌을 때, 이를 트리에 삽입하면서 트리를 구성해줄 수 있습니다. 트리는 재귀적인 형태를 띄므로 재귀적으로 구현해줍시다.
개미굴의 입구(루트)에서 시작하면서 만약 현재 노드의 자식들 중에 어떤 먹이 정보 $S[i]$가 존재하지 않는다면 새로운 자식 노드를 생성해주고 재귀호출하고, 존재한다면 해당 노드로 다시 재귀호출하는 식으로 구현할 수 있습니다.
물론 자식 노드들 중에 같은 이름을 가진 경우가 있을 수도 있습니다만, 이 문제에서 그러한 경우는 없는 것으로 추측됩니다.

3. 구현

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder bw = new StringBuilder();
		Node root = new Node("");
		int N = Integer.parseInt(br.readLine());
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			int K = Integer.parseInt(st.nextToken());
			String[] S = new String[K];
			for (int j = 0; j < K; j++) S[j] = st.nextToken();
			root.insert(-1, S);
		}
		root.print(0, bw);
		System.out.print(bw);
	}

}
class Node implements Comparable<Node> {
	String name;
	PriorityQueue<Node> children;
	
	Node(String n) { name = n; children = new PriorityQueue<>(); }
	
	// 이 노드를 루트로 하는 서브트리에 S[i + 1:]을 삽입
	void insert(int i, String[] S) {
		if (i == S.length - 1) return;
		for (Node ch : children) if (ch.name.equals(S[i + 1])) {
			ch.insert(i + 1, S);
			return;
		}
		Node t = new Node(S[i + 1]);
		t.insert(i + 1, S);
		children.offer(t);
	}
	
	void print(int i, StringBuilder bw) {
		while (!children.isEmpty()) {
			for (int t = 0; t < i; t++) bw.append("--");
			Node ch = children.poll();
			bw.append(ch).append("\n");
			ch.print(i + 1, bw);
		}
	}
	
	@Override
	public String toString() { return name; }
	
	@Override
	public int compareTo(Node o) { return name.compareTo(o.name); }
	
}