[백준/JAVA] 17406번: 배열 돌리기 4

📖 문제

17406번: 배열 돌리기 4

 

 

💡  풀이 방식

• 구현 

. dx/dy 배열을 반시계 방향 순서로 작성한다. (반대 방향에서 값 끌어서 가져오기)

. 회전 순서 순열을 구하고, 리스트에 저장한다. (perm 메소드)

. 회전 순서 순열 리스트를 돌면서, 순서대로 회전 연산을 수행한다. 그리고 이 중 행들의 합 중 최솟값을 구하고 갱신한다.

 

 

 

💥 유의사항

- nx와 ny의 범위를 잘 지정해주어야 한다.

- 이동하면서 빠뜨린 값을 잘 채워넣어주어야 한다.

- 값을 밀면서 이동하는 게 아니라, 값을 가져오는 식으로 진행했다.

(시계 방향 회전이라고 했으니까 반시계 방향으로 이동해서 해당 위치의 값을 현재 위치로 가져오기)

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int min = Integer.MAX_VALUE; // 가장 작은 행들의 합
    
    static int[] dx = {1,0,-1,0};   // 남동북서 (반시계 방향꺼 끌어오기)
    static int[] dy = {0,1,0,-1};
    
    static int N, M, K;
    static int[][] map, rotateArr, tmp; // 원래 배열, 회전 정보, 임시 저장 배열
    
    static int[] numbers;      // 순열 배열
    static boolean[] visited;  // 중복 제거용 방문 배열
    static List<int[]> permList = new ArrayList<>();    // 회전 순서 순열 리스트
    
    public static void main(String[] args) throws IOException {
        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 + 1][M + 1];
        for(int i = 1 ; i <= N ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j = 1 ; j <= M ; j++) {
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        // 회전 연산 정보
        rotateArr = new int[K][3];
        for(int i = 0 ; i < K ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            rotateArr[i][0] = Integer.parseInt(st.nextToken());
            rotateArr[i][1] = Integer.parseInt(st.nextToken());
            rotateArr[i][2] = Integer.parseInt(st.nextToken());
        }
        
        // 1. 회전 순서 순열 리스트 구하기 (순열)
        numbers = new int[K];
        visited = new boolean[K];
        perm(0);
        
        // 2. 회전 연산 순서 리스트 돌면서 순서대로 회전시키고 그 중 최솟값 찾기
        for(int i = 0 ; i < permList.size() ; i++) {
            // 회전시킬 배열 생성하고 깊은 복사
            tmp = new int[N + 1][M + 1];
 
            for(int r = 1 ; r <= N ; r++) {
                for(int c = 1 ; c <= M ; c++) {
                    tmp[r][c] = map[r][c];
                }
            }
            
            // r,c,s 가진 int 배열 가져오기
            int[] rotateInfo = permList.get(i);
            
            // 순서에 맞게 회전
            for(int r : rotateInfo) {
                rotate(rotateArr[r][0] , rotateArr[r][1], rotateArr[r][2]);
            }
 
            // 회전한 배열 탐색해 최소 행 합 계산
            searchMinRowSum();
        }
        
        System.out.println(min);
    }
    
    // 순열 구하는 메소드
    private static void perm(int depth) {
        if(depth == K) {
            permList.add(numbers.clone());
            return;
        }
        
        for(int i = 0 ; i < K ; i++) {
            if(!visited[i]) {
                numbers[depth] = i;
                visited[i] = true;
                perm(depth + 1);
                visited[i] = false;
            }
        }
    }
    
    // 배열 회전 시키는 메소드
    public static void rotate(int r, int c, int s) {
        int sr = r-s;
        int sc = c-s;
        int er = r+s;
        int ec = c+s;
        
        // 부분네모 (왼쪽 위 대각선 꼭대기 위치)
        for(int i = 0 ; i < (er - sr + 1) / 2 ; i++) {
            
            int firstR = sr + i;
            int firstC = sc + i;
            
            int firstVal = tmp[firstR][firstC];    // 초기값 미리 따로 저장
            
            int R = firstR;
            int C = firstC;
            
            int cnt = 0;
            while(cnt < 4) {    // 4방향 배열 한 바퀴 다 돌기 전까지
                int nr = R + dx[cnt];
                int nc = C + dy[cnt];
                
                // 🔔 범위에 유의하기!
                if((sr + i <= nr) && (nr <= er - i) && (sc + i <= nc) && (nc <= ec - i)) {
                    tmp[R][C] = tmp[nr][nc];
                    R = nr;
                    C = nc;
                }
                else {    // 범위 벗어나면, 방향 전환
                    cnt++;
                }
            }
 
            tmp[firstR][firstC + 1] = firstVal;    // 빠졌던 초기값 채워넣기
        }
    }
    
    // 행들의 합 중 최솟값 구하는 메소드
    private static void searchMinRowSum() {
        for(int i = 1 ; i <= N ; i++) {
            int sum = 0;
            
            for(int j = 1 ; j <= M ; j++) {
                sum += tmp[i][j];
            }
            
            min = Math.min(min, sum);
        }
    }
}
 

 

 

