백준 17406 배열 돌리기 4 Kotlin (구현)

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

17406번: 배열 돌리기 4

문제

크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 값은 4이다.

1 2 3
2 1 1
4 5 6

배열은 회전 연산을 수행할 수 있다. 회전 연산은 세 정수 (r, c, s)로 이루어져 있고, 가장 왼쪽 윗 칸이 (r-s, c-s), 가장 오른쪽 아랫 칸이 (r+s, c+s)인 정사각형을 시계 방향으로 한 칸씩 돌린다는 의미이다. 배열의 칸 (r, c)는 r행 c열을 의미한다.

예를 들어, 배열 A의 크기가 6×6이고, 회전 연산이 (3, 4, 2)인 경우에는 아래 그림과 같이 회전하게 된다.

A[1][1]   A[1][2] → A[1][3] → A[1][4] → A[1][5] → A[1][6]
             ↑                                       ↓
A[2][1]   A[2][2]   A[2][3] → A[2][4] → A[2][5]   A[2][6]
             ↑         ↑                   ↓         ↓
A[3][1]   A[3][2]   A[3][3]   A[3][4]   A[3][5]   A[3][6]
             ↑         ↑                   ↓         ↓
A[4][1]   A[4][2]   A[4][3] ← A[4][4] ← A[4][5]   A[4][6]
             ↑                                       ↓
A[5][1]   A[5][2] ← A[5][3] ← A[5][4] ← A[5][5] ← A[5][6]

A[6][1]   A[6][2]   A[6][3]   A[6][4]   A[6][5]   A[6][6]

회전 연산이 두 개 이상이면, 연산을 수행한 순서에 따라 최종 배열이 다르다.

다음은 배열 A의 크기가 5×6이고, 회전 연산이 (3, 4, 2), (4, 2, 1)인 경우의 예시이다.

배열 A	(3, 4, 2) 연산 수행 후	(4, 2, 1) 연산 수행 후
배열 A	(4, 2, 1) 연산 수행 후	(3, 4, 2) 연산 수행 후

배열 A에 (3, 4, 2), (4, 2, 1) 순서로 연산을 수행하면 배열 A의 값은 12, (4, 2, 1), (3, 4, 2) 순서로 연산을 수행하면 15 이다.

배열 A와 사용 가능한 회전 연산이 주어졌을 때, 배열 A의 값의 최솟값을 구해보자. 회전 연산은 모두 한 번씩 사용해야 하며, 순서는 임의로 정해도 된다.

입력

첫째 줄에 배열 A의 크기 N, M, 회전 연산의 개수 K가 주어진다.

둘째 줄부터 N개의 줄에 배열 A에 들어있는 수 A[i][j]가 주어지고, 다음 K개의 줄에 회전 연산의 정보 r, c, s가 주어진다.

출력

배열 A의 값의 최솟값을 출력한다.

제한

• 3 ≤ N, M ≤ 50
• 1 ≤ K ≤ 6
• 1 ≤ A[i][j] ≤ 100
• 1 ≤ s
• 1 ≤ r-s < r < r+s ≤ N
• 1 ≤ c-s < c < c+s ≤ M

알고리즘 분류

• 구현
• 브루트포스 알고리즘
• 백트래킹

풀이

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

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

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

배열 돌리기 시리즈~

이번엔 순열까지 추가됐다.

 

문제 풀이는 다음과 같다.

순열로 회전 연산들의 순서를 바꾼 셋을 뽑는다.

결과셋(회전 연산들의 순서)으로 배열을 rotate한다.

이때 결과셋마다 원본 배열에 회전을 해야 하므로, 배열을 깊은 복사해서 rotate하자.

핵심은 순열 + rotate 구현

이전 글에서도 그랬지만, 본인은 회전을 저렇게 구현한다. 각자 스타일대로 돌리면 될 것 같다.

 

 

코드

val br = System.`in`.bufferedReader()
fun getIntList() = br.readLine().split(' ').map { it.toInt() }
fun getInt() = br.readLine().toInt()
lateinit var oper: Array<List<Int>>
lateinit var visited: BooleanArray
var answer = Int.MAX_VALUE
/*
* 회전 연산 조합
* 순열 결과로 회전, A 최솟값 갱신
* */

fun rotate(op: List<Int>, graph: Array<IntArray>){
    var sr = op[0]-1-op[2]
    var sc = op[1]-1-op[2]
    var er = op[0]-1+op[2]
    var ec = op[1]-1+op[2]
    var n = er-sr
    var m = ec-sc
    var cnt = op[2]
    while (cnt>0){
        var r = sr
        var c = sc
        var temp = graph[r+1][c]
        //우
        for(i in 0 until n){
            graph[r][c] = temp.also{temp = graph[r][c]}
            c++
        }
        //하
        for(i in 0 until n){
            graph[r][c] = temp.also{temp = graph[r][c]}
            r++
        }
        //좌
        for(i in 0 until n){
            graph[r][c] = temp.also{temp = graph[r][c]}
            c--
        }
        //상
        for(i in 0 until n){
            graph[r][c] = temp.also{temp = graph[r][c]}
            r--
        }
        sr++
        sc++
        n-=2
        m-=2
        cnt--
    }
}

fun permuatation(idx: Int, n: Int, m: Int, k: Int, result: IntArray, graph: Array<IntArray>){
    if(idx==k){
        //한 번의 순열 결과셋을 돌려볼 때 origin배열 상태에서 돌려야 함
        val tempArr = Array(n){ r->
            IntArray(m){ c->
                graph[r][c]
            }
        }
        //rotate
        for(r in result){
            val op = oper[r]
            rotate(op,tempArr)
        }
        //cal
        for(r in 0 until n){
            var sum =0
            for(c in 0 until m){
                sum += tempArr[r][c]
            }
            answer = answer.coerceAtMost(sum)
        }
        return
    }

    for(i in 0 until k){
        if(visited[i]) continue
        visited[i] = true
        result[idx] = i
        permuatation(idx+1, n, m, k, result,graph)
        visited[i] = false
    }
}

fun main() = with(System.out.bufferedWriter()){
    //input
    val (n,m,k) = getIntList()
    val graph = Array(n){ getIntList().toIntArray()}
    oper = Array(k) { getIntList() }
    visited = BooleanArray(k)
    //solve
    permuatation(0,n,m,k,IntArray(k),graph)

    //output
    write("$answer")

    close()
}