프로그래머스 퍼즐 조각 채우기 Kotlin (시뮬레이션)

문제 출처  :https://programmers.co.kr/learn/courses/30/lessons/84021

코딩테스트 연습 - 퍼즐 조각 채우기

• 퍼즐 조각 채우기

문제 설명

테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈 공간에 적절히 올려놓으려 합니다. 게임 보드와 테이블은 모두 각 칸이 1x1 크기인 정사각 격자 모양입니다. 이때, 다음 규칙에 따라 테이블 위에 놓인 퍼즐 조각을 게임 보드의 빈칸에 채우면 됩니다.

• 조각은 한 번에 하나씩 채워 넣습니다.
• 조각을 회전시킬 수 있습니다.
• 조각을 뒤집을 수는 없습니다.
• 게임 보드에 새로 채워 넣은 퍼즐 조각과 인접한 칸이 비어있으면 안 됩니다.

다음은 퍼즐 조각을 채우는 예시입니다.

위 그림에서 왼쪽은 현재 게임 보드의 상태를, 오른쪽은 테이블 위에 놓인 퍼즐 조각들을 나타냅니다. 테이블 위에 놓인 퍼즐 조각들 또한 마찬가지로 [상,하,좌,우]로 인접해 붙어있는 경우는 없으며, 흰 칸은 퍼즐이 놓이지 않은 빈 공간을 나타냅니다. 모든 퍼즐 조각은 격자 칸에 딱 맞게 놓여있으며, 격자 칸을 벗어나거나, 걸쳐 있는 등 잘못 놓인 경우는 없습니다.

이때, 아래 그림과 같이 3,4,5번 조각을 격자 칸에 놓으면 규칙에 어긋나므로 불가능한 경우입니다.

• 3번 조각을 놓고 4번 조각을 놓기 전에 위쪽으로 인접한 칸에 빈칸이 생깁니다.
• 5번 조각의 양 옆으로 인접한 칸에 빈칸이 생깁니다.

다음은 규칙에 맞게 최대한 많은 조각을 게임 보드에 채워 넣은 모습입니다.

최대한 많은 조각을 채워 넣으면 총 14칸을 채울 수 있습니다.

현재 게임 보드의 상태 game_board, 테이블 위에 놓인 퍼즐 조각의 상태 table이 매개변수로 주어집니다. 규칙에 맞게 최대한 많은 퍼즐 조각을 채워 넣을 경우, 총 몇 칸을 채울 수 있는지 return 하도록 solution 함수를 완성해주세요.

---

제한사항

• 3 ≤ game_board의 행 길이 ≤ 50
• game_board의 각 열 길이 = game_board의 행 길이
  • 즉, 게임 보드는 정사각 격자 모양입니다.
  • game_board의 모든 원소는 0 또는 1입니다.
  • 0은 빈칸, 1은 이미 채워진 칸을 나타냅니다.
  • 퍼즐 조각이 놓일 빈칸은 1 x 1 크기 정사각형이 최소 1개에서 최대 6개까지 연결된 형태로만 주어집니다.
• table의 행 길이 = game_board의 행 길이
• table의 각 열 길이 = table의 행 길이
  • 즉, 테이블은 game_board와 같은 크기의 정사각 격자 모양입니다.
  • table의 모든 원소는 0 또는 1입니다.
  • 0은 빈칸, 1은 조각이 놓인 칸을 나타냅니다.
  • 퍼즐 조각은 1 x 1 크기 정사각형이 최소 1개에서 최대 6개까지 연결된 형태로만 주어집니다.
• game_board에는 반드시 하나 이상의 빈칸이 있습니다.
• table에는 반드시 하나 이상의 블록이 놓여 있습니다.

입출력 예 설명

입출력 예 #1

입력은 다음과 같은 형태이며, 문제의 예시와 같습니다.

입출력 예 #2

블록의 회전은 가능하지만, 뒤집을 수는 없습니다.

 

풀이

화가 많이 나는 문제.

구현, 시뮬레이션 , 백트래킹 문제이다.

한 3시간 푼 거 같다.

디버깅이 너무 힘들다.

 

전체적인 풀이는 다음과 같다.