➕ 다른 풀이 방식

직접 네 변을 회전하면서 for문으로 구하셨다.

[백준]17406: 배열 돌리기4 - JAVA

[백준]17406: 배열 돌리기4(java)

 

---

💦 어려웠던 점

- 순열 구하고, 이 생성된 순열의 결과를 String형으로 저장해 뽑아 쓰려고 했는데 잘 되지 않았다,,

그래서 다른 분 코드를 보고 int[]형으로 받아 작성했다.

static List<int[]> permList = new ArrayList<>();    // 회전 순서 순열 리스트

.
.

int[] rotateInfo = permList.get(i);		// r,c,s 가진 int 배열 가져오기

for(int r : rotateInfo) {		// 순서에 맞게 회전
    rotate(rotateArr[r][0] , rotateArr[r][1], rotateArr[r][2]);
}

 

 

- 문제에는 시계 방향으로 회전한다고 되어있는데, 코드를 보면 반시계 방향 위치에서의 값을 끌어와 현재 위치에 저장하곤 한다.

- 변수가 많아 이름을 잘 설정하고, 잘 활용해줘야 한다.

- 순서를 작성해놓고 해야지 안 그러면 중간에 뭐해야할지 멍해지는 모먼트가 온다,,

 

 

🧐 새로 알게 된 내용

- 배열 복사는 .clone() 사용

- 부분네모의 경우, 시작 위치만 잘 잡으면 되는 것 같다. (O(N). 보통 범위 / 2)

 

1회독	2회독	3회독	4회독	5회독
V	240502

 

(+240502 2회독)

코드 확인하기

import java.util.*;
import java.io.*;
 
public class Main {
    static int N,M,K;
    static int[][] map, cycle;
    
    static int min = Integer.MAX_VALUE;
    
    public static void main(String[] args) throws IOException {
        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());
            }
        }
        
        cycle = new int[K][3];
        for(int k = 0 ; k < K ; k++) {
            st = new StringTokenizer(br.readLine(), " ");
            cycle[k][0] = Integer.parseInt(st.nextToken()) -1;
            cycle[k][1] = Integer.parseInt(st.nextToken()) -1;
            cycle[k][2] = Integer.parseInt(st.nextToken());
        }
        
        perm(0, new int[K], new boolean[K]);
        System.out.println(min);
    }
    
    private static void perm(int cnt, int[] arr, boolean[] visited) {
        if(cnt == K) {
            rotate(arr);
            return;
        }
        
        for(int i = 0 ; i < K ; i++) {
            if(!visited[i]) {
                visited[i] = true;
                arr[cnt] = i;
                perm(cnt + 1, arr, visited);
                visited[i] = false;
            }
        }
    }
    
    private static void rotate(int[] arr) {
        int[][] copy = new int[N][M];
        for(int i = 0 ; i < N ; i++) {
            for(int j = 0 ; j < M ; j++) {
                copy[i][j] = map[i][j];
            }
        }
        
        for(int i = 0 ; i < K ; i++) {
            int r = cycle[arr[i]][0];
            int c = cycle[arr[i]][1];
            int s = cycle[arr[i]][2];
            
            for(int t = 1 ; t <= s ; t++) {
                // 위
                int upTmp = copy[r-t][c+t];
                for(int y = c+t ; y > c-t ; y--) {
                    copy[r-t][y] = copy[r-t][y-1];
                }
                
                // 오른쪽
                int rightTmp = copy[r+t][c+t];
                for(int x = r+t ; x > r-t ; x--) {
                    copy[x][c+t] = copy[x-1][c+t];
                }
                copy[r-t+1][c+t] = upTmp;
                
                // 아래
                int leftTmp = copy[r+t][c-t];
                for(int y = c-t ; y < c+t ; y++) {
                    copy[r+t][y] = copy[r+t][y+1];
                }
                copy[r+t][c+t-1] = rightTmp;
                
                // 왼쪽
                for(int x = r-t ; x < r+t ; x++) {
                    copy[x][c-t] = copy[x+1][c-t];
                }
                copy[r+t-1][c-t] = leftTmp;
            }
        }
        
        for(int i = 0 ; i < N ; i++) {
            int sum = 0;
            for(int j = 0 ; j < M ; j++) {
                sum += copy[i][j];
            }
            
            min = Math.min(min, sum);
        }
    }
}
 

---

(참고)

[Java] 백준 / 배열 돌리기 4 / 17406번

[백준/JAVA] 16926번: 배열 돌리기 1