[백준] code.plus(브루트 포스 Part 1,JAVA)17406번, 배열 돌리기 4

문제 링크

17406번: 배열 돌리기 4

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심은

 

1. 배열의 값은 각 행의 최소합을 뜻합니다.

2. r, c, s에 따른 범위에 값들을 시계방향으로 회전합니다.

3. 회전 연산의 순서는 임의적으로 바꿀 수 있습니다.

4. 모든 회전 연산 이후 배열의 최소값을 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력되는 정보들을 저장합니다.

 

2. 회전 연산을 진행하는 모든 경우를 탐색합니다.

 

3. 모든 경우를 탐색한 뒤에 배열의 최소값을 결과로 출력합니다.

 

회전.

 

※ 저는 문제를 대충 읽고 90도 회전으로 파악하여 점화식까지 작성하고 진행하였습니다.

예제입력을 넣어보니 틀려서 문제를 다시 읽어보니 한 칸씩 이동하는 것을 깨닫고 후회하였습니다 ㅠ^ㅠ

문제 꼼꼼히 읽어보시면 좋겠습니다.

 

문제에서 설명하듯이 회전은 한 칸씩 시계방향으로 이동하는 것입니다.

→	→	↓
↑		↓
↑	←	←

회전을 진행할 때 기준이 되는 값을 임의의 변수에 저장한 뒤 한 칸씩 땡기는 것을 진행합니다.

임의의 변수에 저장된 값도 회전으로 값을 저장하는 형식으로 회전에 대한 알고리즘을 작성하였습니다.

 

 

예제입력 1.

※그림으로는 문제에서 설명하기 때문에 알고리즘이 어떻게 구현되는지 보여드리겠습니다.

 

1. 입력되는 정보들을 저장합니다.

 

N = 5, M = 6, K = 2

 

회전 연산

(3, 4, 2)

(4, 2, 1)

 

2. 회전 연산을 진행하는 모든 경우를 탐색합니다.

 

(3, 4, 2)를 진행하다고 할 때

 

외곽의 회전 연산이 진행되는 범위를 구합니다.

s : (3 - 2, 4 - 2) : (1, 2)

e : (3 + 2, 4 + 2) : (5, 6)

※저는 s의 좌표를 기준으로 회전으로 시작했습니다.

 

	s(1, 2)→	→	→	→	↓
	↑				↓
	↑				↓
	↑				↓
	↑	←	←	←	←e(5, 6)

 

다음 외곽의 회전 연산이 진행되는 범위를 구합니다.

s : (3 - 1, 4 - 1) : (2, 3)

e : (3 +1, 4 + 1) : (4, 5)

 

	→	→	→	→	↓
	↑	s(2, 3)→	→	↓	↓
	↑	↑		↓	↓
	↑	↑	←	←s(4, 5)	↓
	↑	←	←	←	←

위와 같이 모든 회전 연산에 대하여 회전을 진행합니다.

 

3. 모든 경우를 탐색한 뒤에 배열의 최소값을 결과로 출력합니다.

(3, 4, 2) -> (4, 2, 1)

1	8	2	3	2	5
3	2	3	7	2	6
3	8	4	1	1	3
9	3	5	1	4	5
2	1	1	4	3	1

배열의 값 : (2+ 1 + 1 + 4 + 3 + 1) = 12

 

(4, 2, 1) -> (3, 4, 2)

1	8	2	3	2	5
3	8	2	7	2	6
3	4	3	1	1	3
9	2	1	1	4	5
3	5	1	4	3	1

배열의 값 : (3 + 4 + 3 + 1 + 1 + 3) = 15

 

