SW 역량 테스트 A형 기출 문제 (배열 돌리기 4)

[배열 돌리기 4 _ 18406]

 

 

* 조건

1. 회전 연산(r, c, s)가 주어진다
   
   • 왼쪽 상단 좌표: (r-s, c-s)
   • 오른쪽 하단 좌표: (r+s, c+s)
   • 위 좌표로 구성된 사각형을 큰 둘레부터 시계방향으로 회전한다
2. 회전 연산 수만큼 회전한 뒤, 각 행의 합 중에서 최솟값을 구한다
3. 회전 연산이 2개 이상이면 순열을 통해 여러 경우의 수를 고려한다

* 알고리즘

• 시뮬레이션
• 순열을 활용한 경우의 수: 브루트포스

* 로직(Logic)

• 회전 연산이 주어지면 왼쪽 상단 좌표, 오른쪽 하단 좌표로 변환한 뒤 리스트에 넣는다
• 회전 연산이 가능한 모든 경우의 수를 고려한다
• 경우의 수를 진행할 때 회전을 시킨다
  • 초기 좌 상단(left_top), 우 하단(right_bottom) 좌표를 기본으로 담아놓는다
  • 오른쪽 방향부터 진행하면서 좌 상단과 우 하단의 범위를 벗어나면 다음 방향(여기선 아래)으로 변경시킨다
  • 만약 범위 내에 있다면 다음 값의 좌표와 값은 큐에 보관하고, 다음 좌표의 값 = 현재 좌표의 값으로 덮어준다
  • 만약 한 바퀴를 돌고 처음 출발 좌표로 돌아오면 left_top과 right_bottom을 각각 갱신한다
  • 갱신한 후 서로의 좌표가 같다면 1개만 남았기 때문에 회전시킬 필요가 없다
  • 혹시 모를 직사각형 모양에 대비해 left_top의 좌표와 right_bottom의 좌표에 범위가 생기지 않아도 break를 걸어줬다
• 회전이 적용된 배열을 리턴받고, 변경된 배열을 가지고 각 행의 합 중에서 최솟값을 구한다
• 이러한 과정을 반복하며 최솟값을 갱신해간다

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

//회전 연산자 보관 클래스
class Position_17406 {
    public int y_leftTop, x_leftTop;
    public int y_rightBottom, x_rightBottom;

    public Position_17406(int y_leftTop, int x_leftTop, int y_rightBottom, int x_rightBottom) {
        this.y_leftTop = y_leftTop;
        this.x_leftTop = x_leftTop;
        this.y_rightBottom = y_rightBottom;
        this.x_rightBottom = x_rightBottom;
    }
}

//회전시킬때 좌표를 담는 클래스
class Pos_17406 {
    public int y, x, value;

    public Pos_17406(int y, int x, int value) {
        this.y = y;
        this.x = x;
        this.value = value;
    }
}

public class Problem_17406 {

    static int N, M;
    static int[][] map;
    static ArrayList<Position_17406> rotateOperations = new ArrayList<>();
    static int rotateOperNum;
    static boolean[] operUsed;

    static boolean[][] checked; //회전 마킹

