백준 17140 이차원 배열과 연산 Kotlin (구현)

문제 출처 : https://www.acmicpc.net/problem/17140

17140번: 이차원 배열과 연산

문제

크기가 3×3인 배열 A가 있다. 배열의 인덱스는 1부터 시작한다. 1초가 지날때마다 배열에 연산이 적용된다.

• R 연산: 배열 A의 모든 행에 대해서 정렬을 수행한다. 행의 개수 ≥ 열의 개수인 경우에 적용된다.
• C 연산: 배열 A의 모든 열에 대해서 정렬을 수행한다. 행의 개수 < 열의 개수인 경우에 적용된다.

한 행 또는 열에 있는 수를 정렬하려면, 각각의 수가 몇 번 나왔는지 알아야 한다. 그 다음, 수의 등장 횟수가 커지는 순으로, 그러한 것이 여러가지면 수가 커지는 순으로 정렬한다. 그 다음에는 배열 A에 정렬된 결과를 다시 넣어야 한다. 정렬된 결과를 배열에 넣을 때는, 수와 등장 횟수를 모두 넣으며, 순서는 수가 먼저이다.

예를 들어, [3, 1, 1]에는 3이 1번, 1가 2번 등장한다. 따라서, 정렬된 결과는 [3, 1, 1, 2]가 된다. 다시 이 배열에는 3이 1번, 1이 2번, 2가 1번 등장한다. 다시 정렬하면 [2, 1, 3, 1, 1, 2]가 된다.

정렬된 결과를 배열에 다시 넣으면 행 또는 열의 크기가 달라질 수 있다. R 연산이 적용된 경우에는 가장 큰 행을 기준으로 모든 행의 크기가 변하고, C 연산이 적용된 경우에는 가장 큰 열을 기준으로 모든 열의 크기가 변한다. 행 또는 열의 크기가 커진 곳에는 0이 채워진다. 수를 정렬할 때 0은 무시해야 한다. 예를 들어, [3, 2, 0, 0]을 정렬한 결과는 [3, 2]를 정렬한 결과와 같다.

행 또는 열의 크기가 100을 넘어가는 경우에는 처음 100개를 제외한 나머지는 버린다.

배열 A에 들어있는 수와 r, c, k가 주어졌을 때, A[r][c]에 들어있는 값이 k가 되기 위한 최소 시간을 구해보자.

입력

첫째 줄에 r, c, k가 주어진다. (1 ≤ r, c, k ≤ 100)

둘째 줄부터 3개의 줄에 배열 A에 들어있는 수가 주어진다. 배열 A에 들어있는 수는 100보다 작거나 같은 자연수이다.

출력

A[r][c]에 들어있는 값이 k가 되기 위한 연산의 최소 시간을 출력한다. 100초가 지나도 A[r][c] = k가 되지 않으면 -1을 출력한다.

알고리즘 분류

• 구현
• 정렬
• 시뮬레이션

풀이

시뮬레이션(구현) 문제다.

우선 그래프는 100*100 크기를 넘어가면 버리기 때문에 100*100 크기의 그래프를 생성한다.

이 그래프를 매번 Rsort 혹은 Csort하면서 graph[r][c] = k 가 되는 시점을 구해야 하는데,

본인은 bfs로 Rsort, Csort하면서 그래프를 바꿔나갔다.

문제를 다시 보니 Rsort와 Csort 둘 다 가능한 경우는 없기 때문에 그냥 graph[r][c]가 k가 될 때까지 혹은 100번 Rsort나 Csort둘 중 하나를 계속 돌리면 된다.

또, 그래프를 DeepCopy할 필요도 없이 그냥 기존 객체에 요소들을 바꾸면 된다.

 

무튼 Rsort와 Csort를 구현하는 것과

Rsort를 할지, Csort를 할지 정하기 위해 RMaxSize, CMaxSize를 구하는 것이 관건이다.

RMaxSize와 CMaxSize는 그냥 100*100 포문 돌려서 알아내면 되고,

Rsort구현은 map을 이용해 r행의 c개 열의 숫자와 개수를 map을 이용해 구해낸 후 num, cnt를 ArrayList에 저장한 후 cnt 기준 오름차순, num 기준 오름차순으로 정렬한다.