배열의 최소값 12을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 이용하여 입력값을 띄어쓰기 기준으로 나누었습니다.
• search함수를 회전 연산을 임의의 순서로 진행하는 모든 경우 탐색을 진행합니다.
• 탐색 종료 후 배열의 최소값을 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• search함수는 재귀를 통해서 회전 연산의 임의의 순서로 모든 경우를 탐색합니다.
• rotate함수는 회전 연산에 맞게 회전을 진행합니다.
• cal함수는 배열의 값을 계산하고 최소값인지 확인합니다.
• rollBack함수는 기존 배열로 되돌아오도록 진행합니다.

 

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

public class Main {
    //회전 연산 정보 클래스
    static class info{
        int x, y, s;
        public info(int x, int y, int s) {
            this.x = x;
            this.y = y;
            this.s = s;
        }
    }
    static int N,M,K, answer = Integer.MAX_VALUE;
    static int[][] arr;	//입력되는 배열 저장 배열
    static boolean[] visited;		//회전연산 사용 확인 배열
    static ArrayList<info> list = new ArrayList<>();	//회전 연산 저장 리스트
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st= new StringTokenizer(br.readLine()," ");
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        arr = new int[N][M];
        visited = new boolean[K];
        //입력 배열 저장
        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine()," ");
            for(int j=0;j<M;j++)
                arr[i][j] = Integer.parseInt(st.nextToken());
        }
        //입력되는 회전 연산 저장
        for(int i=0;i<K;i++){
            st = new StringTokenizer(br.readLine()," ");
            int y = Integer.parseInt(st.nextToken())-1;
            int x = Integer.parseInt(st.nextToken())-1;
            int s = Integer.parseInt(st.nextToken());
            list.add(new info(x-s, y-s, s*2));
        }
        search(0);	//회전 연산 임의의 순서에 대한 모든 경우 탐색
        bw.write(answer + "");		//배열의 최소값 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //회전 연산을 임의의 순서로 진행하는 함수
    static void search(int depth){
        if(depth==K){
            cal();
            return;
        }
        //기존 배열 복사.
        int[][] temp = new int[N][M];
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++){
                temp[i][j] = arr[i][j];
            }
        }
        //탐색
        for(int i=0;i<K;i++){
            if(visited[i])		//사용한 회전 연산인 경우
                continue;
            //회전연산 사용
            visited[i] = true;
            rotate(list.get(i));
            search(depth + 1);
            //회전연산 복구
            visited[i] = false;
            rollBack(temp);		//기존 배열로 복구 함수 실행
        }
    }
    //배열의 값 구하는 함수
    static void cal(){
        int result = Integer.MAX_VALUE;
        for(int i=0;i<N;i++){
            int temp = 0;
            for(int j=0;j<M;j++)
                temp += arr[i][j];
            result = Math.min(result, temp);
        }
        answer = Math.min(answer, result);		//최소값과 비교하기
    }
    //회전 연산에 맞게 배열 회전하는 함수
    static void rotate(info value){
        for(int i=0;i<value.s/2;i++){
            int sx = value.x + i;		//왼쪽 상단 x
            int sy = value.y + i;		//왼쪽 상단 y
            int ex = value.x + value.s - i;		//오른쪽 하단 x
            int ey = value.y + value.s - i;		//오른쪽 하단 y
            int temp = arr[sy][sx];	//기준 값(sy, sx) 저장
            //↑
            for(int j=sy;j<ey;j++)
                arr[j][sx] = arr[j+1][sx];
            //←
            for(int j=sx;j<ex;j++)
                arr[ey][j] = arr[ey][j+1];
            //↓
            for(int j=ey;j>sy;j--)
                arr[j][ex] = arr[j-1][ex];
            //→
            for(int j=ex;j>sx+1;j--)
                arr[sy][j] = arr[sy][j-1];
            arr[sy][sx+1] = temp;	//기준 값도 회전

        }
    }
    //기존 배열로 되돌아오는 함수
    static void rollBack(int[][] temp){
        for(int i=0;i<N;i++){
            for(int j=0;j<M;j++)
                arr[i][j] = temp[i][j];
        }
    }
}