웹서핑을 하다가 신기한 짤을 하나 보게 되었다. 흔히 서울대 애들이 흥분하는 짤이라고 하는데 너무 신기해서 가져와봤다. 간단하게 설명하자면 원에는 1부터 32까지의 수가 중복 없이 들어 있으며, 인접한 두 수를 더하면 제곱수가 된다.
너무 신기하다! 원리가 궁금했다. 그래서 찾아보던 와중 또 신기한 사실을 발견했다.
n=32일 때만 우연하게 가능한 줄 알았는데 32 이상의 자연수면 가능하다고 한다. 어떻게 가능한 건지 수학적으로 증명된 것은 찾지 못했지만.. n이 다른 숫자일 때 정말 가능한지, 가능하다면 그 배열이 어떻게 되는지 궁금했다.
자료를 찾다보니 위의 문제는 해밀턴 순환을 찾는 문제와 같다고 해서 직접 구현해보기로 했다.
해밀턴 순환을 찾는 문제는 그래프와 백트래킹 알고리즘을 이용해서 풀 수 있다. 백트래킹이란 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾는 방법을 의미한다.
이 문제를 풀기 위해선 그래프를 만들어줘야 한다. n개의 노드를 만든 후, 두 개의 노드를 더해서 제곱수가 되는 짝을 찾아 선으로 연결해준다. 아래의 그림은 n=8일 때의 그래프이다.
이걸 코드로 표현하면 아래와 같이 나온다.
// 1, 4, 9, 16, 25, 36, 49, ...
val squareSet: Set<Int> = mutableSetOf<Int>().apply {
var root = 1
while (root * root < 2 * n) {
add(root * root)
root++
}
}
val graph: Array<Set<Int>> = Array(n + 1) { i ->
if (i == 0) return@Array emptySet()
squareSet.asSequence()
.filter { square -> square > i && square - i <= n }
.mapNotNull { square -> (square - i).takeIf { it != i } }
.toSet()
}
squareSet은 n이 몇이냐에 따라대응되는 제곱수의 집합이다. n이 만약 32라면, 제곱수의 집합은 {1, 4, 9, 16, 25, 36, 49}이다. 32 이하의 두 수를 더해서 49 다음 제곱수인 64를 넘을 순 없기 때문이다.
squareSet을 먼저 만들어 준 뒤, 그래프를 만들어준다. Array<Set<Int>> 타입으로 각각의 index는 노드 번호를 뜻하고, 거기에 대응되는 Set은 노드가 연결된 다른 노드들의 집합을 뜻한다.
위에서 만든 그래프를 출력해보면 아래와 같은 로그가 나온다.
node: 1, set: [3, 8, 15, 24]
node: 2, set: [7, 14, 23]
node: 3, set: [1, 6, 13, 22]
node: 4, set: [5, 12, 21, 32]
...
node: 29, set: [7, 20]
node: 30, set: [6, 19]
node: 31, set: [5, 18]
node: 32, set: [4, 17]
그래프까지 다 만들었으면, 이제 백트래킹 알고리즘을 이용해서 해밀턴 순환을 찾아주면 된다.
fun valid(): Boolean = hamiltonian(n, 1)
private val visit = Array(n + 1) { false }
private val path = Array(n + 1) { 0 }
private fun hamiltonian(node: Int, index: Int): Boolean {
if (index == n + 1) {
val start = path[1]
val end = path[n]
// 시작점과 끝나는 지점이 연결되는지 체크
if (graph[start].contains(end)) return true
}
for (i in graph[node]) {
if (visit[i]) continue
visit[i] = true
path[index] = i
val isFinish = hamiltonian(i, index + 1)
if (isFinish) return true
visit[i] = false
path[index] = 0
}
return false
}
n부터 시작해서 경로를 찾아 나선다. 백트래킹 알고리즘에서는 해가 될 것 같지 않으면 그 경로를 더 이상 가지 않고 되돌아가야 한다. 그래야 반복문의 횟수를 줄여서 효율적으로 해를 찾을 수 있다.
이를 위해 방문한 노드를 표시해주기 위해 visit 배열을 사용한다. 방문했던 노드는 visit 처리해줘서 다시 방문 했을 때 건너뛰기를 해준다. 이후 재귀 함수로 해를 찾아준다.
한 가지 포인트는, Amazing circle은 시작했던 노드와 끝나는 노드도 연결되어야 한다는 점이다. 따라서 마지막 끝나는 조건에 시작점과 끝나는 지점이 연결 되어있는지 체크해준다.
전체 코드는 다음과 같다.
class AmazingCircleTest {
class AmazingCircle(private val n: Int) {
private val visit = Array(n + 1) { false }
private val path = Array(n + 1) { 0 }
// 1, 4, 9, 16, 25, 36, 49, ...
private val squareSet: Set<Int> = mutableSetOf<Int>().apply {
var root = 1
while (root * root < 2 * n) {
add(root * root)
root++
}
}
private val graph: Array<Set<Int>> = Array(n + 1) { i ->
if (i == 0) return@Array emptySet()
squareSet.asSequence()
.filter { square -> square > i && square - i <= n }
.mapNotNull { square -> (square - i).takeIf { it != i } }
.toSet()
}
fun valid(): Boolean = hamiltonian(n, 1)
private fun hamiltonian(node: Int, index: Int): Boolean {
if (index == n + 1) {
val start = path[1]
val end = path[n]
// 시작점과 끝나는 지점이 연결되는지 체크
if (graph[start].contains(end)) return true
}
for (i in graph[node]) {
if (visit[i]) continue
visit[i] = true
path[index] = i
val isFinish = hamiltonian(i, index + 1)
if (isFinish) return true
visit[i] = false
path[index] = 0
}
return false
}
}
@Test
fun `1부터 n까지의 수가 있을 때 amazing circle이 되는지 판별하라`() {
val n = 32
val amazingCircle = AmazingCircle(n)
assertTrue(amazingCircle.valid())
}
}
저장된 경로를 프린트 해주면 해밀턴 순환을 알아낼 수 있다.
n=32, path=4 21 28 8 1 15 10 26 23 2 14 22 27 9 16 20 29 7 18 31 5 11 25 24 12 13 3 6 30 19 17 32
n=33, path=3 6 30 19 17 32 4 21 28 8 1 15 10 26 23 2 14 22 27 9 16 33 31 18 7 29 20 5 11 25 24 12 13
n=34, path=2 14 11 25 24 12 13 23 26 10 6 30 19 17 32 4 5 20 29 7 18 31 33 16 9 27 22 3 1 8 28 21 15 34
n=35, path=1 3 6 19 30 34 2 7 18 31 33 16 9 27 22 14 11 25 24 12 13 23 26 10 15 21 28 8 17 32 4 5 20 29 35
n=36, path=13 3 1 8 17 32 4 12 24 25 11 5 20 29 35 14 22 27 9 16 33 31 18 7 2 23 26 10 6 19 30 34 15 21 28 36
n=37, path=12 4 32 17 8 1 24 25 11 5 20 29 35 14 22 3 13 36 28 21 15 34 30 19 6 10 26 23 2 7 18 31 33 16 9 27 37
n=38, path=11 25 24 1 3 33 16 9 7 18 31 5 20 29 35 14 22 27 37 12 13 36 28 8 17 32 4 21 15 10 6 19 30 34 2 23 26 38
n=39, path=10 6 3 22 14 35 29 20 5 11 38 26 23 13 36 28 8 1 15 21 4 32 17 19 30 34 2 7 18 31 33 16 9 27 37 12 24 25 39
n=40, path=9 7 18 31 5 4 32 17 8 1 15 21 28 36 13 12 37 27 22 3 33 16 20 29 35 14 11 38 26 23 2 34 30 19 6 10 39 25 24 40
...