문제 설명
라이캣은 배 위에서 만난 개리의 능력을 시험해 보았습니다. 개리는 기꺼이 시험에 응했고, 무사히 통과했죠.
시간이 흘러 일행은 드디어 제주도에 도착했습니다. 제주도는 생각보다 훨씬 넓어서, 끝에서 끝까지 걸어가려면 일주일이나 걸릴 정도였어요. 단서를 찾기 위해 무작정 돌아다니기에는 너무나 넓은 곳이었습니다.
"파이와 썬이 이곳에 와서 무슨 생각을 했을까냥?" "어떤 단서를, 어디다 두어야 할지 고민했겠지. 개굴!" "만약 내가 파이와 썬이라면, '어쩌다' 찾을 수 있는 곳에 단서를 놓지 않았을 것 같다냥."
잠시 후, 자바독이 생각에 잠겨 혼잣말을 했어요.
"우리가 가진 단서가 있독. 알고리즘, 보물, 파이, 썬, 제주. 제주가 가진 알고리즘, 제주의 보물..."
그 순간, 세 명이 동시에 외쳤습니다. "제주의 보물!"
라이캣과 일행들은 제주의 유명 관광지를 돌아다니며 단서를 찾기 시작했습니다. 만장굴, 정방폭포, 성산일출봉, 한라산 등을 둘러보았죠. 그러던 중 '아부 오름'에서 특이한 돌탑을 발견했습니다.

바람이 많이 부는 제주에서는 돌탑의 형상을 유지하기 쉽지 않아 하층부터 견고히 쌓는 것이 일반적이었어요. 그런데 발견한 돌탑은 틈새가 많아 태풍을 만나면 그대로 무너질 것 같았어요. 그럼에도 무너지지 않았다는 것은, 인위적인 힘이 가해졌다고 밖에 볼 수 없는 것이죠.
"모두 이리로 와봐라냥. 단서를 찾았다냥!"
단서를 찾았다는 라이캣의 말에 모두가 모여들었습니다.

"그래서 그 단서가 무엇이지? 개굴!" "이 돌들의 그림자를 자세히 보라냥!"
라이캣의 말대로 그림자를 자세히 보니 바위 틈 사이로 빛이 통과한 곳에 작은 원들이 그려진 것을 볼 수 있었습니다.
"하지만 저 모양으로는 아무 단서도 발견할 수 없다독. 활용할 수 있는 데이터가 너무 적다독." "저 모양을 보고 떠오르는 것이 없냥?" "트리!"
자바독과 개리가 동시에 외쳤어요. 그렇지만 자바독이 말한 것처럼 활용할 수 있는 데이터가 너무 적었습니다. 모두가 라이캣이 더 설명해주길 기다렸어요.
"우리가 활용할 수 있는 것은 그림자, 빛, 빛 간의 거리, 그리고 알고리즘이다냥. 트리의 알고리즘이 많지 않으니, 모두 시도해보고 유의미한 데이터가 뽑히는 알고리즘을 사용해보면 된다냥!"
라이캣은 각 간선 사이의 길이 비율이 오후까지 변하지 않는다는 사실을 알아냈습니다. 처음 선의 비율이 1이라고 했을 때, 모든 선의 비율은 아래와 같습니다.

라이캣은 이 선의 비율에 100을 곱하여 노드를 완성하였어요.

- 그림자의 길이 비율이 데이터였습니다. 해당 데이터는 트리의 형태를 갖추고 있으며, 각 간선은 아래와 같이 표현됩니다.
graph = {100: set([67, 66]),
67: set([100, 82, 63]),
66: set([100, 73, 69]),
82: set([67, 61, 79]),
63: set([67]),
73: set([66]),
69: set([66, 65, 81]),
61: set([82]),
79: set([82, 87, 77]),
65: set([69, 84, 89]),
81: set([69]),
87: set([79, 31, 78]),
77: set([79]),
84: set([65]),
89: set([65]),
31: set([87]),
78: set([87])}
- 노드 100에서 출발해, 지금 노드와 이어진 노드 가운데 아직 지나지 않은 노드 중 가장 작은 값으로 한 칸씩 내려갑니다. 더 내려갈 노드가 없으면 멈춥니다. 이렇게 지나간 값들(출발점 100은 빼고)이 '작은 값' 경로입니다. 같은 방법으로 가장 큰 값을 골라 내려간 값들이 '큰 값' 경로입니다.
- 이를 통해 나온 값들을 모두 유니코드에서 문자로 찾아 그 문자들을 합쳐서 반환해주세요. 합칠 때에는 큰 값 경로의 문자열, 띄어쓰기 한 칸, 작은 값 경로의 문자열 순서로 합쳐 주세요. 예를 들어 작은 값 경로가 'hello', 큰 값 경로가 'world'라면 'world hello'를 반환합니다.
제한 사항
- 입력은 위 예시처럼 노드 번호를 키로, 이어진 노드 번호의 집합을 값으로 하는 딕셔너리이며, 항상 노드 100이 들어 있는 트리입니다.
- 그래프의 노드 값은 모두 양의 정수입니다.
- 그래프의 노드 수는 최소 3개, 최대 100개입니다.
- 각 노드의 값은 1 이상 100 이하입니다.
- 결과로 반환되는 문자열의 길이는 1 이상 10 이하입니다.
입출력 예
| 입력 | 출력 |
|---|---|
| 문제에 주어진 그래프 | "CROWN BEAT" |
입출력 설명
-
주어진 그래프에서 깊이 우선 탐색으로 큰 값만을 선택하며 탐색합니다. 100 -> 67 -> 82 -> 79 -> 87 -> 78
-
이 값들을 유니코드 문자로 변환합니다.
- 67 -> 'C'
- 82 -> 'R'
- 79 -> 'O'
- 87 -> 'W'
- 78 -> 'N'
-
변환된 문자들을 순서대로 이어 붙여 "CROWN"을 얻습니다. 같은 방식으로 작은 값을 탐색하여 "BEAT"를 얻습니다. 이 두 개의 문자열을 띄어쓰기로 합쳐 "CROWN BEAT"를 반환합니다.
예시 테스트
| # | 입력 | 기대값 |
|---|---|---|
| 1 | {"31": [87], "61": [82], "63": [67], "65": [69, 84, 89], "66": [100, 69, 73], "67": [100, 63, 82], "69": [65, 66, 81], "73": [66], "77": [79], "78": [87], "79": [77, 82, 87], "81": [69], "82": [61, 67, 79], "84": [65], "87": [31, 78, 79], "89": [65], "100": [66, 67]} | "CROWN BEAT" |
| 2 | {"70": [80], "75": [90], "80": [100, 70, 95], "85": [90], "90": [100, 75, 85], "95": [80], "100": [80, 90]} | "ZU PF" |
| 3 | {"67": [70], "70": [67, 73, 80], "72": [75], "73": [70], "75": [72, 78, 90], "78": [75], "80": [100, 70, 95], "82": [85], "85": [82, 88, 90], "88": [85], "90": [100, 75, 85], "92": [95], "95": [80, 92, 98], "98": [95], "100": [80, 90]} | "ZUX PFC" |
입력은 solution에 넘기는 인자예요. 제출하면 숨김 테스트 8개도 함께 채점해요.