    //오른 -> 아래 -> 왼 -> 위
    static int[] dy = {0, 1, 0, -1};
    static int[] dx = {1, 0, -1, 0};
    static int answer = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        String config = br.readLine();
        st = new StringTokenizer(config, " ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());   //회전 연산 개수

        //map 넣기
        map = new int[N+1][M+1];
        for(int i=1; i<=N; ++i){
            String input = br.readLine();
            st = new StringTokenizer(input, " ");
            for(int j=1; j<=M; ++j){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        //회전 연산 받기
        for(int i=0; i<k; ++i){
            String input = br.readLine();
            st = new StringTokenizer(input, " ");
            int r = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            int s = Integer.parseInt(st.nextToken());

            int y_leftTop = r - s;
            int x_leftTop = c - s;
            int y_rightTop = r + s;
            int x_rightTop = c + s;

            rotateOperations.add(new Position_17406(y_leftTop, x_leftTop, y_rightTop, x_rightTop));
        }
        rotateOperNum = rotateOperations.size();    //회전 연산 개수

        //회전 연산의 개수에 맞게끔 순열로 경우의 수 구하기
        operUsed = new boolean[rotateOperNum];

        int count = 0;
        int index = 0;
        int[][] tmpMap = new int[N+1][M+1];
        doProcess(index, count, tmpMap);

        System.out.println(answer);

    }

    private static void doProcess(int index, int count, int[][] tmpMap) {
        //각 단계별로 회전 적용
        int[][] changedMap = new int[N+1][M+1];
        if(count >= 1){
            //해당 index의 회전 명령 좌표를 가지고 회전
            changedMap = doRotate(index, tmpMap);
        }

        //최종 회전까지 다했다면
        if(count == rotateOperNum){
            int min = getMinValue(changedMap);

            //각 행의 최솟값을 구하고 -> 최솟값 도출
            answer = Math.min(answer, min);
            return;
        }

        for(int i=0; i<rotateOperNum; ++i){
            if(!operUsed[i]){

                //시작할 땐 초기화
                if(count == 0){
                    for(int a=1; a<=N; ++a){
                        for(int b=1; b<=M; ++b){
                            changedMap[a][b] = map[a][b];
                        }
                    }
                }
                operUsed[i] = true;
                doProcess(i, count+1, changedMap);
                operUsed[i] = false;
            }
        }
    }

    private static int getMinValue(int[][] currentMap) {
        int min = Integer.MAX_VALUE;
        for(int i=1; i<=N; ++i){
            int acc = 0;
            for(int j=1; j<=M; ++j){
                acc += currentMap[i][j];
            }
            min = Math.min(min, acc);
        }

        return min;
    }

    private static int[][] doRotate(int index, int[][] currentMap) {
        int[][] tmpMap = new int[N+1][M+1];
        for(int i=1; i<=N; ++i){
            for(int j=1; j<=M; ++j){
                tmpMap[i][j] = currentMap[i][j];
            }
        }

        //오 -> 아 -> 왼 -> 위
        checked = new boolean[N+1][M+1];

        //dir = 0, 1, 2, 3까지 진행
        //초기에 왼쪽 상단의 좌표를 담아줌
        int baseY_leftTop = rotateOperations.get(index).y_leftTop;
        int baseX_leftTop = rotateOperations.get(index).x_leftTop;
        int baseY_rightBottom = rotateOperations.get(index).y_rightBottom;
        int baseX_rightBottom = rotateOperations.get(index).x_rightBottom;
        Queue<Pos_17406> queue = new LinkedList<>();
        queue.offer(new Pos_17406(baseY_leftTop, baseX_leftTop, tmpMap[baseY_leftTop][baseX_leftTop]));

        int dir = 0;
        while (true){
            Pos_17406 q = queue.poll();
            int currentY = q.y;
            int currentX = q.x;

            int moveY = currentY + dy[dir];
            int moveX = currentX + dx[dir];

            //회전하고 출발지점으로 돌아왔다면 -> 출발지를 새로 바꾸고 다시 시작
            if(moveY == baseY_leftTop && moveX == baseX_leftTop){
                tmpMap[moveY][moveX] = q.value;

                baseY_leftTop = baseY_leftTop + 1;
                baseX_leftTop = baseX_leftTop + 1;
                baseY_rightBottom = baseY_rightBottom - 1;
                baseX_rightBottom = baseX_rightBottom - 1;
                queue.offer(new Pos_17406(baseY_leftTop, baseX_leftTop, tmpMap[baseY_leftTop][baseX_leftTop]));

                //마지막 한칸 남았을 때는 종료
                if(baseY_leftTop == baseY_rightBottom && baseX_leftTop == baseX_rightBottom) break;

                //직사각형인 경우
                if(baseY_leftTop > baseY_rightBottom || baseX_leftTop > baseX_rightBottom) break;
                if(checked[baseY_leftTop][baseX_leftTop] || checked[baseY_rightBottom][baseX_rightBottom]) break;

                dir = 0;
                continue;
            }

            //명령에 있는 범위를 벗어나면 안됨
            if(moveY >= baseY_leftTop && moveY <= baseY_rightBottom &&
                            moveX >= baseX_leftTop && moveX <= baseX_rightBottom){

                if(!checked[moveY][moveX]){
                    //다음 값은 리스트에 넣고 다음 위치에 현재 값을 넣기
                    queue.offer(new Pos_17406(moveY, moveX, tmpMap[moveY][moveX]));
                    checked[moveY][moveX] = true;

                    tmpMap[moveY][moveX] = q.value;
                }
            }

            //범위를 넘어가면 -> 다음 방향으로
            else {
                queue.offer(q);
                dir++;
            }
        }

        return tmpMap;
    }
}

 

전형적인 브루트 포스 + 시뮬레이션 문제였다. 여기서 회전을 시킬 때 배열을 새로 리턴해야 중간에 모든 경우의 수를 변화없이 구할 수 있는데 순간 간과했던거 같다.. 클래스도 2개까진 만들 필요도 없을 거 같지만 다음번에 리팩토링 해봐야겠다.