AngelPlayer`s Diary

링크

https://www.acmicpc.net/problem/17406

 

17406번: 배열 돌리기 4

크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의

www.acmicpc.net

 

 

 

 

문제 해석

배열 A 값 == 각 행에 있는 모든 수의 합 중 최소값

명령 : r c s
가장 왼쪽 위 (r-s, c-s)
가장 오른쪽 아래 (r+s, c+s)인 정사각형으로 시계방향으로 한 칸씩 돌리겠다는 의미


- 입력
첫 번째 줄 : N M K
  N : 세로 크기
  M : 가로 크기
  K : 회전 명령 개수
N개 줄 : 각 행의 값
K개 줄 : r c s
  

- 출력
각 행에 있는 모든 수의 합 중 최소값

 

 

 

풀이 & 코드 해석

배열 돌리기 시리즈의 심화 문제입니다.

 

시작점과 끝점을 구하는 공식이 주어지기 때문에 조건에 맞게 돌리기만 한다면 큰 무리 없이 해결 가능합니다.

 

순서를 임의로 정할 수 있기 때문에 순서를 정하는 순열이 필요합니다.

 

 

 

배열은 0부터 시작해야 하므로 명령의 시작점과 끝점의 계산 후 -1을 해줍니다.

 

 

 

코드

import java.io.*;
import java.util.*;

public class boj17406 {

    static int[] arr_r;
    static int[] arr_c;
    static int[] arr_s;
    static int[][] map;
    static int answer;

    static int[] sel;
    static boolean[] v;

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

        // 첫 번째 줄
        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        map = new int[N][M];
        sel = new int[K];
        v = new boolean[K];

        // N개 줄
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());

            int j = 0;
            while (st.hasMoreTokens()) {
                map[i][j] = Integer.parseInt(st.nextToken());
                j++;
            }
        }
//        print(map);

        arr_r = new int[K];
        arr_c = new int[K];
        arr_s = new int[K];

        // K개 줄
        for (int i = 0; i < K; i++) {
            st = new StringTokenizer(br.readLine());

            arr_r[i] = Integer.parseInt(st.nextToken());
            arr_c[i] = Integer.parseInt(st.nextToken());
            arr_s[i] = Integer.parseInt(st.nextToken());

        }
        answer = Integer.MAX_VALUE;
        recursive(0);
        System.out.println(answer);



    } // [E] main

    static void recursive(int count) {
        if (count == sel.length) {
            int[][] copyMap = new int[map.length][map[0].length];
            for (int i = 0; i < map.length; i++) {
                for (int j = 0; j < map[0].length; j++) {
                    copyMap[i][j] = map[i][j];
                }
            }

            for (int z = 0; z < sel.length; z++ ) {

                int r = arr_r[sel[z]];
                int c = arr_c[sel[z]];
                int s = arr_s[sel[z]];

                int start_r = r - s - 1;
                int start_c = c - s - 1;
                int end_r = r + s - 1;
                int end_c = c + s - 1;

                L: while (true) {
                    int now_r = start_r;
                    int now_c = start_c;

                    int before = copyMap[start_r][start_c]; // 이전 값을 저장하는 변수
                    int now = 0;
                    int rot = 0;

                    while (true) {
                        if (start_r >= end_r || start_c >= end_c) break L;
                        now_r = now_r + dr[rot];
                        now_c = now_c + dc[rot];

                        // 허용 범위 내에 있으면
                        if (now_r >= start_r && now_r <= end_r && now_c >= start_c && now_c <= end_c) {
                            now = copyMap[now_r][now_c];
                            copyMap[now_r][now_c] = before;
                            before = now;

                            // 처음 위치로 되돌아오면
                            if (now_r == start_r && now_c == start_c) {
                                start_r += 1;
                                start_c += 1;
                                end_r -= 1;
                                end_c -= 1;

                                break;
                            }
                        } else {
                            now_r = now_r - dr[rot];
                            now_c = now_c - dc[rot];
                            rot += 1;
                        }
                    }
                }
            }

            for (int i = 0; i < copyMap.length; i++) {
                int row_answer = 0;
                for (int j = 0; j < copyMap[0].length; j++) {
                    row_answer += copyMap[i][j];
                }
                answer = Math.min(answer, row_answer);
            }
            return;
        }

        for (int i = 0; i < sel.length; i++) {
            if (v[i] == true) continue;
            v[i] = true;
            sel[count] = i;
            recursive(count + 1);
            sel[count] = 0;
            v[i] = false;
        }
    }

    static int[] dr = {0, 1, 0, -1};
    static int[] dc = {1, 0, -1, 0};

    static void print(int[][] map) {
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[0].length; j++) {
                System.out.print(map[i][j] + " ");
            }
            System.out.println("");
        }
    }
}

 

 

 

 

발생한 문제 & 해결 방안

식을 작성할 때 무념무상으로 복붙하면서 c를 제대로 작성하지 않아 에러가 발생하였다.

 

순서를 임으로 정하지 않고 순차적으로 해서 한 번 틀렸다.

 

 

 

 

 

 

 

해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.

혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!

python source : https://github.com/ssh5212/conding-test-practice

java source : https://github.com/ssh5212/coding-test-java

공유하기

facebook twitter kakaoTalk kakaostory naver band