링크

17406 배열 돌리기 4

문제

풀이

처음에 bfs로 한칸씩 밀다가 벽에 만나면 90도 올리고 이런식으로 풀었지만 시간초과가 발생해서 처음부터 다시 풀었다.

그래서 내가 풀이 한 방법은
1. dfs를 통해서 순번을 정했다.
2. rotate를 해서 돌린다.
3. 행의 최솟값을 구한다.

여기서 가장 화가 나는 부분이 rotate부분인데 rotate부분만 좀 보면

이렇게 수기로 작성하다 보니 규칙이 보였다.
나는 s만큼 반복문을 수행한다. 한번 한번 수행할때마다 좁아져야하기 때문에 맨위를 결정하는 startX에 + 1, 맨 마지막인 EndX - 1, 맨 오른쪽인 startY + 1, 맨 왼쪽인 endY - 1을 해주면서 계속 rotate를 했다.

1. 오른쪽으로 이동하는 경우
   오른쪽으로 이동하는 경우는 (0,5)인 부분을 저장해두고 (0,4)인부분을 (0,5)로 이동시키고 (0,4)인 부분에다가 (0,3)을 이동시키고 쭉쭉쭊 수행해준다.

2. 아래쪽으로 이동하는 경우
   (4,5)의 값을 저장해두고 (3,5)의 값을 (4,5)에 넣고 (3,5)에 (2,5)의 값을 넣어주고 쭉쭉 하다보면 (0,5)의 값과 (1,5)의 값이 같아진다.
   그러기 때문에 (1,5)에 수동으로 위에 저장해뒀던 (0,5)인 부분을 넣어줘야 한다

한번 수기로 작성해보면 문제풀이에 큰 도움이 된다. 이렇게 돌리면서 최솟값을 찾으면 된다.

구현문제를 원트에 거의 못풀어서 연습 좀 해야겠다.

코드

import java.awt.*;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.sql.Array;
import java.util.*;
import java.util.List;

public class Main{
    public static int[][] map;
    public static int[][] copyMap;
    public static int n;
    public static int m;
    public static int k;
    public static int min = Integer.MAX_VALUE;
    public static boolean[] visited;
    public static List[] list;
    public static List<Integer> order = new ArrayList<>();
    public static int[] dx = {0, 1, 0, -1};
    public static int[] dy = {1, 0, -1, 0};

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());

        map = new int[n][m];
        for(int i=0;i<n;i++){
            st = new StringTokenizer(br.readLine());

            for(int j=0;j<m;j++){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
//            System.out.println(Arrays.toString(map[i]));
        }

        list = new ArrayList[k];
        visited = new boolean[k];

        for(int i=0;i<list.length;i++){
            list[i] = new ArrayList<>();
        }

        for(int i=0;i<k;i++){

            st = new StringTokenizer(br.readLine());
            int r = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            int s = Integer.parseInt(st.nextToken());

            list[i].add(r);
            list[i].add(c);
            list[i].add(s);

        }

        dfs(0);
        System.out.println(min);

    }

    //순서 정하기
    public static void dfs(int dept){
        if(dept == k){
//            System.out.println("order = " + order);
            copyMap = new int[map.length][map[0].length];
            func();
            return;
        }
        for(int i=0;i<k;i++){
            if(!visited[i]){
                visited[i] = true;
                order.add(i);
                dfs(dept+1);
                order.remove(order.size() - 1);
                visited[i] = false;
            }
        }
    }

    public static void func(){
        for(int j=0;j<copyMap.length;j++){
            for(int k=0;k<copyMap[j].length;k++){
                copyMap[j][k] = map[j][k];
            }
        }

        for(int i=0;i<order.size();i++){
//            System.out.println(order.get(i));

            rotate(order.get(i));
        }

        for(int i=0;i<copyMap.length;i++){
            int sum = 0;
            for(int j=0;j<copyMap[i].length;j++){
                sum += copyMap[i][j];
            }

            min = Math.min(min, sum);
        }

    }

    public static void rotate(int order){
//        System.out.println(list[order]);
        int r = (int)list[order].get(0);
        int c = (int)list[order].get(1);
        int s = (int)list[order].get(2);

        int startX = r - s - 1;
        int startY = c - s - 1;
        int endX = r + s - 1;
        int endY = c + s - 1;

        for(int i=0;i<s;i++){
            int tempStartX = startX + i;
            int tempStartY = startY + i;
            int tempEndX = endX - i;
            int tempEndY = endY - i;

//            System.out.println("startX = " + startX + "  startY = " + startY + " endX = " + endX + " endY = " + endY);

            // 오른쪽 이동
            int rightValue = copyMap[tempStartX][tempEndY];
            for(int j=tempEndY;j>tempStartY;j--){
                copyMap[tempStartX][j] = copyMap[tempStartX][j-1];
            }

            // 아래쪽 이동
            int DownValue = copyMap[tempEndX][tempEndY];
            for(int j=tempEndX;j>tempStartX;j--){
                copyMap[j][tempEndY] = copyMap[j-1][tempEndY];
            }

            copyMap[tempStartX+1][tempEndY] = rightValue;

            // 왼쪽 이동
            int leftValue = copyMap[tempEndX][tempStartY];
            for(int j=tempStartY;j<tempEndY;j++){
                copyMap[tempEndX][j] = copyMap[tempEndX][j+1];
            }

            copyMap[tempEndX][tempEndY-1] = DownValue;

            // 위쪽 이동
            for(int j=tempStartX;j<tempEndX;j++){
                copyMap[j][tempStartY] = copyMap[j+1][tempStartY];
            }

            copyMap[tempEndX - 1][tempStartY] = leftValue;



        }
//        System.out.println("--------makemakemake--------------");
//        for(int k=0;k<copyMap.length;k++) System.out.println(Arrays.toString(copyMap[k]));


    }

}