[Programers] 카드 짝 맞추기 (Kotlin)

https://school.programmers.co.kr/learn/courses/30/lessons/72415

프로그래머스

풀이

BFS + 순열을 이용한 문제였다.

중요한 점은 BFS 로직을 작성할 때

1. 도착 시
2. 한 칸 이동
3. Ctrl + 이동

세 부분을 나누어서 생각해야 하는 점이다.

 

2차원 배열을 Deep Copy 할 때 board.clone() 을 해서 오류가 발생했다.
clone() 메서드를 2차원 배열에 사용하면 배열 내부의 요소는 Deep Copy 되지 않는다는 점을 조심하자.

 

 

import java.util.LinkedList
import kotlin.math.min

class Solution {
    lateinit var board: Array<IntArray>
    lateinit var pVisit: BooleanArray

    val dir = arrayOf(intArrayOf(1, 0), intArrayOf(0, 1), intArrayOf(-1, 0), intArrayOf(0, -1))
    val cards = BooleanArray(7)

    var size = 0
    var answer = Int.MAX_VALUE

    fun solution(board: Array<IntArray>, r: Int, c: Int): Int {
        this.board = board

        for (arr in board) {
            for (value in arr) {
                if (value != 0) {
                    cards[value] = true
                    size++
                }
            }
        }
        size /= 2

        pVisit = BooleanArray(size + 1)

        permutation(0, IntArray(size + 1), r, c)

        return answer
    }

    fun permutation(idx: Int, order: IntArray, r: Int, c: Int) {
        if (idx == size) {
            find(order, intArrayOf(r, c), copyArr())
            return
        }

        for (i in 1..6) {
            if (!cards[i] || pVisit[i]) continue
            pVisit[i] = true
            order[idx] = i
            permutation(idx + 1, order, r, c)
            pVisit[i] = false
        }
    }

    fun copyArr(): Array<IntArray> {
        val copy = Array(4) { IntArray(4) }
        for ((x, arr) in board.withIndex()) {
            copy[x] = arr.clone()
        }
        return copy
    }

    fun find(order: IntArray, curLocation: IntArray, copyBoard: Array<IntArray>) {
        var totalCnt = 0

        for (i in 0 until size) {
            totalCnt += bfs(order[i], curLocation, copyBoard)
            copyBoard[curLocation[0]][curLocation[1]] = 0
            totalCnt++

            totalCnt += bfs(order[i], curLocation, copyBoard)
            copyBoard[curLocation[0]][curLocation[1]] = 0
            totalCnt++
        }

        answer = min(totalCnt, answer)
    }

    fun bfs(target: Int, curLocation: IntArray, copyBoard: Array<IntArray>): Int {
        val q = LinkedList<Point>()
        val visit = Array(4) { BooleanArray(4) }

        q.offer(Point(curLocation[0], curLocation[1], 0))
        visit[curLocation[0]][curLocation[1]] = true

        while (!q.isEmpty()) {
            val cur = q.poll()
            val x = cur.x
            val y = cur.y

            // 도착
            if (target == copyBoard[x][y]) {
                curLocation[0] = x
                curLocation[1] = y
                return cur.dist
            }

            // 1칸 이동
            for (d in dir) {
                val nx = x + d[0]
                val ny = y + d[1]

                if (!isValid(nx, ny)) continue
                if (visit[nx][ny]) continue

                q.offer(Point(nx, ny, cur.dist + 1))
                visit[nx][ny] = true
            }

            // Ctrl + 이동
            for (d in dir) {
                var nx = x
                var ny = y

                while (isValid(nx + d[0], ny + d[1])) {
                    nx += d[0]
                    ny += d[1]

                    if (copyBoard[nx][ny] != 0) {
                        break
                    }
                }

                if (!isValid(nx, ny)) continue
                if (visit[nx][ny]) continue

                q.offer(Point(nx, ny, cur.dist + 1))
                visit[nx][ny] = true
            }
        }

        return 0
    }

    fun isValid(x: Int, y: Int): Boolean {
        return x in 0..3 && y in 0..3
    }

    class Point(val x: Int, val y: Int, val dist: Int)

        /**
    board    r    c    result
    [[1,0,0,3],[2,0,0,0],[0,0,0,2],[3,0,1,0]]    1    0    14
    [[3,0,0,2],[0,0,1,0],[0,1,0,0],[2,0,0,3]]    0    1    16
     */

    @Test
    fun test() {
        val board1 = arrayOf(
            intArrayOf(1, 0, 0, 3),
            intArrayOf(2, 0, 0, 0),
            intArrayOf(0, 0, 0, 2),
            intArrayOf(3, 0, 1, 0)
        )
        val board2 = arrayOf(
            intArrayOf(3, 0, 0, 2),
            intArrayOf(0, 0, 1, 0),
            intArrayOf(0, 1, 0, 0),
            intArrayOf(2, 0, 0, 3)
        )

        assertAll(
            { Assertions.assertThat(test(board1, 1, 0)).isEqualTo(14) },
            { Assertions.assertThat(test(board2, 0, 1)).isEqualTo(16) }
        )
    }

    companion object {
        fun test(board: Array<IntArray>, r: Int, c: Int): Int {
            val test = Solution()
            return test.solution(board, r, c)
        }
    }
}