P92. Scala로 풀어본 Von Koch's conjection

P92 (***) Von Koch's conjecture.

Several years ago I met a mathematician who was intrigued by a problem for which he didn't know a solution. His name was Von Koch, and I don't know whether the problem has been solved since. [The "I" here refers to the author of the Prolog problems. <PMG>]

Anyway the puzzle goes like this: Given a tree with N nodes (and hence N-1 edges), find a way to enumerate the nodes from 1 to N and, accordingly, the edges from 1 to N-1 in such a way, that for each edge K the difference of its node numbers is equal to K. The conjecture is that this is always possible.

For small trees the problem is easy to solve by hand. However, for larger trees, and 14 is already very large, it is extremely difficult to find a solution. And remember, we don't know for sure whether there is always a solution!

Write a function that calculates a numbering scheme for a given tree. What is the solution for the larger tree pictured below?

문제를 간략하게 설명하자면

노드가 N개, 각 노드를 연결한 엣지가 M개 있다고 가정한다. 

각각의 노드는 1부터 N까지의 수 중 하나를 값으로 가지고 있고

두 개의 노드를 연결한 엣지의 값은 양 노드 값 차이의 절대값이라고 하자.

이 때, 엣지들이 중복없이 1부터 M까지의 값을 가지게 되는 경우를 찾는 문제다.

비슷한 내용을 Graceful-labeling이라는 내용으로 위키백과에서 볼 수 있다.

Graceful labeling은 노드의 수에 따라 해결할 수 있는 시간이 불규칙적으로 변하는 NP문제라고 한다.

이 문제는 사이클이 없어 트리로 볼 수 있으므로 더 쉽게 풀 수 있지만 그래도 충분히 어렵다.

늘 그렇듯 이 문제에 대해 생각해 보자.

ㄱ. 문제에서 주어지는 그래프는 하나의 노드를 루트로 하는 트리로 볼 수 있다. 트리로 본 예제1 이 문제는 Knight's tour같은 문제와 다르게 한번 방문한 노드에 다시 방문해야 한다. 차일드 노드에 값을 할당하고 남은 값을 이용해 다른 차일드 노드에 값을 할당해야 하기 때문이다. 따라서 이전 방문했던 노드를 기억해야 하는데, 하나의 노드를 잡아 위로 들어 올려 구조 자체를 트리로 구성한다면 부모 노드라는 개념으로 이전 노드를 더 쉽게 파악할 수 있다. 하지만 그래프에 사이클이 있다면 트리로 생각할 수 없을 것이고, 부모 대신 방문한 노드의 순서를 이용해 상위 노드로 돌아가야 할 것이다. ㄴ. 값의 할당은 트리 순회로 할 수 있다. 1) 문제의 그래프를 트리로 바꾸었을 때, 차일드 노드의 수가 일정하지 않아 in-order는 고려하기 어렵다. 2) post-order를 사용한다면 차일드 노드의 값을 할당 한 후 다시 부모 노드로 돌아와야 한다. 하지만 차일드 노드에 방문할 때마다 경우의 수가 기하급수적으로 증가하므로 post-order는 적합하지 않다. 답의 수가 명확하지 않은 이상 Stream을 사용해야 할 것이고, 그 특성상 경우의 수가 많을수록 StackOverFlow가 발생하기 쉽다. ※ 결과적으로 Pre-order, 부모 노드에 값을 할당한 후 자식 노드로 이동하는 형식을 택했다. ㄷ. 문제 그래프는 순차적으로 선언할 수 없다. 노드의 차일드 노드들은 관계는 순차적으로 선언할 수 없는 형태다. 따라서 노드간의 관계를 lazy하게 선언하거나 mutable 콜렉션을 이용해 노드들을 만든 후  차일드 노드로 추가하는 방법을 사용해야 한다.  () => (...) 형태로 사용하는 스칼라의 Thunk(자바8에서의 Supplier) 함수를 사용하면 실행까지 선언을 미룰 수 있으므로 익숙한 List를 그대로 사용할 수 있다.

