백준 16927 배열 돌리기 2 Kotlin (구현)

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

16927번: 배열 돌리기 2

문제

크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다.

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

예를 들어, 아래와 같은 배열을 2번 회전시키면 다음과 같이 변하게 된다.

1 2 3 4       2 3 4 8       3 4 8 6
5 6 7 8       1 7 7 6       2 7 8 2
9 8 7 6   →   5 6 8 2   →   1 7 6 3
5 4 3 2       9 5 4 3       5 9 5 4
 <시작>         <회전1>        <회전2>

배열과 정수 R이 주어졌을 때, 배열을 R번 회전시킨 결과를 구해보자.

입력

첫째 줄에 배열의 크기 N, M과 수행해야 하는 회전의 수 R이 주어진다.

둘째 줄부터 N개의 줄에 배열 A의 원소 Aij가 주어진다.

출력

입력으로 주어진 배열을 R번 회전시킨 결과를 출력한다.

제한

• 2 ≤ N, M ≤ 300
• 1 ≤ R ≤ 10^9
• min(N, M) mod 2 = 0
• 1 ≤ Aij ≤ 10^8

알고리즘 분류

• 구현

풀이

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

이전 배열 돌리기 1과 동일한데 회전 횟수가 10^9이기 때문에 주어진 r을 있는 그대로 돌리면 시간 초과다.

따라서 r을 줄이는 방법을 찾아야 하는데, mod 연산은 쉽게 생각할 수 있다.

2차원 그래프를 직접 그려보면 2*n + 2*m -4만큼 회전하면 그래프는 다시 제자리로 돌아오는 것을 알 수 있다.

위의 식은 2*n + 2*m -4 혹은 n*2 + (m-2) * 2 둘 다 가능하다.

무튼 위의 식으로 사이클의 사이즈를 구했으니, r을 이 횟수로 나누어 주면 x번 제자리로 돌아오고 +y만큼 회전한 그래프를 구할 수 있다.

따라서 우리는 y번 만큼만 회전시키면 된다.

즉 y = r % (2*n + 2*m -4)이란 식이 나온다.

여기서 주의할 점

본인은 그래프의 뎁스에 상관없이 처음  y를 구해놓고, 0,0에서 회전을 시작하는 0뎁스, 1,1에서 회전을 시작하는 1뎁스 등 모든 뎁스에 y만큼 회전을 했다.

여기서 생기는 문제는, 만약 4*5의 그래프가 있다고 하면 0뎁스의 사이클 사이즈는 14이다.

1뎁스의 사이클은 2*3이기 때문에 6이다.

r이 30이라고 하면 0뎁스의 y는 2여야 하고, 1뎁스의 y는 0이어야 한다.

하지만 처음 y를 구해놓고 같은 y값으로 모든 뎁스를 회전하면 0뎁스도 2번 회전, 1뎁스도 2번 회전하기 때문에 제출하면 바로 틀렸다고 나온다.

주어진 테케들은 r의 값이 작아서 (2*n + 2*m -4)으로 나눈 나머지 값에 상관없이 r번 만큼 돌기 때문에 정상적으로 답이 출력되기 때문에 틀린 부분을 찾는 데 애먹었다.

(모든 뎁스를 r 번 만큼 회전하는 것은 당연히 정답이다.)

 

코드

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

lateinit var graph: Array<IntArray>

fun rotate(a: Int, b: Int, t: Int){
    var n = a
    var m = b
    var sr = 0
    var sc = 0
    //바깥 테두리부터
    label@while(n>0 && m>0) {
    	//뎁스별로 전체 회전 횟수 r을 나눈 값이 달라야 한다.
        repeat(t % (n * 2 + (m - 2) * 2)) {
            var r = sr
            var c = sc
            var temp = graph[r][c]
            //좌 세로
            while (r + 1 < sr + n) {
                graph[r + 1][c] = temp.also { temp = graph[r + 1][c] }
                r++
            }
            //하 가로
            while (c + 1 < sc + m) {
                graph[r][c + 1] = temp.also { temp = graph[r][c + 1] }
                c++
            }
            //우 세로
            while (r - 1 >= sr) {
                graph[r - 1][c] = temp.also { temp = graph[r - 1][c] }
                r--
            }
            //상 가로
            while (c - 1 >= sc) {
                graph[r][c - 1] = temp.also { temp = graph[r][c - 1] }
                c--
            }
        }
        sr++
        sc++
        n -= 2
        m -= 2
    }
}

fun main() = with(System.out.bufferedWriter()){
    //input
    val (n,m,r) = getIntList()
    graph = Array(n){ getIntList().toIntArray()}
    //solve
    rotate(n,m,r)
    //output
    for(i in 0 until n){
        for(j in 0 until m){
            write("${graph[i][j]} ")
        }
        write("\n")
    }
    close()
}