행복의 비결이 개미가 사는 개미굴에 있다고 생각한 윤수는 개미굴의 구조를 알아보기 위해 로봇 개미를 만들었다. 로봇 개미는 센서가 있어 개미굴의 각 층에 먹이가 있는 방을 따라 내려가다 더 이상 내려갈 수 없으면 그 자리에서 움직이지 않고 신호를 보낸다. 이 신호로 로봇 개미는 개미굴 각 층을 따라 내려오면서 알게 된 각 방에 저장된 먹이 정보를 윤수한테 알려줄 수 있다.
로봇 개미 개발을 완료한 윤수는 개미굴 탐사를 앞두고 로봇 개미를 테스트 해보기 위해 위 그림의 개미굴에 로봇 개미를 투입했다. 로봇 개미의 수는 각 개미굴의 저장소를 모두 확인할 수 있을 만큼 넣는다.
다음은 로봇 개미들이 윤수에게 보내준 정보다.
KIWI BANANA KIWI APPLE APPLE APPLE APPLE BANANA KIWI 공백을 기준으로 왼쪽부터 순서대로 로봇 개미가 각 층마다 지나온 방에 있는 먹이 이름을 뜻한다.
윤수는 로봇 개미들이 보내준 정보를 바탕으로 다음과 같이 개미굴의 구조를 손으로 그려봤다.
APPLE --APPLE --BANANA ----KIWI KIWI --APPLE --BANANA 개미굴의 각 층은 "--" 로 구분을 하였다. 또 같은 층에 여러 개의 방이 있을 때에는 사전 순서가 앞서는 먹이 정보가 먼저 나온다.
... (중략) ... 행복의 비결을 알기 위해 윤수를 도와 개미굴이 어떤 구조인지 확인해보자.
✔️ 소요된 시간
35분
✨ 수도 코드
문제에 제시된 그림이 너무 트리의 형태를 나타내고 있어서 바로 트리를 활용해야겠다는 생각을 했습니다 😅 다만 이진 트리가 아니라 자식 노드로 여러개가 올 수 있다는 점, 그리고 자식 노드를 먹이 알파벳 순으로 보여줘야 한다는 점에 주의했습니다!
자식으로 여러개가 올 수 있기 때문에 자식을 list로 관리해야겠다고 생각했습니다
data class Node(
var feed: String, // 먹이
var nodes: MutableList<Node>
)
그래서 이렇게 노드 정보에 먹이 이름과 자식을 저장할 리스트를 설정해줬습니다
문제에 제시된 예제로 설명을 하자면, 아래 그림과 같이 저장이 된다고 볼 수 있습니다
🤔 입력 데이터를 어떻게 그림과 같은 구조로 정리할 수 있을까요?
부모 노드의 자식에 해당 먹이가 있는지 확인한다
없다면 추가한다
현재 먹이가 부모가 되고 위 과정을 반복한다
저는 개미가 지나온 경로의 입력 정보마다 위 과정을 반복해서 트리 구조로 정리를 해줬습니다. 최상위의 개미굴 입구를 root로 두고, 입력 순서대로 자식 노드를 추가해준 것입니다!
Tree로 정리된 정보를 출력 형식에 맞춰서 정리
개미굴 입구, 즉 root 노드 정보는 출력할 필요가 없기 때문에 그 아래 노드부터 탐색을 해줍니다. 단, 알파벳 순으로 출력을 해야하기 때문에 자식 노드를 정렬하고, 전위순회 방식하면서출력 데이터를 정리할 수 있었습니다
✅ 최종 코드
// 4차시 2024.07.27.토 : 백준 - 개미굴(14725)
import java.io.BufferedReader
import java.io.InputStreamReader
import java.util.StringTokenizer
const val DEPTH_STRING = "--"
data class Node(
var feed: String, // 먹이
var nodes: MutableList<Node>
)
var answer: StringBuilder = StringBuilder()
fun main() {
val br = BufferedReader(InputStreamReader(System.`in`))
val N = br.readLine().toInt()
val root = Node("", mutableListOf())
for(i: Int in 1..N) {
val st = StringTokenizer(br.readLine())
val num = st.nextToken().toInt()
// 트리로 정리
var parent = root
for(j: Int in 1..num) {
val currentFeed = st.nextToken()
var index = -1
// 부모 노드에 이미 존재하는지 확인
for(k: Int in 0..parent.nodes.size - 1) {
if(parent.nodes[k].feed.equals(currentFeed)) {
index = k
break
}
}
// 존재하지 않을 경우 자식으로 추가
if(index == -1) {
parent.nodes.add(Node(currentFeed, mutableListOf()))
index = parent.nodes.size - 1
}
// 다음 자식을 체크하기 위해 depth 증가
parent = parent.nodes[index]
}
}
root.nodes.sortBy{ it.feed } // 자식 노드를 먹이 이름 기준으로 오름차순 정렬
for(node in root.nodes) {
tree(node, "") // depth 1
}
print(answer)
}
fun tree(current: Node, depth: String) {
answer.append(depth).append(current.feed).append("\n")
current.nodes.sortBy{ it.feed } // 자식 노드를 먹이 이름 기준으로 오름차순 정렬
for(node in current.nodes) {
tree(node, depth + DEPTH_STRING) // Depth 증가시켜주고 자식 노드도 탐색
}
}
📚 새롭게 알게된 내용
ps. 이번 차시에는 다른 일정 때문에 문제를 풀 시간이 부족해서 정답률 높은 문제를 선택했는데, 다음 문제는 좀 더 시간과 고민이 많이 필요한 문제를 풀어보려고 합니다!
