14725-개미굴 Swift

문제

개미는(뚠뚠) 오늘도(뚠뚠) 열심히(뚠뚠) 일을 하네.

개미는 아무말도 하지 않지만 땀을 뻘뻘 흘리면서 매일 매일을 살길 위해서 열심히 일을 하네.

한 치 앞도(뚠뚠) 모르는(뚠뚠) 험한 이 세상(뚠뚠) 그렇지만(뚠뚠) 오늘도 행복한 개미들!

우리의 천재 공학자 윤수는 이 개미들이 왜 행복한지 궁금해졌다.

행복의 비결이 개미가 사는 개미굴에 있다고 생각한 윤수는 개미굴의 구조를 알아보기 위해 로봇 개미를 만들었다.

로봇 개미는 센서가 있어 개미굴의 각 층에 먹이가 있는 방을 따라 내려가다 더 이상 내려갈 수 없으면 그 자리에서 움직이지 않고 신호를 보낸다.

이 신호로 로봇 개미는 개미굴 각 층을 따라 내려오면서 알게 된 각 방에 저장된 먹이 정보를 윤수한테 알려줄 수 있다.

로봇 개미 개발을 완료한 윤수는 개미굴 탐사를 앞두고 로봇 개미를 테스트 해보기 위해 위 그림의 개미굴에 로봇 개미를 투입했다. 로봇 개미의 수는 각 개미굴의 저장소를 모두 확인할 수 있을 만큼 넣는다.

다음은 로봇 개미들이 윤수에게 보내준 정보다.

• 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를 만족한다. 먹이 정보는 알파벳 대문자로만 이루어져 있다.

출력

개미굴의 시각화된 구조를 출력하여라.

개미굴의 각 층을 "--" 로 구분하며, 같은 층에 여러개의 방이 있을 때에는 사전 순서가 앞서는 먹이 정보가 먼저 나온다.

최상위 굴을 포함하여 하나의 굴에서 개미굴이 여러개로 나뉠 때 먹이 종류별로 최대 한 번만 나올 수 있다.

내가 푼 풀이

 접근방법: 트라이 자료구조

이전에 트라이 자료구조를 사용할 땐, 문자열의 문자 하나하나 찾아가며 일치하는지 판단했었는데

조금 변형하여, 문자열을 하나하나 판단후, 마지막 문자열까지 도달하여 출력하는 방향으로 바꾸었다.

같은 층에서 다른곳으로 트리처럼 나누어질수 있으므로, 입력순서가 같은 두 문자열은 같은 방으로 취급한다.

위 예시그림이 트리형태로 되어있는데 트라이 자료구조가 바로 저그림과 유사하다.

트라이 구조를 구현하고 문제풀이에 맞게 바꾸어주고 출력

 

코드로 구현하면 다음과 같다.

import Foundation

// 트라이 자료구조
class Tries {
    // 문자열과, 다음 자식노드를 저장할 Dictionary 구현
    var child: [String: Tries] = [:]
    // 해당 정보의 마지막 문자인가 판단하는 변수지만 이 문제 해답을 구하기 위해선 사용하진 않았다.
    var end = false
    
    // 트라이 자료구조에 입력
    // arr: 정보로 얻은 문자열의 배열
    // currentIndex: 현재 인덱스(그림에서의 트리 깊이(depth)), idx: arr의 크기
    func insert(_ arr: [String],_ currentIndex: Int,_ idx: Int) {
        // 주어진 문자열배열을 모두 넣었다면 종료
        if currentIndex == idx {
            self.end = true
            return
        }
        // 해당 문자열이 처음 입력되는거라면 자식노드 만들어서 생성
        // 이미 만들어졌다면 통과
        if child[arr[currentIndex]] == nil {
            child[arr[currentIndex]] = Tries()
        }
        // 만들어진 자식노드를 통해서 그 다음 주어지는 문자열을 넣는다.
        child[arr[currentIndex]]!.insert(arr, currentIndex+1, idx)
    }
    
    // 트라이 구조에서 저장된 모든 노드의 문자열 출력
    func find(_ idx: Int) {
        // 같은 깊이라면 사전순으로 출력하기위해 오름차순
        var arr = Array(self.child.keys).sorted{ $0 < $1 }
        // 깊이를 의미하는 문자
        // 깊은만큼 "--" 추가
        var answer = ""
        for i in 0..<idx {
            answer += "--"
        }
        // 해당 깊이의 모든 문자열을 출력한다.
        // 문자열의 자식노드가 존재하면 재귀호출로 출력
        for i in arr {
            print("\(answer)\(i)")
            child[i]!.find(idx+1)
        }
    }
}

// 생성, 입력
var trie = Tries()
let N = Int(readLine()!)!

// 주어진 정보들을 모두 트라이구조에 넣는다.
for i in 0..<N {
    let info = readLine()!.split(separator: " ").map{String($0)}
    let foods = info[1..<info.count].map{String($0)}
    trie.insert(foods, 0, foods.count)
}
// 출력
trie.find(0)