[구현] 백준 16927: 배열 돌리기 2

앞으로 매일매일 포스팅을 하기로 했지만, 계절학기가 바빠지고 개인적인 일들이 생기면서 한참만에 포스팅을 한다.

 

우선 배열을 한 칸씩 반시계 방향으로 미루는 방법을 먼저 고안해야 했는데, 나는 큐를 만들어 그 큐에 배열의 테두리 값을 다 밀어넣고, 한 칸씩 미뤄서 큐를 이용해 다시 채워넣는 방식을 택했다.

Queue<Integer> q = new LinkedList<>();
            //좌변
            for(int i=init;i<init+N-1;i++){
                q.offer(targetArr[i][init]);
            }
            //하단
            for(int i=init;i<M+init-1;i++){
                q.offer(targetArr[init+N-1][i]);
            }
            //우변
            for(int i=init+N-1;i>=init+1;i--){
                q.offer(targetArr[i][init+M-1]);
            }
            //상단
            for(int i=init+M-1;i>=init+1;i--){
                q.offer(targetArr[init][i]);
            }
            //한 칸 씩 미뤄서 큐에 있는 값들을 밀어넣음.
            //좌변
            for(int i=init+1;i<init+N;i++){
                targetArr[i][init] = q.poll();
            }
            //하단
            for(int i=init+1;i<init+M;i++){
                targetArr[init+N-1][i] = q.poll();
            }
            //우변
            for(int i=init+N-2;i>=init;i--){
                targetArr[i][init+M-1] = q.poll();
            }
            //상단
            for(int i=init+M-2;i>=init;i--){
                targetArr[init][i] = q.poll();
            }

이렇게만 만들고 채점을 돌렸을 때 시간초과가 떴는데, 이 문제의 핵심 포인트(아직 못 풀었으니 그럴 것 같은...) 인 "한 바퀴 돌아 다시 되돌아오는 경우"를 고려하지 않았기 때문인 듯 하다.

 

한 바퀴 되돌아오는 경우의 수는 고려할 필요가 없으니, 주어진 회전수인 R을 지금 회전시키려는 배열(+부분배열)의 테두리 길이로 나눈 값만큼만 회전시키기로 하였다.

        int len = (2*N + 2*M - 4);

        int rotTimes = R%len;

이를 바탕으로 전체 코드를 아래와 같이 작성하였다.

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;

public class BOJ_16927 {
    static int[][] arr;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] NMR = br.readLine().split(" ");
        int N = Integer.parseInt(NMR[0]);
        int M = Integer.parseInt(NMR[1]);
        int R = Integer.parseInt(NMR[2]);

        arr = new int[N][M];
        for(int i=0;i<N;i++){
            String[] input = br.readLine().split(" ");
            for(int j=0;j<M;j++){
                arr[i][j] = Integer.parseInt(input[j]);
            }
        }
        br.close();

        rotateArr(arr,N,M,R,0);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                bw.write(arr[i][j]+" ");
            }
            bw.write("\n");
        }
        bw.flush();
        bw.close();
    }

    static void rotateArr(int[][] targetArr,int N,int M,int R,int init){

        if(init>Math.min(N,M)/2){
            return;
        }
        //변의 둘레만큼 회전하면 다시 원위치로 돌아옴. 지정 회전수%변의 길이만큼만 회전시키면 됨
        //변의 둘레 - 2*N+2*M - 4
        int len = (2*N + 2*M - 4);

        int rotTimes = R%len;

        while(rotTimes>0){
             //큐를 생성해서 큐에 모든 값을 넣음.
            Queue<Integer> q = new LinkedList<>();
            //좌변
            for(int i=init;i<init+N-1;i++){
                q.offer(targetArr[i][init]);
            }
            //하단
            for(int i=init;i<M+init-1;i++){
                q.offer(targetArr[init+N-1][i]);
            }
            //우변
            for(int i=init+N-1;i>=init+1;i--){
                q.offer(targetArr[i][init+M-1]);
            }
            //상단
            for(int i=init+M-1;i>=init+1;i--){
                q.offer(targetArr[init][i]);
            }
            //한 칸 씩 미뤄서 큐에 있는 값들을 밀어넣음.
            //좌변
            for(int i=init+1;i<init+N;i++){
                targetArr[i][init] = q.poll();
            }
            //하단
            for(int i=init+1;i<init+M;i++){
                targetArr[init+N-1][i] = q.poll();
            }
            //우변
            for(int i=init+N-2;i>=init;i--){
                targetArr[i][init+M-1] = q.poll();
            }
            //상단
            for(int i=init+M-2;i>=init;i--){
                targetArr[init][i] = q.poll();
            }
            rotTimes--;
        }

        rotateArr(targetArr,N-2,M-2,R,init+1);
    }
}