이때 그냥 sortedMap을 사용해도 된다. 또, 요소들을 검사할 때는 0을 제외해야 하고 c의 범위는 0 until max(rSize,cSize)이다. 

이렇게 구한 정렬된 리스트를 새로운 graph의 r행에 삽입한다.

이를 max(rSize,cSize)만큼 반복한다.

코드

import java.util.*
val br = System.`in`.bufferedReader()
fun getIntList() = br.readLine().trim().split(' ').map { it.toInt() }
fun getInt() = br.readLine().trim().toInt()


//개수 오름차순
//수 오름차순

var er = 0
var ec = 0
var k = 0

fun getRCSize(graph: Array<IntArray>): Pair<Int, Int> {
    var rSize = 0
    var cSize = 0
    for (r in 0 until 100) {
        for (c in 0 until 100) {
            if (graph[r][c] != 0) {
                rSize = rSize.coerceAtLeast(r + 1)
                cSize = cSize.coerceAtLeast(c + 1)
            }
        }
    }
    return Pair(rSize, cSize)
}

data class Node(
    val num: Int,
    val cnt: Int
)

fun sortR(graph: Array<IntArray>, size: Int): Array<IntArray> {
    val newGraph = Array(100) { IntArray(100) }
    for (r in 0 until size) {
        val map = mutableMapOf<Int, Int>()
        for (c in 0 until size) {
            if(graph[r][c]==0) continue
            map[graph[r][c]] = map.getOrDefault(graph[r][c], 0) + 1
        }
        val afterList = ArrayList<Node>()
        map.forEach { num, cnt ->
            afterList.add(Node(num, cnt))
        }
        afterList.sortWith(compareBy<Node> { it.cnt }.thenBy { it.num })
        var idx = 0
        for (c in afterList.indices) {
            if (idx < 100) {
                newGraph[r][idx++] = afterList[c].num
            }
            if (idx < 100) {
                newGraph[r][idx++] = afterList[c].cnt
            }
        }
    }
    return newGraph
}

fun sortC(graph: Array<IntArray>, size: Int): Array<IntArray> {
    val newGraph = Array(100) { IntArray(100) }
    for (c in 0 until size) {
        val map = mutableMapOf<Int, Int>()
        for (r in 0 until size) {
            if(graph[r][c]==0) continue
            map[graph[r][c]] = map.getOrDefault(graph[r][c], 0) + 1
        }
        val afterList = ArrayList<Node>()
        map.forEach { num, cnt ->
            afterList.add(Node(num, cnt))
        }
        afterList.sortWith(compareBy<Node> { it.cnt }.thenBy { it.num })
        var idx = 0
        for (r in afterList.indices) {
            if (idx < 100) {
                newGraph[idx++][c] = afterList[r].num
            }
            if (idx < 100) {
                newGraph[idx++][c] = afterList[r].cnt
            }
        }
    }
    return newGraph
}

fun bfs(graph: Array<IntArray>): Int {
    val q: Queue<Array<IntArray>> = LinkedList()
    q.add(graph)
    var cnt = 0
    while (q.isNotEmpty()) {
        val cur = q.poll()
        val (rSize, cSize) = getRCSize(cur)
        cnt++
        if (cnt > 100) break
        if (rSize >= cSize) {
            val next = sortR(cur, rSize)
            if (next[er - 1][ec - 1] == k) return cnt
            q.add(next)
        } else {
            val next = sortC(cur, cSize)
            if (next[er - 1][ec - 1] == k) return cnt
            q.add(next)
        }
    }
    return -1
}

fun main() = with(System.out.bufferedWriter()) {
    //input
    getIntList().apply {
        er = this[0]
        ec = this[1]
        k = this[2]
    }
    val input = Array(3){ getIntList()}
    //pre
    val graph = Array(100) { IntArray(100) }
    for (i in 0 until 3) {
        for (j in 0 until 3) {
            graph[i][j] = input[i][j]
        }
    }
    //solve
    if (graph[er - 1][ec - 1] == k) {
        write("0")
        close()
        return
    }
    write("${bfs(graph)}")
    close()
}