1. 퍼즐 셋 생성, 구멍 셋 생성
2. 퍼즐 회전 구현
3. 구멍 셋을 기준으로 퍼즐 셋을 맞춰보는 백트래킹

 

구현에 대한 설명은 생략한다.

 

퍼즐 셋 생성과 구멍 셋 생성은

주어진 테이블과 보드에서 추출해야 하는데,

이때 '핏하게' 추출해야 한다.

예를 들어

11

01

모양의 퍼즐이 있는데 이걸

0000

0110

0010

0000

이런식으로 공간을 낭비하면 안 된다.

이렇게 해도 다른 부분에서 최적화한 사람은 통과될런지는 모르겠다.

다만 내 코드는 이렇게 했을 때 시간 초과였다.

그리고 구멍과 퍼즐을 맞춰보기 불편하다.

이렇게 퍼즐 셋과 구멍 셋은 구했다.

 

퍼즐 회전은 그냥 돌리면 된다. 어렵다면 배열 돌리기 시리즈를 풀고 오자.

2022.06.23 - [알고리즘 문제 풀이/백준] - 백준 17406 배열 돌리기 4 Kotlin (구현)

2022.06.13 - [알고리즘 문제 풀이/백준] - 백준 16935 배열 돌리기 3 Kotlin (구현)

2022.06.17 - [알고리즘 문제 풀이/백준] - 백준 16927 배열 돌리기 2 Kotlin (구현)

2021.11.15 - [알고리즘 문제 풀이/백준] - 백준 16926 배열 돌리기 1 c++ (구현)

 

이제 퍼즐 셋을 회전해 가며 구멍 셋에 맞추어야 한다.

맞춰보는 함수는 아래 전체 코드에 canMatchBoard함수를 보면 이해할 수 있을 것이다.

아래 부분 코드는 백트래킹의 일부 코드이다.

여기서 usedPuzzle[i] = true, 재귀 호출한 이후 usedPuzzle[i] = false로 다시 초기화해서 시간 초과가 떴었다.

한 번 맞은 puzzle은 굳이 다른 데 껴보지 않아도 된다.

 

또 아무것도 안 맞으면 다음 재귀 호출을 해 주어야 하는데, 이 부분을 빼먹었었다. 하지만 예제 테케는 다 맞게 나오고, 풀이 자체는 틀리지 않았기 때문에 막막했다.

 

https://programmers.co.kr/questions/19906

그러던 와중 pgstter님이 날 구원해 주었다.

내 풀이가 저격된 테케는 아니지만, 지쳐버려 반례를 만들 엄두가 안 났던 내게

내 풀이는 이 테케의 정답과 다른 답을 출력했고, 이를 디버깅하는 과정에서 아무것도 안 맞으면 다음 재귀 호출하는 코드를 빼먹었단 걸 알게 되었다.

 

이 문제는 시간 많을 때 푸는 것을 추천한다... 한 방에 못 맞으면 디버깅 지옥이다.

                //맞으면 다음 탐색, 회전 스탑
                else {
                    usedPuzzle[i] = true
                    backTracking(idx + 1, sum + matchCnt)

                    break
                }
            }
        }
        //아무것도 안 맞으면 다음
        backTracking(idx+1, sum)

 

코드

import java.util.*
/*
1. 퍼즐 셋 생성, 보드 셋 생성
2. 퍼즐 회전 구현
3. 구멍 셋을 기준으로 퍼즐 셋을 맞춰보는 백트래킹
*/
class Solution {
    var n = 0
    var m = 0
    var answer = 0
    lateinit var usedPuzzle: BooleanArray
    val puzzleList = ArrayList<Array<IntArray>>()
    val spaceList = ArrayList<Array<IntArray>>()
    val dir = arrayOf(
        arrayOf(-1, 0),//상
        arrayOf(0, 1),//우
        arrayOf(1, 0),//하
        arrayOf(0, -1)//좌
    )

	// space랑 puzzle 딱 들어맞는지 확인, 퍼즐 맞춘 칸 개수 반환
    fun canMatchBoard(space: Array<IntArray>, idx: Int): Int {
        val puzzle = puzzleList[idx]
        if (space.size != puzzle.size || space[0].size != puzzle[0].size) return 0

        var matchCnt = 0
        for (r in space.indices) {
            for (c in space[r].indices) {
                if (space[r][c] == puzzle[r][c]) {
                    return 0
                }
                if (space[r][c] == 0) matchCnt++
            }
        }
        return matchCnt
    }