이 문제는 다른 문제들보다 더 많은 경우의 수를 가지고 더 복잡한 조건을 가진다. 

때문에 StackOverFlow 방지와 더 빠른 실행 시간을 위해 경우의 수를 줄이기 위한 몇 가지 룰을 더 생각해 보자.

1. 다음 노드로 이동할 때, 노드 중 차일드를 가장 적게 가진 노드로 우선해서 이동한다. Knight's tour 문제에서 보았던 Warndorff's Rule과 마찬가지로 이렇게 이동함으로써 생기는 경우의 수를 크게 줄일 수 있다. 차일드가 많을 수록 차일드들이 가질 수 있는 값이 많아지고, 그에 따라 경우의 수가 급격하게 증가하기 때문이다. 2. 루트 노드는 작은 값, 엣지는 큰 값부터 할당한다. 엣지가 가장 큰 값을 가질 수 있는 경우는 노드의 값이 가장 작을 때 뿐이다. 다시 말하자면, 노드의 값이 커질수록 엣지의 값은 작아져야 한다. 따라서 루트 노드에 작은 값부터, 엣지는 큰 값부터 할당함으로써  가장 작은 값과 가장 큰 값이 인접하게 되고, 정답의 가능성을 높인다. (정확히는 가장 작은 값과 가장 큰 값이 인접하지 않으면 절대 정답이 될 수 없다.)

스칼라로 구현한 코드는 아래와 같다.

/**
  * @since 2017-02-02
  */
class Von_Koch {

  /** 노드
    * @param name   노드의 이름
    * @param parent 연결된 부모노드
    * @param child  연결된 자식노드
    */
  case class Node(name: String, parent: Option[Node], child: () => List[Node]) {
    override def toString: String = name
  }

  // 문제 그래프 선언
  val nodeA: Node = Node("A", None, () => List(nodeG, nodeI, nodeH, nodeB, nodeC))
  val nodeG: Node = Node("G", Some(nodeA), () => Nil)
  val nodeI: Node = Node("I", Some(nodeA), () => Nil)
  val nodeH: Node = Node("H", Some(nodeA), () => Nil)
  val nodeB: Node = Node("B", Some(nodeA), () => Nil)
  val nodeC: Node = Node("C", Some(nodeA), () => List(nodeD, nodeF, nodeE))
  val nodeF: Node = Node("F", Some(nodeC), () => Nil)
  val nodeD: Node = Node("D", Some(nodeC), () => List(nodeK))
  val nodeK: Node = Node("K", Some(nodeD), () => Nil)
  val nodeE: Node = Node("E", Some(nodeC), () => List(nodeQ))
  val nodeQ: Node = Node("Q", Some(nodeE), () => List(nodeM, nodeN))
  val nodeM: Node = Node("M", Some(nodeQ), () => Nil)
  val nodeN: Node = Node("N", Some(nodeQ), () => List(nodeP))
  val nodeP: Node = Node("P", Some(nodeN), () => Nil)

  val firstStack: List[Log] = {
    val nodes = (1 to 14).toList
    val edges = (13 to 1 by -1).toList
    nodes.map(v => Log(nodeA, nodes.filterNot(_ == v), edges, Map(nodeA -> v)))
  }

  /** 계산 과정을 가지고 있는 로그
    *
    * @param node      현재 노드
    * @param nodeValue 노드에 할당 가능한 값들
    * @param edgeValue 엣지에 할당 가능한 값들
    * @param logMap    지금까지 노드에 할당한 값들
    */
  case class Log(node: Node, nodeValue: List[Int], edgeValue: List[Int], logMap: Map[Node, Int])

