BOJ 17406번: 배열 돌리기 4

문제

문제 바로가기> BOJ 17406번: 배열 돌리기 4

17406번: 배열 돌리기 4

 

풀이

우선 K가 최대 6으로 작기 때문에, 모든 경우의 수를 탐색하는 방법으로 문제를 풀 수 있다. 

 

문제를 풀 때 필요한 점은 다음 2가지 였던 것 같다.

1. 순열을 구현할 수 있는가?

2. 배열을 원하는 대로 조작할 수 있는가? 

 

1(순열 구현) 을 만족하기 위해, cnt 변수와 visited 배열을 활용하여 재귀적으로 호출을 해주었다.

2(배열 조작)은 규칙을 찾는 게 중요하다. ur>=dr 이 되는 순간, 더 이상 돌리지 않아도 된 다는 것은, 조금만 생각해봐도 알 수 있다. 이 점을 이용해서 ur, uc, dr, dc 카운트를 조작해가면서 시작점과 종료지점의 위치를 파악해주었다.

 

C++

#include<iostream>
#include<vector>
#define MAX 51
#define MAX_K 7
#define INF 1000000001
using namespace std;

struct OPER{int r, c, s;};
vector<OPER> v;

int N, M, K;
int ans = INF;
int arr[MAX][MAX];
bool visited[MAX_K];

void input(){
    cin >> N >> M >> K;
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++) cin >> arr[i][j];
    }

    int r, c, s;
    for(int i=0; i<K; i++){
        cin >> r >> c >> s;
        v.push_back({r-1, c-1, s}); // start with 0
    }
}

void rotate_arr(int r, int c, int s){

    int ur = r-s, uc = c-s; // 좌측 상단 좌표
    int dr = r+s, dc = c+s; // 우측 하단 좌표

    while(1){
        if(ur >= dr) break; // 종료 조건
        int tmp = arr[ur][uc];
        for(int i=ur; i<dr; i++) arr[i][uc] = arr[i+1][uc]; // 좌
        for(int j=uc; j<dc; j++) arr[dr][j] = arr[dr][j+1]; // 하
        for(int i=dr; i>ur; i--) arr[i][dc] = arr[i-1][dc]; // 우
        for(int j=dc; j>uc; j--) arr[ur][j] = arr[ur][j-1]; // 상
        arr[ur][uc+1] = tmp;
        ur++; uc++;
        dr--; dc--;
    }
}

int get_min_val(){
    int res = INF;
    for(int i=0; i<N; i++){
        int sum = 0;
        for(int j=0; j<M; j++) sum+=arr[i][j];
        res = min(res, sum);
    }
    return res;
}

void solution(int cnt){

    if(cnt == K){
        ans = min(ans, get_min_val());
        return;
    }

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

        if(visited[k]) continue; // 이미 사용한 경우
        visited[k] = true; // 사용

        // save state
        int copy_arr[MAX][MAX];
        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++) copy_arr[i][j] = arr[i][j];
        }
        
        rotate_arr(v[k].r, v[k].c, v[k].s); // 회전 연산
        solution(cnt+1); // 순열 구현
        
        visited[k] = false; // 다른 순열에서 사용하기 위해

        // recovery
        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++) arr[i][j] = copy_arr[i][j];
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    input();
    solution(0);
    cout << ans;
}

 

Java

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

public class Main {
	
	static int N, M, K;
	static int[] seq; // 배열을 돌릴 순서를 저장  (연산을 수행한 순서에 따라 최종 배열이 다름)
	static int[][] arr; // 배열 A
	static int[][] init_arr; // 초기 배열 A
	static int[][] cycle; // K개 cycle의 정보 저장
	static boolean[] visited; // 순열을 만들기 위해 사용
	static int ans = Integer.MAX_VALUE;

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("res/input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken()); // 배열 A의 크기 N x M
		M = Integer.parseInt(st.nextToken()); // 배열 A의 크기 N x M
		K = Integer.parseInt(st.nextToken()); // 회전 연산의 개수
		
		arr = new int[N][M];
		init_arr = new int[N][M];
		cycle = new int[K][3];
		
		seq = new int[K];
		visited = new boolean[K];
		
		// 배열 입력
		for(int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0; j<M; j++) {
				init_arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		// 회전 연산 정보 입력
		for(int k=0; k<K; k++) {
			st = new StringTokenizer(br.readLine());
			cycle[k][0] = Integer.parseInt(st.nextToken())-1; // index 0 부터 시작 
			cycle[k][1] = Integer.parseInt(st.nextToken())-1;
			cycle[k][2] = Integer.parseInt(st.nextToken());
		}
		
		solution(0); // 순열 
		System.out.println(ans); // 배열 A의 값의 최솟값
		br.close();
	}
	
	public static int get_min_val() {
		int res = Integer.MAX_VALUE;
		for(int i=0; i<N; i++) {
			int sum = 0;
			for(int j=0; j<M; j++) sum+=arr[i][j];
			res = Math.min(res, sum); // 각 행에 있는 모든 수의 합 중 최솟값
		}
		return res;
	}
	
	public static void roate_arr(int r, int c, int s) {
		int ur = r-s, uc = c-s; // 좌측 상단 좌표
	    int dr = r+s, dc = c+s; // 우측 하단 좌표

	    while(true){ // 정사각형 시계 방향 회전 
	        if(ur >= dr) break; // 종료 조건
	        int tmp = arr[ur][uc];
	        for(int i=ur; i<dr; i++) arr[i][uc] = arr[i+1][uc]; // 좌
	        for(int j=uc; j<dc; j++) arr[dr][j] = arr[dr][j+1]; // 하
	        for(int i=dr; i>ur; i--) arr[i][dc] = arr[i-1][dc]; // 우
	        for(int j=dc; j>uc; j--) arr[ur][j] = arr[ur][j-1]; // 상
	        arr[ur][uc+1] = tmp;
	        ur++; uc++;
	        dr--; dc--;
	    }
	}
	
	public static void solution(int cnt) {
		if(cnt == K) { // 배열을 돌릴 순서를 다 정한 경우
			
			// copy
	        for(int i=0; i<N; i++){
	            for(int j=0; j<M; j++) arr[i][j] = init_arr[i][j];
	        }
			
			// 배열 회전 
			for(int i=0; i<K; i++) {
				int s = seq[i];
				roate_arr(cycle[s][0], cycle[s][1], cycle[s][2]);
			}
			
			// min 값 update
			ans = Math.min(ans,  get_min_val());
			
			return ;
		}
		
		for(int k=0; k<K; k++) {
			if(visited[k]) continue; // 이미 사용한 경우
			visited[k] = true; // 사용
			seq[cnt] = k;
			solution(cnt+1); // 순열 구현
			visited[k] = false; // 다른 순열에서 사용하기 위해
		}
	}
}