백준 14725번 개미굴 - 스위프트(Swift) 풀이 + 그림 설명

 solved.ac CLASS 6 따려고 시작한 문제인데, 문제 조건에 제대로 명시되지 않은 것이 있어 도대체 무슨 문제인지 헤맸다. 첫 번째 입력 예를 보면서 아래 두 가지 모두 가능하다고 생각했다. 루트-리프로 가는 경로들 만으로는 절대 트리를 하나로 특정할 수가 없는데... 근데 또 정답 비율은 66%나 돼서 나만 이해를 못 하고 있구나 싶었다. 예제 입출력 2개를 한참 보고 나서야 설마 이건가? 하는 규칙을 찾았는데, 트라이 문제인 것 같았다. (너무 오랜만에 PS를 해서 트라이의 존재를 잊고 있었다ㅠㅠ) 풀고 나서 질문/검색에 가보니 https://www.acmicpc.net/board/view/18583 역시나 조건 추가 요청 글이 올라와있었다. 문제 오류가 맞는 것 같다. 66%의 사람들도 아마 문제가 이상하다고 생각하면서도 출제자가 트라이를 원한 것 같으니 트라이로 풀지 않았을까 싶다.

 

 일단 개미굴 그림처럼 트리를 만들어야 한다. 노드 역할의 Room 클래스를 선언해주고, 방에 저장된 먹이 이름을 food, 그리고 자식들을 childRooms라는 프로퍼티로 저장해주었다. 이때 childRooms는 딕셔너리를 써준다. 위의 우측 그림의 A-B-C-D를 처리한 뒤 A-C를 처리한다고 하면, 이미 있는 A노드에다가 C를 자식으로 추가해주어야 하는데, A 노드를 효율적으로 찾기 위해서 배열이 아닌 딕셔너리를 써주었다. depth 프로퍼티는 나중에 설명하겠음!

 addFoodInfo(depth: Int, foodList: [String]) 함수는 현재 노드 아래에 foodList[depth...]를 줄줄이 소시지처럼 달아주는 함수이다. 그림으로 살펴보자. 초기 상태가 아래와 같다.

 

여기서 입구.addFoodInfo(depth: 0, foodList: [“A”, “B”, “C”, “D”]를 호출한다. depth가 0이므로 foodList[0]인 A를 추가할 차례인데, 이미 입구의 자식으로 A(childRooms[A])가 존재하므로 새로 A 노드를 만들 필요가 없다. 

 

 A 아래 남은 줄줄이 B, C, D까지 붙여주어야 한다. 순서대로 다음은 B차례이다. 따라서 depth가 1 커져서 노드 A에 addFoodInfo(depth: 1, foodList: ["A", "B", "C", "D"])를 해준다. 이번에는 B노드가 기존에 없으므로, 새로 만들어주어야 한다! (foodList에서 A는 이제 필요 없지 않나 하는 의문이 들 수 있는데, 앞을 계속 자르면서 쓰는 게 깔끔하지만 슬라이싱도 타임 코스트가 있을 것 같아 그냥 통째로 넘겨주었다.)

 

 계속해서 재귀적으로 C, D까지 붙이면 된다.

 

 이제 depth 설명 차례! 트리를 만들었다고 해서 끝난 것이 아니라 트리를 문제에서 요구하는 형태로 출력해주어야 한다. 왼쪽과 같은 트리가 완성되었다면 오른쪽과 같이 depth에 비례하게 하이픈을 출력해야 한다. 전형적인 DFS 출력이기 때문에 아예 트리 생성 과정에서부터 출력에 필요할 depth를 저장해두었던 것이다.