  /**
    * 다음 노드에 할당 가능한 값을 구하는 메소드
    * 엣지 값을 선택하면 현재 노드의 값에 엣지 값을 더하거나 뺀 값이
    * 다음 노드에 할당 가능하다는 점을 이용함.
    *
    * @param value      현재 노드의 값
    * @param nodeValues 노드에 할당 가능한 값들
    * @param edgeValues 엣지에 할당 가능한 값들
    * @return (엣지에 할당한 값, 다음 노드에 할당 가능한 값)의 리스트
    */
  private def nextNodeValues(value: Int, nodeValues: List[Int], edgeValues: List[Int]): List[(Int, List[Int])] =
    edgeValues.map{ edgeValue =>
      (edgeValue, nodeValues.intersect(List(value + edgeValue, value - edgeValue))) }

  /**
    * 다음 노드에 할당 가능한 값들을 찾아 다음 노드의 값을 할당하고
    * 그 노드로 이동한 Log들을 만들어내는 메소드
    *
    * @param nextNode      다음 노드
    * @param thisNodeValue 현재 노드의 값
    * @param nodeValue     노드에 할당 가능한 값
    * @param edgeValue     엣지에 할당 가능한 값
    * @param logMap        지금까지 노드에 할당한 값들
    * @return 새로운 Log의 리스트
    */
  private def getNewStack(nextNode: Node, thisNodeValue: Int, nodeValue: List[Int],
                          edgeValue: List[Int], logMap: Map[Node, Int]): List[Log] =
    for {nextValue     <- nextNodeValues(thisNodeValue, nodeValue, edgeValue)
         nextNodeValue <- nextValue._2} // 다음 노드에 할당 가능한 값
      yield Log(nextNode,
                nodeValue.filterNot(_ == nextNodeValue),
                edgeValue.filterNot(_ == nextValue._1),
                logMap + (nextNode -> nextNodeValue))
    // 할당한 노드, 엣지 값을 제외한 가능한 값들, 할당한 값을 추가한 맵으로 이루어진
    // 새로운 Log들을 만든다.


  /**
    * @param stack 경우의 수를 쌓은 스택
    * @return Map[Node, Int] 형태의 답
    */
  def solve(stack: List[Log] = firstStack): Stream[Map[Node, Int]] = stack match {
    case Log(node, nodeValue, edgeValue, logMap) :: t =>
      if (nodeValue.isEmpty && edgeValue.isEmpty) logMap #:: solve(t) // 모든 값을 할당한 경우 - 답
      else {
        val unvisitedChild = node.child().sortWith(_.child().size < _.child().size)
                                         .filterNot(logMap.keySet.contains)
        if (unvisitedChild.isEmpty) // 방문할 자식노드가 없으면 부모노드로 돌아감
          solve(Log(node.parent.get, nodeValue, edgeValue, logMap) :: t)
        else // 방문할 자식노드가 있으면 그 노드로 이동
          solve(getNewStack(unvisitedChild.head, logMap(node), nodeValue, edgeValue, logMap) ::: t)
      }
    case Nil => Stream.empty
  }

}

nextNodeValues 메소드는 현재 노드의 값이 있을 때 엣지의 값을 정하면 현재 노드의 차일드 노드의 값은 

(현재 노드의 값 + 엣지의 값 or 현재 노드의 값 - 엣지의 값)과 노드에 할당 가능한 값의 교집합이라는 점을 이용해 차일드 노드에 할당할 수 있는 값의 리스트를 구하는 메소드다.

getNewStack 메소드는 차일드 노드에 할당 가능한 값들을 이용해 그 노드에 값을 할당했을 경우의 Log들을 만들어 내는 메소드다. 차일드 노드에 더 이상 할당할 수 있는 값이 없으면 Nil이 리턴된다.

이 두 메소드를 이용해 차일드 노드에 값을 할당하고 Log들을 만들어 쌓아가며 답을 구한다.

Option으로 선언된 노드의 부모 노드나 Map에서의 get의 예외처리는 조금이라도 더 알아보기 쉽게 생략했다.

사실 발생 할 수 있는 예외가 아니기도 하다.