이 코드로 주어진 테스트케이스들을 통과하고, 내가 임의로 만들어 넣은 테스트케이스들도 무난히 통과하였다.

 

그런데! 계속 틀렸다... 혹시 출력할 때 여백이 잘못된 건가? 해서 여백이 아예 안 나오는 방식으로도 만들어 보고, 극단적인 경우도 나름대로 생각해서 넣어 봤는데 계속 계속 계속! 틀렸다.

 

한참을 고생하다가 답을 알아냈는데, N,M이 계속 갱신됨에도 불구하고 그것을 바탕으로 재귀함수의 base case를 작성해서 틀린 것이었다.

 

미리 전체 N,M의 크기로 구한 depth 값으로 base case를 구현하여 문제풀이에 성공하였다.

 

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;

public class BOJ_16927 {
    static int[][] arr;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] NMR = br.readLine().split(" ");
        int N = Integer.parseInt(NMR[0]);
        int M = Integer.parseInt(NMR[1]);
        int R = Integer.parseInt(NMR[2]);

        arr = new int[N][M];
        for(int i=0;i<N;i++){
            String[] input = br.readLine().split(" ");
            for(int j=0;j<M;j++){
                arr[i][j] = Integer.parseInt(input[j]);
            }
        }
        br.close();

        rotateArr(arr,N,M,R,Math.min(N,M)/2,0);
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                bw.write(arr[i][j]+" ");
            }
            bw.write("\n");
        }
        bw.flush();
        bw.close();
    }

    static void rotateArr(int[][] targetArr,int N,int M,int R,int depth,int init){

        if(init>=depth){
            return;
        }
        //변의 둘레만큼 회전하면 다시 원위치로 돌아옴. 지정 회전수%변의 길이만큼만 회전시키면 됨
        //변의 둘레 - 2*N+2*M - 4
        int len = (2*N + 2*M - 4);

        int rotTimes = R%len;

        while(rotTimes>0){
             //큐를 생성해서 큐에 모든 값을 넣음.
            Queue<Integer> q = new LinkedList<>();
            //좌변
            for(int i=init;i<init+N-1;i++){
                q.offer(targetArr[i][init]);
            }
            //하단
            for(int i=init;i<M+init-1;i++){
                q.offer(targetArr[init+N-1][i]);
            }
            //우변
            for(int i=init+N-1;i>=init+1;i--){
                q.offer(targetArr[i][init+M-1]);
            }
            //상단
            for(int i=init+M-1;i>=init+1;i--){
                q.offer(targetArr[init][i]);
            }
            //한 칸 씩 미뤄서 큐에 있는 값들을 밀어넣음.
            //좌변
            for(int i=init+1;i<init+N;i++){
                targetArr[i][init] = q.poll();
            }
            //하단
            for(int i=init+1;i<init+M;i++){
                targetArr[init+N-1][i] = q.poll();
            }
            //우변
            for(int i=init+N-2;i>=init;i--){
                targetArr[i][init+M-1] = q.poll();
            }
            //상단
            for(int i=init+M-2;i>=init;i--){
                targetArr[init][i] = q.poll();
            }
            rotTimes--;
        }

        rotateArr(targetArr,N-2,M-2,R,depth,init+1);
    }
}

 

이번 문제로 고생하면서 느낀 점은, 1) 재귀함수를 구성할 때 베이스케이스 구성을 더 신중히 할 것. 2) 재귀함수에 전달하는 값은 가능하면 다른 값을 사용할 것. 이다. 이 문제의 경우 사실 R은 주어진 값을 그대로 활용하는 거니 문제가 없더라도, N,M의 값은 배열을 구성할 때 주어지는 고정된 값인데 그걸 재귀함수에서 -2씩 갱신하여 쓰면서 재귀함수의 매개변수에도 똑같은 변수명을 썼기에 저게 틀렸을 거라는 생각조차 못 했지 않나 싶다. rowLen, colLen 정도로만 쓰고 그것을 base case에 적용하려고 했으면 금방 뭐가 문제인지 찾았을 것이다.