P94. Scala로 만들어본 K-regular simple graph(정규 그래프)

P94 (***) Generate K-regular simple graphs with N nodes.

In a K-regular graph all nodes have a degree of K; i.e. the number of edges incident in each node is K. How many (non-isomorphic!) 3-regular graphs with 6 nodes are there?

노드의 갯수 N, 각 노드의 엣지 갯수 K를 입력받아 정규 그래프를 만드는 문제다.

정규 그래프(Regular graph)란 각 노드가 동일한 갯수의 엣지를 가지는 그래프로 각 엣지는 다른 노드와 연결된다.

노드와 엣지 갯수에 따른 정규 그래프들

 

 

 정규 그래프를 그려보면 몇 가지 간단한 규칙을 찾을 수 있다.

1. k는 n보다 작거나 같아야 한다.  2. n * k가 짝수일때만 답이 존재한다.  3. 전체 엣지 수는 n * k / 2개다.

엣지의 규칙에 대해서도 생각해 보자.

n = 5, k =2 정규 그래프 중 하나

위의 그림에서 엣지는 [1 - 2], [2 - 3], [3 - 4], [4 - 5], [5 - 1]로 총 다섯개다.

이 엣지들에서 언급되는 노드를 적어보면

[1, 2, 2, 3, 3, 4, 4, 5, 5, 1], 순서대로 다시 적어보면

[1, 2, 3, 4, 5, 1, 2, 3, 4, 5]로 노드의 목록이 두 번 반복 되었음을 알 수 있다.

사실 당연하다. 각 노드는 k개의 엣지를 가져야 하고, 엣지는 노드 둘의 연결이기 때문이다.

결과적으로

k 정규 그래프의 모든 엣지를 나열하면 노드의 목록이 k번 반복된다는 사실을 알 수 있다.

이 말을 다시 하자면, 노드의 목록을 k번 반복하여 두 개의 노드씩 짝짓는다면(당연히 자기 자신은 제외하고)

정규 그래프의 엣지들을 만들 수 있다는 것이다.

위 그림과 같이 k번 반복된 노드들을 두개씩 짝지어 엣지들을 만들 수 있다.

여기서 추가적으로 고려해야 할 것은

엣지의 방향과 순서는 고려할 필요가 없다는 점이다. (엣지 [2 - 1]와 엣지 [1 - 2]는 같다.  엣지들 ([1 - 2], [2 - 3])과 ([2 - 3], [1 - 2])는 같다.)

중복을 허용하지 않는 콜렉션인 Set과 equals/hashCode 메소드 혹은 생성자를 이용하면 두 가지는 너무 간단하게 해결할 수 있다.

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

/** 
  * @param value 노드 - 노드의 튜플.
  */
case class Edge(var value: (Int, Int)){
  if(value._1 > value._2) value = value.swap
  override def toString: String = s"[${value._1}-${value._2}]"
}

/**
  * @param n 노드의 갯수
  * @param k 각 노드가 가지는 엣지의 갯수
  * @param lst 노드 목록. 노드 목록은 1 to n이 k번 반복된 값.
  * @param edges 그래프의 엣지들
  * @return 정규 그래프
  */
private def solve(n: Int, k: Int, lst: List[Int], edges: Set[Edge] = Set.empty): Set[Set[Edge]] = lst match {
  case h::t =>
    val result = for{v <- lst.toSet.filter(_ != h) // 중복된 노드, 같은 노드를 제외
                        newEdge = Edge(h, v)  // 새로운 엣지
                        nLst = t.diff(List(v))  // 남은 노드에서 이번 선택한 노드 제외
                        if !edges.contains(newEdge)} yield solve(n, k, nLst, edges + newEdge)
    result.flatten
  case Nil => Set(edges)
}

/**
  * n * k가 짝수개일때만 답이 존재하며
  * 엣지 수는 n * k / 2개라는 것을 알 수 있다.
  * @param n 노드 갯수
  * @param k 엣지 갯수
  * @return 만들어질 수 있는 엣지들
  */
def solution(n: Int, k: Int): Set[Set[Edge]] =
  if(n * k % 2 != 0 || k > n) Set.empty
  else{
    val lst = List.fill(k)(1 to n).flatten
    solve(n, k, lst)
  }

문제에서 제시된 N은 6, K는 3으므로 최대한 간단한 코드로 짜는 것을 목표로 삼았다.

노드를 선택할 때마다 diff 메소드로 노드를 제거하는데, 

quick sort에서 살펴봤던 것 처럼 filter를 사용하면 '하나의' 요소가 아닌 조건에 맞는 '모든' 요소가 제거되기 때문이다.

하지만 diff 메소드도 distinct 메소드와 마찬가지로 내부에 Map을 만들어 처리하기 때문에 이런 작은 입력 값에서는 느린 결과를 보여준다.