소개
Toyland에서는 기차들이 온 도시에 보물을 배달하느라 항상 바빠요. 반짝이는 구슬부터 희귀한 블록까지 말이죠.
기차가 달리는 선로는 알록달록한 도미노 모양 조각으로 되어 있고, 조각마다 두 개의 숫자가 적혀 있어요.
기차가 움직이려면 도미노 조각들이 숫자가 서로 맞는 완벽한 사슬을 이루어야 해요.
오늘은 희귀한 장난감의 긴급 배송이 보류되어 있어요.
살펴봐야 할 선로 조각 한 세트를 건네받았죠.
이 조각들이 끊김 없이 이어지는 사슬을 만들 수 있다면, 기차는 곧 출발해 Toyland 곳곳에 웃음을 전할 거예요.
그렇지 않으면 이 세트는 버려지고, 다른 세트로 다시 시도하게 돼요.
장난감들이 이 퍼즐을 풀어 주기를 손꼽아 기다리고 있어요.
도미노가 선로를 이어 기차를 굴려 보낼 수 있을까요? 아니면 이 세트는 그대로 남겨질까요?
지침
도미노 사슬을 만들어요.
주어진 도미노 타일들을 올바른 도미노 사슬이 되도록 순서를 정하는 방법을 계산해요.
사슬에서 한 타일의 한쪽 면에 있는 점은 이웃한 타일의 맞닿은 면에 있는 점과 일치해야 해요.
또한 이웃이 없는 타일, 즉 첫 번째와 마지막 타일의 면에 있는 점은 서로 일치해야 해요.
예를 들어 타일 [2|1], [2|3], [1|3]이 주어지면 [1|2] [2|3] [3|1]이나 [3|2] [2|1] [1|3], [1|3] [3|2] [2|1] 등과 같이 계산해야 하는데, 여기서 첫 번째와 마지막 숫자가 같아요.
타일 [1|2], [4|1], [2|3]의 경우 만들어지는 사슬은 유효하지 않아요. [4|1] [1|2] [2|3]의 첫 번째와 마지막 숫자가 같지 않아요.
4 != 3
일부 테스트 케이스는 사슬 해법에 중복된 타일을 사용할 수 있어요. 이 경우 여러 개의 도미노 세트를 사용한다고 가정해요.
구현
도미노 슬라이스를 받아 올바른 도미노 사슬을 만들려고 시도하는 Go 함수 MakeChain 하나를 정의해요.
MakeChain의 시그니처는 다음과 같아요:
type Domino [2]int
func MakeChain(input []Domino) (chain []Domino, ok bool)
ok 불리언 결과는 주어진 입력 도미노 목록을 올바른 사슬로 배열할 수 있는지를 나타내요.
입력 목록이 비어 있는 것도 올바른 것으로 간주하고, 양쪽 면이 같은 도미노 하나도 올바른 것으로 간주해요.
'chain' 결과는 올바른 사슬을 보여 주는 순서로 배열된 0개 이상의 도미노 슬라이스예요.
'input'의 도미노는 사슬에서 이웃한 도미노와 각 면이 맞도록 회전해야 할 수도 있는데, 이는 허용되며 (오히려 예상되는 일이에요).
사슬의 처음과 끝에 있는 도미노는 바깥쪽 면도 서로 맞아야 해요.
주어진 입력 도미노 슬라이스를 올바른 사슬로 배열할 수 없다면 MakeChain은 chain 결과로 nil을 반환해도 되지만, ok 결과로는 반드시 false를 반환해야 해요.
주어진 입력 목록에 대해 올바른 사슬 배열이 여러 개 있을 수 있으므로, ok가 true일 때 테스트 프로그램은 사슬의 유효성만 검사해요.
