백준 표회전 - boj2932

2932번: 표 회전

백준의 표 회전 문제입니다.

이 문제...분명 풀었을 때는 실버 3이었던 것 같은데 실버 2가 되었네요. 사실 반년 전에 푼 문제인데 아직도 풀이방법을 잊을 수 없는... 그런 매콤한 추억이 있는 문제랍니다.

제출 300, 정답 98, 맞힌 사람 73으로 정답 비율이 35%입니다. 그런데 백준에서 맞힌 사람 200명 안넘으면 티어를 믿으시면 안 됩니다. 보통 고수들이 새로운 문제 나왔다고 찍먹해보거나 아무것도 모르는 뉴비들이 랜덤뽑기로 풀게 되거든요. 뉴비들이 랜뽑으로 문제에 접근하는 경우는 드물고, 고수들이 대부분 기미를 해보시는데요.

그런데 정답률이 35%...?

정신 건강을 위해 안 건드는 편이 좋습니다. 이런 사실을 몰랐던 저도 티어 보고 쉬운 문제인 줄 알았는데 며칠 눈물뽑았습니다.

맞춘 사람 100 밑인데 티어가 실버? 그럼 그냥 골드 정도 문제로 상정하고 단단히 각오하셔야 합니다.

 

문제 설명

문제

상근이는 N×N 표를 만들었다. 표에는 1부터 N2까지의 수가 행 우선 순서(row-major order)에 따라 쓰여져 있다. 표가 수행할 수 있는 연산은 아래와 같이 두 가지이다.

1. 행을 회전시킨다 - 한 행을 골라 오른쪽으로 한 칸 회전시킨다. 마지막 열에 있던 수가 가장 첫 열에 오게 된다.
2. 열을 회전시킨다 - 한 열을 골라 아래로 한 칸 회전시킨다. 마지막 행에 있던 수가 가장 첫 행에 오게 된다.

상근이는 수 X를 (R,C)로 이동시키려고 한다. 이때, 상근이는 다음과 같은 과정을 거쳐서 수를 찾는다.

• X의 위치가 C열이 될 때 까지, X가 있는 행을 회전시킨다.
• X의 위치가 R행이 될 때 까지, X가 있는 열을 회전시킨다.

아래 그림은 6을 (3,4)에 이동시키는 방법이다.

상근이는 숫자 K개를 이동시키려고 한다. 한 숫자를 이동시키고 난 후에, 바로 그 다음 숫자를 이동시키며, 다음 숫자를 이동시킬 때, 표에 들어있는 수를 처음 상태로 되돌리지 않는다. 숫자 K개를 이동시키는데 필요한 회전의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 표의 크기 N(2 ≤ N ≤ 10000)과 이동시키려고 하는 숫자의 수 K(1 ≤ K ≤ 1000)이 주어진다.

다음 K개 줄에는 이동시키려고 하는 숫자 X와 위치 R, C가 주어진다. (1 ≤ X ≤ N2, 1 ≤ R,C ≤ N)

항상 입력으로 주어진 순서대로 하나씩 이동시켜야 한다.

출력

총 K개 줄에 각각의 숫자를 이동시키는데 필요한 회전의 수를 출력한다.

 

풀이

개인적으로 이 문제의 키포인트는 다음 두 가지라고 생각합니다.

1. 표에서 특정 숫자의 초기 위치는 계산으로 알 수 있다.

2. 그러므로 이동하지 않는 수는 추적하지 않아도 된다.

 

문제의 입력제한을 잠깐 볼까요.

표가 NxN, 즉 정사각형으로 들어오는데 N이 1만으로 들어옵니다.

최악의 경우 Array(10000){IntArray(10000)}이 되는데, 즉 4byte짜리 Int를 1억 개 저장해야 한다는 건데요.

그러면 400000000byte가 되는데...이게 400MB입니다.

메모리 제한을 한참 넘어가죠...

그래서 전체 수열을 저장해서 시뮬레이션 방식으로 편하게 풀어보겠다는 생각은 진작에 접으셔야 합니다.(저는 몰라서 이 방식으로 3트 했습니다)

그러면 이제 알고리즘을 좀 풀어보신 분들이면 움직일 애들만 저장해야겠다는 생각을 하시게 될 겁니다.

어떻게...?

바로 그 어떻게를 구현하는 것이 문제입니다.

다행히도 숫자를 움직이는 방식은 정해져 있습니다. 1. 행 회전, 2. 열 회전입니다. 그럼 순서에 맞게 옮기기만 하면 되는데요.

문제에서 요구하는 것은 각 숫자를 이동시키는 데 필요한 회전 수입니다. 그리고 어떤 숫자를 옮길 것인지는 처음에 다 알려주죠. 그래서 이 문제는 입력 하나 받아서 회전시켜보고 회전 수 출력하고... 이런 방식으로 풀면 안 됩니다.

어떤 수를 움직여야 하는지 처음에 다 저장해서, 하나의 수를 옮길 때 저장되어 있는 다른 수의 위치가 변경되는지를 추적해야 하기 때문입니다.

즉 첫번째 수를 옮길 때 두번째 수의 위치가 달라질 경우를 생각해야 한다는 뜻이죠.

 

최종 로직

1. 옮겨지는 수의 초기 위치를 저장한다.

2. 수를 옮기되, 옮기는 과정에서 다른 수의 위치가 변경될 경우 추적한다.

가 끝입니다.

그래서 목표 위치를 저장하는 array와 수의 현재 위치를 저장하는 array, 총 두 개가 필요합니다.

 

정답

package silver2

fun main() = with(System.`in`.bufferedReader()) {
    val (N, M) = readLine().split(" ").map { it.toInt() }

	// 목표 위치 저장(최종적으로 어디로 보내야 하는지)
    var RClist = Array(M) { shortArrayOf(0, 0) }

    var matrix_r = IntArray(1000)
    var matrix_c = IntArray(1000)

    for (i in 0 until M) {
        val (X, R, C) = readLine().split(" ").map { it.toInt() }
        RClist[i] = shortArrayOf((R - 1).toShort(), (C - 1).toShort())

        // 입력받은 값의 초기 r위치 저장
        matrix_r[i] = (X - 1) / N
        // 입력받은 값의 초기 c위치 저장
        matrix_c[i] = (X - 1) % N
    }

	// r값을 기준으로 행렬을 회전시킬 때 영향을 받는 다른 수가 있는지 확인해야 한다
	// 있을 경우 그 수도 회전시켜주고 최종 위치를 저장해 주어야 함
    fun RotateRow(r: Int, p: Int) {
        for (i in 0 until M) {
            if (matrix_r[i] == r) {
                matrix_c[i] = (matrix_c[i] + p) % N
            }
        }
    }

	// RotateRow()와 동일
    fun RotateColumn(c: Int, p: Int) {
        for (i in 0 until M) {
            if (matrix_c[i] == c) {
                matrix_r[i] = (matrix_r[i] + p) % N
            }
        }
    }

    for (i in 0 until M) {
		// 목표 위치까지 얼마나 움직여야 하는지 저장
        var r_move = RClist[i][0] - matrix_r[i]
        var c_move = RClist[i][1] - matrix_c[i]
		// OutOfRange일 때 N을 더해서 범위 안으로 넣어준다(회전하기 때문)
        if (r_move < 0) r_move += N
        if (c_move < 0) c_move += N

        RotateRow(matrix_r[i], c_move)
        RotateColumn(matrix_c[i], r_move)

        println(r_move + c_move)
    }
}