이전 글에서 살펴본 특징을 바탕으로 스칼라 코드로 구현해 보자.
0. 유틸리티성 정의
Int로 표기하면 굉장히 복잡해진다. 좀 더 이해하기 쉽게 Enumeration을 정의한다.
/**
* Nonogram 문제에서 사용할 Enumeration.
* 칠한 부분은 O, 칠할 수 없는 부분은 X, 알 수 없는 부분은 U로 표기한다.
*/
object NonogramEnum extends Enumeration {
val O, X, U = Value
}
이전 문제들과 달리 스택에 쌓아가며 재귀호출하는 문제는 아니기 때문에 mutable 콜렉션을 사용할 수도 있다.
하지만 함수형답게 immutable 콜렉션으로 푼다면 아래 메소드들이 필요하다.
/**
* 행이 칠해진 보드를 리턴하는 함수
*
* @param board 칠하려고 하는 보드
* @param col 칠하려고 하는 열의 인덱스
* @param valueLst 칠하려고 하는 값들
* @return (칠해진 보드, 칠해진 내역)
*/
def updateRow(board: Board, col: Int, valueLst:List[Value]): (Board, List[Value]) = {
def getUpdatedLst(lst:List[Value], valueLst: List[Value]): List[Value] = (lst, valueLst) match {
case (l, Nil) => l
case (lstH::lstT, valueH::valueT) =>
val updatedValue = if(lstH == NonogramEnum.U) valueH else lstH
updatedValue :: getUpdatedLst(lstT, valueT)
}
val updatedLst = getUpdatedLst(board(col), valueLst)
(board.updated(col, updatedLst), updatedLst)
}
보드의 행을 칠하는 함수
/**
* 열이 칠해진 보드를 리턴하는 함수
*
* @param board 칠하려고 하는 보드
* @param row 칠하려고 하는 행의 인덱스
* @param valueLst 칠하려고 하는 값들
* @return (칠해진 보드, 칠해진 내역)
*/
def updateCol(board: Board, row: Int, valueLst: List[Value]): (Board, List[Value]) = {
def updateColRec(board: Board, row: Int, valueLst: List[Value], col: Int): (Board, List[Value]) = valueLst match {
case Nil => (board, Nil)
case valueH :: valueT =>
val boardValue = board(col)(row)
val updatedValue = if (boardValue == NonogramEnum.U) valueH else boardValue
val filledBoard = board.updated(col, board(col).updated(row, updatedValue))
val (newBoard, updatedLst) = updateColRec(filledBoard, row, valueT, col + 1)
(newBoard, updatedValue :: updatedLst)
}
updateColRec(board, row, valueLst, 0)
}
보드의 열을 칠하는 함수
/**
* 보드를 출력용 문자열로 변환하는 함수
*
* @param board 문자열로 변환할 보드
* @return 보드로 만든 출력용 문자열
*/
implicit def boardToString(board: Board): String = {
val sb = StringBuilder.newBuilder
board.foreach { col =>
col.foreach { point =>
if (point == NonogramEnum.O) sb.append("| O ")
// else if(point == NonogramEnum.X) sb.append("| X ")
else sb.append("| ")
}
sb.append("|\n")
}
sb.toString()
}
1. 힌트를 이용해 모든 경우의 수들을 만드는 함수
P27. Subset 문제에서 익힌 방식과 비슷하지만 힌트 사이에 빈 칸이 최소 하나 있어야 한다는 점을 신경써야 한다.
어차피 칠한 부분을 리스트로 표현해야 하기 때문에 힌트로 적힌 숫자만큼 List.fill 함수를 이용하여 리스트에 채워넣되
마지막 힌트가 아니면 칠하지 않는다는 의미인 'X'를 뒤에 추가한다. 그렇게 하면 P27과 같은 재귀호출로 구현할 수 있다.
/**
* 전체 길이와 힌트를 입력받아
* 가능한 경우의 수를 모두 만들어내는 메소드
*
* @param length 전체 길이
* @param hint 힌트
* @return 만들어질 수 있는 모든 경우의 수
*/
def getAllCases(length: Int, hint: List[Int]): List[List[NonogramEnum.Value]] = {
/**
* 힌트를 입력받아 칠할 부분들을 구하는 메소드
* 마지막 힌트가 아니면 최소 한 칸의 칠해지면 안되는 부분이 필요하다.
*
* @param hint Int 형태의 힌트
* @return 칠해진 부분들의 그룹(힌트 그룹)
*/
def hintToGroup(hint: List[Int]): List[List[NonogramEnum.Value]] = hint match {
case h :: Nil => List(List.fill(h)(NonogramEnum.O))
case h :: t =>
(List.fill(h)(NonogramEnum.O) :+ NonogramEnum.X) :: hintToGroup(t)
}
if (hint.isEmpty) List(List.fill(length)(NonogramEnum.X)) // 힌트가 더 이상 없으면 남은 길이만큼 채움
else {
val hintGroup = hintToGroup(hint)
val maxLength = length - hintGroup.map(_.size).sum
// 0부터 만들 수 있는 최대 갯수만큼의 왼쪽 빈 칸을 만들고
// 힌트 그룹 하나를 합친 후 남은 길이와 힌트 그룹으로 재귀호출
(0 to maxLength).flatMap { v =>
val left = List.fill(v)(NonogramEnum.X) ::: hintGroup.head
getAllCases(length - left.size, hint.tail).map(left ::: _)
}.toList
}
}
getAllCases(8, List(3, 2)) foreach println List(O, O, O, X, O, O, X, X) List(O, O, O, X, X, O, O, X) List(O, O, O, X, X, X, O, O) List(X, O, O, O, X, O, O, X) List(X, O, O, O, X, X, O, O) List(X, X, O, O, O, X, O, O) |
2. '이미 어느정도 칠해진 부분'과 '힌트로 만들 수 있는 경우의 수들'을 입력받아 '칠해지는 부분'과 '칠해지지 않는 부분'을 구하는 함수
몇 번의 반복으로 보드의 일부가 칠해졌을 때 (혹은 하나도 칠해지지 않았을 때) 칠해진 일부와
힌트로 얻을 수 있는 '칠해지는 부분'과 '칠해지지 않는 부분'을 찾는 함수다.
이 함수는 몇 가지 순서로 나누어 생각하면 의외로 쉽다.
- 입력받은 '이미 어느정도 칠해진 부분'를 A라고 한다. - 힌트로 만들 수 있는 경우의 수들을 C라고 한다. - 칠할 수 없는 부분을 X, 칠해지는 부분을 O라고 한다. 1) C 중 A와 '완전히 어긋나는' 경우를 제거한다. '완전히 어긋나는' 경우는 A에서 X인 부분이 O인 C, A에서 O인 부분이 X인 C 두 가지가 있다. 2) C가 1개라면 A는 C와 같다. A를 C처럼 칠해야 한다. 3) C가 2개 이상이라면 C를 한개로 만든다. 모든 C에서 O인 부분은 '칠해지는 부분'이다. 모든 C에서 X인 부분은 '칠해지지 않는 부분'이다. |
이 순서로 구현한 함수는 아래와 같다.
/**
* 이미 어느정도 칠해진 부분과 경우의 수를 이용해
* `무조건 칠해지는 부분`과 `칠해지지 않는 부분`을 구하는 메소드
*
* @param nowFilledLine 이미 어느정도 칠해진 부분
* @param cases 경우의 수들
* @return 이미 칠한 부분과 경우의 수를 이용해 구한 `무조건 칠해지는 부분`과 `칠해지지 않는 부분`
*/
def getNextFilledLine(nowFilledLine: List[NonogramEnum.Value],
cases: List[List[NonogramEnum.Value]]): List[NonogramEnum.Value] = {
/**
* 경우의 수들을 합쳐 공통된 부분을 구하는 함수
*
* @param cases 경우의 수들
* @return 경우의 수들의 공통된 부분
*/
def foldCases(cases: List[List[NonogramEnum.Value]]): List[NonogramEnum.Value] =
cases.foldLeft(List.empty[NonogramEnum.Value]) { (total, caseLst) =>
if (total.isEmpty) caseLst
else caseLst.zipWithIndex.map(c =>
if (total(c._2) == c._1) c._1
else NonogramEnum.U
)
}
/**
* that이 lst와 `완전히 어긋난` 리스트인지 체크하는 메소드.
* 연속된 칠 중 일부 부분만 빈 경우를 알아낼 수 있음.
*
* @param lst 대상이 되는 리스트
* @param that 비교할 리스트
* @return 완전히 포함하는 리스트인지 여부
*/
@tailrec
def isContraryCase(lst: List[NonogramEnum.Value],
that: List[NonogramEnum.Value]): Boolean = (lst, that) match {
case (Nil, Nil) => false
case (lstH :: lstT, thatH :: thatT) =>
if (lstH == NonogramEnum.X && thatH == NonogramEnum.O) true
else if(lstH == NonogramEnum.O && thatH == NonogramEnum.X) true
else isContraryCase(lstT, thatT)
}
val intersect = cases.filterNot(isContraryCase(nowFilledLine, _))
if (intersect.size == 1) intersect.head
else foldCases(intersect)
}
아주 강력한 fold 함수를 이용해 경우의 수들을 합치는 함수를 간단하게 구현했다.
3. '완전히 풀어낸 부분'인지 확인하는 함수
힌트로 알 수 있는 '칠해야 하는 칸 수' 만큼 칠해졌는지 확인하는 함수다.
/**
* 리스트가 힌트를 모두 충족한 완성된 리스트인지 체크하는 메소드
*
* @param lst 대상 리스트
* @param hint 힌트
* @return 완성된 리스트인지 여부
*/
def validate(lst: List[NonogramEnum.Value], hint: List[Int]): Boolean =
lst.count(_ == NonogramEnum.O) == hint.sum
이 함수 자체는 매우 간단하지만 리턴값으로 true를 받는다면 칠해진 부분을 제외한 나머지 부분들은 모두 '칠해지지 않는 부분'이라는 점이 중요하다. O가 아닌 부분은 모두 X가 되어야 한다는 것이다.
위에서 구현한 함수들을 이용해 노노그램을 푸는 알고리즘을 구현하면 아래와 같다.
class Nonogram (rowHints: List[List[Int]], colHints: List[List[Int]]) {
type Board = List[List[Value]]
type Value = NonogramEnum.Value
val ROW_LENGTH: Int = colHints.size
val COL_LENGTH: Int = rowHints.size
val rowHintWithIndex: List[(List[Int], Int)] = rowHints.zipWithIndex
val colHintWithIndex: List[(List[Int], Int)] = colHints.zipWithIndex
val board: Board = List.fill(COL_LENGTH)(List.fill(ROW_LENGTH)(NonogramEnum.U))
/**
* 전체 길이와 힌트를 입력받아
* 가능한 경우의 수를 모두 만들어내는 메소드
*
* @param length 전체 길이
* @param hint 힌트
* @return 만들어질 수 있는 모든 경우의 수
*/
def getAllCases(length: Int, hint: List[Int]): List[List[Value]] = {
/**
* 힌트를 입력받아 칠할 부분들을 구하는 메소드
* 마지막 힌트가 아니면 최소 한 칸의 칠해지면 안되는 부분이 필요하다.
*
* @param hint Int 형태의 힌트
* @return 칠해진 부분들의 그룹
*/
def hintToGroup(hint: List[Int]): List[List[Value]] = hint match {
case h :: Nil => List(List.fill(h)(NonogramEnum.O))
case h :: t =>
(List.fill(h)(NonogramEnum.O) :+ NonogramEnum.X) :: hintToGroup(t)
}
if (hint.isEmpty) List(List.fill(length)(NonogramEnum.X)) // 힌트가 더 이상 없으면 남은 길이만큼 채움
else {
val hintGroup = hintToGroup(hint)
val maxLength = length - hintGroup.map(_.size).sum
// 0부터 만들 수 있는 최대 갯수만큼의 왼쪽 빈 칸을 만들고
// 힌트 그룹 하나를 합친 후 나머지 갯수와 힌트로 재귀호출
(0 to maxLength).flatMap { v =>
val left = List.fill(v)(NonogramEnum.X) ::: hintGroup.head
getAllCases(length - left.size, hint.tail).map(left ::: _)
}.toList
}
}
/**
* 이미 어느정도 칠해진 부분과 경우의 수를 이용해
* `무조건 칠해지는 부분`과 `칠해지지 않는 부분`을 구하는 메소드
*
* @param nowFilledLine 이미 어느정도 칠해진 부분
* @param cases 경우의 수들
* @return 이미 칠한 부분과 경우의 수를 이용해 구한 `무조건 칠해지는 부분`과 `칠해지지 않는 부분`
*/
def getNextFilledLine(nowFilledLine: List[Value],
cases: List[List[Value]]): List[Value] = {
/**
* 경우의 수들을 합쳐 공통된 부분을 구하는 함수
*
* @param cases 경우의 수들
* @return 경우의 수들의 공통된 부분
*/
def foldCases(cases: List[List[Value]]): List[Value] =
cases.foldLeft(List.empty[Value]) { (total, caseLst) =>
if (total.isEmpty) caseLst
else caseLst.zipWithIndex.map(c =>
if (total(c._2) == c._1) c._1
else NonogramEnum.U
)
}
/**
* that이 lst와 `완전히 어긋난` 리스트인지 체크하는 메소드.
* 연속된 칠 중 일부 부분만 빈 경우를 알아낼 수 있음.
*
* @param lst 대상이 되는 리스트
* @param that 비교할 리스트
* @return 완전히 포함하는 리스트인지 여부
*/
@tailrec
def isContraryCase(lst: List[Value],
that: List[Value]): Boolean = (lst, that) match {
case (Nil, Nil) => false
case (lstH :: lstT, thatH :: thatT) =>
if (lstH == NonogramEnum.X && thatH == NonogramEnum.O) true
else if(lstH == NonogramEnum.O && thatH == NonogramEnum.X) true
else isContraryCase(lstT, thatT)
}
val intersect = cases.filterNot(isContraryCase(nowFilledLine, _))
if (intersect.size == 1) intersect.head
else foldCases(intersect)
}
/**
* 행이 칠해진 보드를 리턴하는 메소드
*
* @param board 칠하려고 하는 보드
* @param col 칠하려고 하는 열의 인덱스
* @param valueLst 칠하려고 하는 값들
* @return (칠해진 보드, 칠해진 내역)
*/
def updateRow(board: Board, col: Int, valueLst:List[Value]): (Board, List[Value]) = {
def getUpdatedLst(lst:List[Value], valueLst: List[Value]): List[Value] = (lst, valueLst) match {
case (l, Nil) => l
case (lstH::lstT, valueH::valueT) =>
val updatedValue = if(lstH == NonogramEnum.U) valueH else lstH
updatedValue :: getUpdatedLst(lstT, valueT)
}
val updatedLst = getUpdatedLst(board(col), valueLst)
(board.updated(col, updatedLst), updatedLst)
}
/**
* 행이 완성되었을 때 칠해진 부분만 남기는 메소드
*
* @param board 보드
* @param col 완성된 행의 열 인덱스
* @return 칠해진 부분만 남은 보드
*/
def closeRow(board: Board, col: Int): Board = {
val lst = board(col).map(v => if(v != NonogramEnum.O) NonogramEnum.X else v)
board.updated(col, lst)
}
/**
* 열이 칠해진 보드를 리턴하는 메소드
*
* @param board 칠하려고 하는 보드
* @param row 칠하려고 하는 행의 인덱스
* @param valueLst 칠하려고 하는 값들
* @return (칠해진 보드, 칠해진 내역)
*/
def updateCol(board: Board, row: Int, valueLst: List[Value]): (Board, List[Value]) = {
def updateColRec(board: Board, row: Int, valueLst: List[Value], col: Int): (Board, List[Value]) = valueLst match {
case Nil => (board, Nil)
case valueH :: valueT =>
val boardValue = board(col)(row)
val updatedValue = if (boardValue == NonogramEnum.U) valueH else boardValue
val filledBoard = board.updated(col, board(col).updated(row, updatedValue))
val (newBoard, updatedLst) = updateColRec(filledBoard, row, valueT, col + 1)
(newBoard, updatedValue :: updatedLst)
}
updateColRec(board, row, valueLst, 0)
}
/**
* 열이 완성되었을 때 칠해진 부분만 남기는 메소드
*
* @param board 보드
* @param col 완성된 열의 행 인덱스
* @return 칠해진 부분만 남은 보드
*/
def closeCol(board: Board, col: Int): Board = {
@tailrec
def closeColRec(board: Board, row: Int, col: Int): Board = {
if(col >= COL_LENGTH) return board
val v = if(board(col)(row) != NonogramEnum.O) NonogramEnum.X else NonogramEnum.O
val nextBoard = board.updated(col, board(col).updated(row, v))
closeColRec(nextBoard, row, col + 1)
}
closeColRec(board, col, 0)
}
/**
* 리스트가 힌트를 모두 충족한 완성된 리스트인지 체크하는 메소드
*
* @param lst 대상 리스트
* @param hint 힌트
* @return 완성된 리스트인지 여부
*/
private def validate(lst: List[Value], hint: List[Int]): Boolean =
lst.count(_ == NonogramEnum.O) == hint.sum
/**
* 문제를 풀어내는 메소드
*
* @param board 답을 입력할 보드
* @param hint 힌트
* @param isRow 현재 체크하는 부분이 행인지 여부
* @param vailCount 행, 혹은 열에서 완성된 줄의 수.
* 전체 길이와 같으면 함수가 종료된다.
*
* @return 답이 입력된 보드
*/
@tailrec
private final def solve(board: Board,
hint: List[(List[Int], Int)],
isRow: Boolean, vailCount: Int = 0): String = {
// 행/열 상황에 맞춘 함수와 길이 설정
val (updateFunction, closeFunction, length) = if(isRow) (updateRow _, closeRow _, ROW_LENGTH)
else (updateCol _, closeCol _, COL_LENGTH)
hint match {
case hintH :: hintT =>
val (hint, i) = hintH
val line = if(isRow) board(i) else board.map(_(i))
val newFill = getNextFilledLine(line, getAllCases(length, hint))
// 현재에 상황에 맞는 함수로 얻은 '무조건 칠해지는 부분'을 칠한다.
val (filledBoard: Board, updatedLst: List[Value]) = updateFunction(board, i, newFill)
// '완전히 풀어낸 부분' 인지 확인하고 완성된 줄의 수를 체크한다.
val (nextBoard, nowVailCount) = if(vaildate(updatedLst, hint))
// '완전히 풀어낸 부분'이면 칠해진 부분만 남기고 나머지 부분 X.
(closeFunction(filledBoard, i), vailCount + 1)
else (filledBoard, vailCount)
solve(nextBoard, hintT, isRow, nowVailCount)
case Nil =>
if (vailCount == length) return board
val nextHint = if(!isRow) rowHintWithIndex else colHintWithIndex
solve(board, nextHint, !isRow)
}
}
/**
* 보드를 출력용 문자열로 변환하는 메소드
*
* @param board 문자열로 변환할 보드
* @return 보드로 만든 출력용 문자열
*/
implicit def boardToString(board: Board): String = {
val sb = StringBuilder.newBuilder
board.foreach { col =>
col.foreach { point =>
if (point == NonogramEnum.O) sb.append("| O ")
// else if(point == NonogramEnum.X) sb.append("| X ")
else sb.append("| ")
}
sb.append("|\n")
}
sb.toString()
}
/**
* 결과를 출력하기 위해 호출하는 메소드
* @return 결과
*/
def solution: String = solve(board, rowHintWithIndex, isRow = true)
}
※ immutable List를 사용하는 코드로 변경했다.
// 문제 |
이 사이트에 있는 노노그램 문제를 몇 가지 더 풀어보았다.
|
|
풀어내는 속도는 그럭저럭 만족스럽지만 좋은 코드인지에 대한 아쉬움이 남는다.
변경 불가능한 리스트를 사용하기 위해 update 메소드들이 필요했고, 열과 행을 담당하는 코드의 중복을 제거하기 위해 if-else 구문이 많아졌다. 덕분에 코드는 짧아졌지만 더 복잡한 코드가 되어 버렸다.
앞으로는 더 많은, 더 깊은 고민으로 더 좋은 풀이를 만들어 낼 수 있기를 바란다.
'Scala > Scala Ninety-Nine Problems' 카테고리의 다른 글
| P98. Scala로 풀어본 Nonogram(노노그램, 네모네모로직) - 1 (0) | 2017.03.21 |
|---|---|
| P97. Scala로 풀어본 Sudoku(스도쿠) (0) | 2017.03.20 |
| P94. Scala로 만들어본 K-regular simple graph(정규 그래프) (0) | 2017.03.16 |
| P93. Scala로 풀어본 Arithmetic Puzzle (0) | 2017.03.09 |
| P92. Scala로 풀어본 Von Koch's conjection (0) | 2017.03.06 |