    //3. 보드에 퍼즐 맞추기(백트래킹)
    fun backTracking(idx: Int, sum: Int) {
        answer = answer.coerceAtLeast(sum)
        if (idx == spaceList.size) {
            return
        }
        //모든 퍼즐
        for (i in puzzleList.indices) {
            if (usedPuzzle[i]) continue
            //회전
            for (j in 0 until 4) {
                //퍼즐 대보기
                val matchCnt = canMatchBoard(spaceList[idx], i)
                //안 맞으면 돌리기
                if (matchCnt == 0) {
                    puzzleList[i] = rotate(i)
                }
                //맞으면 다음 탐색, 회전 스탑
                else {
                    usedPuzzle[i] = true
                    backTracking(idx + 1, sum + matchCnt)

                    break
                }
            }
        }
        //아무것도 안 맞으면 다음
        backTracking(idx+1, sum)
    }

    //2. 퍼즐 회전
    fun rotate(idx: Int): Array<IntArray> {
        val N = puzzleList[idx][0].size
        val M = puzzleList[idx].size
        val temp = Array(N) { IntArray(M) }

        for (r in 0 until N) {
            for (c in 0 until M) {
                temp[r][c] = puzzleList[idx][M - c - 1][r]
            }
        }
        return temp
    }

    //1.퍼즐 셋 생성, 보드 셋 생성
    //핏하게 저장
    fun makePiece(
        table: Array<IntArray>,
        r: Int,
        c: Int,
        visited: Array<BooleanArray>,
        state: String
    ): Array<IntArray> {
        val rc = ArrayList<Pair<Int, Int>>()
        var minR = r
        var maxR = r
        var minC = c
        var maxC = c
        val q: Queue<Pair<Int, Int>> = LinkedList()
        q.add(Pair(r, c))
        rc.add(Pair(r, c))
        visited[r][c] = true
        while (q.isNotEmpty()) {
            val (cr, cc) = q.poll()
            for (i in 0 until 4) {
                val nr = cr + dir[i][0]
                val nc = cc + dir[i][1]
                if (nr !in 0 until n || nc !in 0 until m) continue
                when (state) {
                    "board" -> {
                        if (table[nr][nc] == 1 || visited[nr][nc]) continue
                    }
                    else -> {
                        if (table[nr][nc] == 0 || visited[nr][nc]) continue
                    }
                }
                q.add(Pair(nr, nc))
                visited[nr][nc] = true
                rc.add(Pair(nr, nc))
                minR = minR.coerceAtMost(nr)
                maxR = maxR.coerceAtLeast(nr)
                minC = minC.coerceAtMost(nc)
                maxC = maxC.coerceAtLeast(nc)
            }
        }
        val piece = when (state) {
            "board" -> {
                Array(maxR - minR + 1) { IntArray(maxC - minC + 1) { 1 } }
            }
            else -> {
                Array(maxR - minR + 1) { IntArray(maxC - minC + 1) }
            }
        }
        for ((rr, cc) in rc) {
            piece[rr - minR][cc - minC] = when (state) {
                "board" -> {
                    0
                }
                else -> {
                    1
                }
            }
        }
        return piece
    }

    fun solution(game_board: Array<IntArray>, table: Array<IntArray>): Int {
        //preset
        n = game_board.size
        m = game_board[0].size

        //make Puzzle set
        var visited = Array(n) { BooleanArray(m) }
        for (r in 0 until n) {
            for (c in 0 until m) {
                if (visited[r][c] || table[r][c] == 0) continue
                puzzleList.add(makePiece(table, r, c, visited, "puzzle"))
            }
        }
        usedPuzzle = BooleanArray(puzzleList.size)
        //make space set
        visited = Array(n) { BooleanArray(m) }
        for (r in 0 until n) {
            for (c in 0 until m) {
                if (visited[r][c] || game_board[r][c] == 1) continue
                spaceList.add(makePiece(game_board, r, c, visited, "board"))
            }
        }
        //solve
        backTracking(0, 0)
        //output
        return answer
    }
}