[백준] 17406 배열 돌리기4

1. 문제

www.acmicpc.net/problem/17406

17406번: 배열 돌리기 4

2. 접근방법

순열을 이용해 가능한 경우의 수를 모두 뽑아놓고

 

배열을 잘 돌려보면 되는 구현 문제이다.

 

순열을 모른다면 재귀의 아주 기초이니 배우고 다시 풀어보길 권장한다.

 

배열을 돌리는 것은 어떻게 할까 보니

 

요 그림에서 3,4를 기준으로

거리가 1인 얘들끼리만 오른쪽으로 돌고

거리가 2인 얘들끼리만 오른쪽으로 돌고 하는 것을 볼 수 있다.

 

여기서 오른쪽으로 돈다에서 착안해서

거리가 1인 경우에 2,3에서 출발한다 하면

2,5를 만나면 방향을 꺽고 4,5를 만나면 방향을 꺽고 4,3을 만나면 꺽고 2,3을 만나면 끝내면 된다.

 

거리가 2인 경우엔

1,2 -> 1,6 ->5,6 -> 5,2 -> 1,2끝 으로 하면 될것이다.

 

그렇다면 방향을 꺽을 저 위치들을 어떻게 알 수 있을까?

 

그림이 조금 그렇긴한데

중심을 기준으로 방향이 바뀌는 지점 즉 회전하는 사각형의 꼭지점들은

중심과 꼭지점의 좌표를 뺀 절대값이 x,y값 모두 회전하는 거리와 같은 점들이다.

 

이제 회전을 시키며 각 자리 값들을 옮겨주면 회전이 완성 되겠다.

 

행의 합 구하는건 그냥 구하면 되니 패쓰~

3. 자바 코드

package Gold;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class P17406배열돌리기4 {
	static class turn {
		int r;
		int c;
		int s;

		public turn(int r, int c, int s) {
			this.r = r;
			this.c = c;
			this.s = s;
		}
	}

	static turn turns[];
	static int N,M,K,map[][];
	public static void main(String[] args) throws Exception {
		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];
		sel = new turn[K];
		visit = new boolean[K];
		turns = new turn[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());
			}
		}
		for (int i = 0; i < K; i++) {
			st = new StringTokenizer(br.readLine());
			int r = Integer.parseInt(st.nextToken())-1;
			int c = Integer.parseInt(st.nextToken())-1;
			int s = Integer.parseInt(st.nextToken());
			turns[i] = new turn(r, c, s);
		}
		perm(0);
		System.out.println(min);
	}
	static turn sel[];
	static boolean visit[];
	static int min = Integer.MAX_VALUE;
	static void perm(int selidx) {
		if(selidx == K) {
			int [][] copymap = new int[N][M];
			for (int i = 0; i < N; i++)
				copymap[i] = map[i].clone();
			for(int i = 0 ; i < K ; i++)
				turnning(copymap,sel[i]);
			min = Math.min(min, findmin(copymap));
			return;
		}
		for(int i = 0 ; i < K ; i++) {
			if(visit[i])
				continue;
			visit[i] = true;
			sel[selidx] = turns[i];
			perm(selidx+1);
			visit[i] = false;
		}
		
	}
	static int dr[] = { 0, 1, 0, -1 };
	static int dc[] = { 1, 0, -1, 0 };
	static void turnning(int map[][], turn t) {
		for (int i = 1; i <= t.s; i++) {
			int r = t.r - i;
			int c = t.c - i;
			int d = 0;
			int temp = map[r][c];
			while (true) {
				r = r + dr[d];
				c = c + dc[d];
				temp = map[r][c] ^ temp ^(map[r][c] = temp );
				if(Math.abs(t.r-r) == i && Math.abs(t.c-c) == i) {
					if(++d >= 4)
						break;
				}
			}
		}
	}
	static int findmin(int map[][]) {
		int min = Integer.MAX_VALUE;
		for(int i = 0 ; i < N ; i++) {
			int sum = 0;
			for(int j = 0 ; j < M ; j++)
				sum += map[i][j];
			min = Math.min(sum, min);
		}
		
		return min;
	}
}

4. 마치며

오랜만에 알고리즘 풀이를 했더니 조금 어려웠던 느낌

감을 살려놓으려면 알고리즘은 정말 꾸준히 해야겠다.