Baekjoon[17406] - 배열 돌리기 4

링크

17406번: 배열 돌리기 4

문제설명

• 완전탐색 + 시뮬레이션

문제풀이

• 완전탐색 + 시뮬레이션
• 회전하는 함수는 규칙성이 하, 우, 좌, 상으로 i*2 만큼 swap하고, 마지막은 안한다(또는 한번더 swap해주면 된다.)

문제코드

package baekjoon;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.StringTokenizer;



public class Main17406 {

    public static int[][] dir = {
            {1,0},    //하
            {0,1},    //우
            {-1,0},    //상
            {0,-1}    //좌
    };

    public static int Ans=Integer.MAX_VALUE;
    public static int N;
    public static int M;
    public static int K;
    public static int[][] map;
    public static int[][] n_map;
    public static int[][] oper;
    public static int[] serial;

    public static int Value() {
        int ans = Integer.MAX_VALUE;
        int temp;
        for (int i = 0; i < N; i++) {
            temp=0;
            for (int j = 0; j < M; j++) {
                temp+=n_map[i][j];
            }
            ans = Math.min(ans, temp);
        }
        return ans;
    }

    public static void swap(int r, int c, int now_dir) {
        int temp=0;
        int nr = r + dir[now_dir][0];
        int nc = c + dir[now_dir][1];
        temp = n_map[r][c];
        n_map[r][c] = n_map[nr][nc];
        n_map[nr][nc] = temp;
    }

    public static void Rotate(int r, int c, int s) {
        int nr;
        int nc;
//        회전 사각형 크기
        for (int i = 1; i <= s; i++) {
//        회전하는 사각형 왼쪽 위의 rc좌표
            nr = r-i;
            nc = c-i;
//            회전방향 하, 우, 상, 좌
            for (int d = 0; d < 4; d++) {
//                변의 크기
                for (int j = 0; j < i*2; j++) {
                    swap(nr,nc,d);
                    nr += dir[d][0];
                    nc += dir[d][1];
                }
            }
//            마지막 swap제외하기위해서 swap 한번 더함
            swap(nr,nc,1);
        }
    }

    public static void Search(int cnt, int flag) {
        if(cnt==K) {
//            oper의 순서(serial)기준으로 rotate 실행 후 행렬의 값 갱신.
//            System.out.println(Arrays.toString(serial));
//            n_map 갱신
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < M; j++) {
                    n_map[i][j] = map[i][j];
                }
            }
            for (int i = 0; i < K; i++) {
                Rotate(oper[serial[i]][0],
                        oper[serial[i]][1],
                        oper[serial[i]][2]);
            }


            Ans = Math.min(Ans, Value());
            return;
        }
//        이 경우는 가지치기 못함. 왜냐하면 진행과정중에 전부 다 바뀌는거라 예상못함.

        for (int i = 0; i < K; i++) {
//            안썼다면
            if((flag & 1<<i)==0) {
                serial[cnt]=i;
                Search(cnt+1,flag | 1<<i);
            }
        }
    }

    public static void main(String[] args) throws NumberFormatException, IOException {
        System.setIn(new FileInputStream("res/baekjoon/17406.txt"));
        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];
        n_map = new int [N][M];
        oper = new int[K][3];
        serial = new int[K];

        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());
                n_map[i][j] = map[i][j];
            }
        }

        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());
            oper[i][0] = Integer.parseInt(st.nextToken())-1;
            oper[i][1] = Integer.parseInt(st.nextToken())-1;
            oper[i][2] = Integer.parseInt(st.nextToken());
        }

//        Rotate(3,1,1);
//        Rotate(2,3,2);
        Search(0,0);

        System.out.println(Ans);
//        초기화
        Ans=0;
    }
}

아쉬운점

• 문제 제대로 안읽음
  • 배열 (1,1)부터 시작함
  • input을 -1씩해서 받으면 됨
  • rotate 순서 바꿔도 되는건줄 몰랐었음
    • K! 조합만들어서 그 중 최소값.

잘한점

• rotate 메서드를 swap와 direction을 적절히 섞어서 잘 만들었음, 한칸씩 이동하면서 swap
• 마지막에 한번더 swap해주면 됨. 굳이 if문 써서 비교하면서 하는거보다 편한듯
• 시간(45분)