[백준] 17406 배열 돌리기 4 - 브루트포스(BruteForce) + 순열(Permutation) + HashSet(해쉬) JAVA

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

17406번: 배열 돌리기 4

코드설명

DFS를 활용하여 조합(HashSet 활용) 을 구하고, 브루트포스 알고리즘을 실행합니다.

 

먼저 조합을 HashSet을 활용하여 저장하고 진행하는 코드입니다.

먼저 각 순서를 임의로 정할 수 있으므로 모든 순서를 탐색해야합니다.

아래의 코드를 통해 순열을 구합니다. {0 1}, {1, 0} 이런식으로 순서를 구합니다.

public static void permutaiton(int level, int idx) {
    if(level == K) {
        hashset.clear();
        for(int a : operationOrder) {
            hashset.add(a);
        }
        if(hashset.size() == K) {
            simulate();
        }
        return ;
    }
    for(int i=0; i<K; i++) {
        operationOrder[level] = i; 
        permutaiton(level + 1, i);
        operationOrder[level] = -99;
    }
}

각 순서에 맞게 회전을 시키면되는데,

회전을 시킬떄 순서는,

1. 상단 변 오른쪽으로 이동시키기.

2. 좌측 변 위으로 이동시키기

3. 하단 변 왼쪽으로 이동시키기.

4. 오른쪽 변 아래쪽으로 이동시키기

5. newMap[startR+1][startC] = map[startR][startC+size]

 

위의 로직을 정확히 구현하여 알맞게 회전시킵니다. 처음에 시계방향으로 회전시킨다는 말이 있어 저도 같이 시계방향으로 구현하려고하였지만, 해당 방안으로 구현할경우 꼭지점 부분이 계속해서 겹치게 되면서 꼭지점 부분을 직접 모두 갱신해줘야 하므로 

반시계방향으로 한다면 처리할 수 있습니다.

 

반면에, 

HashSet을 사용하지 않는 코드도 있습니다.  순열을 만들면서 바로 로직을 진행합니다.

아래의 로직에서 유의해야할점은 visited[i]는 해당 Command를 사용했느냐 안했느냐를 저장하는 것입니다.

처음에 실수했던점은, visited[level]로 처리하여 올바르게 방문처리가 작동하지 않았습니다.

만약 바로 만들면서 진행하는것이 아닌 selected[K]를 통해서 순열을 만들고 작업한다면, 이떄 selected[level]=i 이런 방식으로 순서를 저장합니다.

public static void simulate(int level) {
    	if(level == K) {
    		answer = Math.min(answer, calculate());
    		return ;
    	}
    	
    	//순서에 따라 결과가 바뀌므로 순열을 사용합니다.
    	int[][] storeMap = new int[N][M];
    	for(int i=0;i<N;i++) {
    		for(int j=0;j<M;j++) {
    			storeMap[i][j] = map[i][j];
    		}
    	}
    	
    	for(int i=0;i<K;i++) {
    		if(visited[i] == false) {
    			visited[i] = true;
    			rotate(i);
    			simulate(level + 1);
        		for(int k=0;k<N;k++) {
            		for(int h=0;h<M;h++) {
            			map[k][h] = storeMap[k][h];
            		}
            	}
    			visited[i] = false;
    		}
    		
    	}
    }

 

속도같은경우, 바로 만들어서 진행할경우 원래대로 되돌리는 작업이 오직 1번만 있으면 되니, 모든 조합을 만들을 경우가 더 빠릅니다.

반면에, 만들면서 바로 rotate하며 진행할경우 이전 map값을 다시 되돌려주는 작업이 필요하므로 시간이 조금 더 소요됩니다. 

 

코드 

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

public class Main {
	public static int N,M,K;
	public static int answer = Integer.MAX_VALUE;
	public static int[] r, c, s;
	public static int[][] map;
	public static int[][] newMap;
	public static int[] operationOrder;
	public static boolean[] visited;
	public static HashSet<Integer> hashset = new HashSet<>();
	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];
    	newMap = 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());
    		}
    	}

    	r = new int[K];
    	c = new int[K];
    	s = new int[K];
    	operationOrder = new int[K];
    	visited = new boolean[K];
    	for(int k=0;k<K;k++) {
    		st = new StringTokenizer(br.readLine());
    		r[k] = Integer.parseInt(st.nextToken());
    		c[k] = Integer.parseInt(st.nextToken());
    		s[k] = Integer.parseInt(st.nextToken());
    	}
    	for(int i=0;i<operationOrder.length;i++) {
    		operationOrder[i] = -99;
    	}
    	
    	permutaiton(0, 0);
    	System.out.println(answer);
    }
	public static void permutaiton(int level, int idx) {
		if(level == K) {
			hashset.clear();
			for(int a : operationOrder) {
				hashset.add(a);
			}
			if(hashset.size() == K) {
				simulate();
			}
			return ;
		}
		for(int i=0; i<K; i++) {
			operationOrder[level] = i; 
			permutaiton(level + 1, i);
			operationOrder[level] = -99;
		}
		
	}
	
	
	public static void simulate() {
		for(int i=1;i<=N;i++) {
			for(int j=1;j<=M;j++) {
				newMap[i][j] = map[i][j];
			}
		}
		for(int k=0;k<K;k++) {
			int order = operationOrder[k];
			rotate(r[order],c[order],s[order]);
		}
		
		for(int i=1;i<=N;i++) {
			int sum = 0;
			for(int j=1;j<=M;j++) {
				sum += newMap[i][j];
			}
			answer = Math.min(answer, sum);
		}
		
	}
	
	public static void rotate(int r, int c, int s) {
		
		for(int d=1; d<=s;d++) {
			int startR = r - d;
			int startC = c - d;
			int endR = r + d;
			int endC = c + d;
			
			int size = 2 * d;
			int secondTemp = newMap[startR][startC+size]; //오른쪽 상단 꼭지점
			
			//위쪽 변 오른쪽으로 이동시키기.
			for(int i=endC; i>startC; i--) {
				newMap[startR][i] = newMap[startR][i-1];
			}
			//좌측 변 위으로 이동시키기
			for(int i=startR; i<endR;i++) {
				newMap[i][startC] = newMap[i+1][startC];
				
			}
			//하단 변 왼쪽으로 이동시키기.
			for(int i=startC; i<endC; i++) {
				newMap[endR][i] = newMap[endR][i+1];
			}
			//오른쪽 변 아래쪽으로 이동시키기
			for(int i=endR; i>startR;i--) {
				newMap[i][endC] = newMap[i-1][endC];
			}
			newMap[startR+1][endC] = secondTemp;
		}
	}
}

 

 

회전시킬때 , sr, sc, er, ec 를 모두 미리 구하여 불필요 연산을 제거합니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	public static int N,M, K;
	public static int answer = Integer.MAX_VALUE;
	public static int[][] map;
	public static int[][] command;
	public static boolean[] visited;
	
    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];
    	command = new int[K][3];
    	visited = new boolean[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());
    		command[i][0] = Integer.parseInt(st.nextToken());
    		command[i][1] = Integer.parseInt(st.nextToken());
    		command[i][2] = Integer.parseInt(st.nextToken());
    	}
    	simulate(0);
    	System.out.println(answer);
    }
    
    public static void simulate(int level) {
    	if(level == K) {
//    		System.out.println("HELLO");
//    		for(int i=0;i<N;i++) {
//        		for(int j=0;j<M;j++) {
//        			System.out.print(" "+map[i][j]);
//        		}
//        		System.out.println();
//        	}
//    		System.out.println();
    		answer = Math.min(answer, calculate());
    		return ;
    	}
    	
    	//순서에 따라 결과가 바뀌므로 순열을 사용합니다.
    	int[][] storeMap = new int[N][M];
    	for(int i=0;i<N;i++) {
    		for(int j=0;j<M;j++) {
    			storeMap[i][j] = map[i][j];
    		}
    	}
    	
    	for(int i=0;i<K;i++) {
    		if(visited[i] == false) {
    			visited[i] = true;
    			rotate(i);
    			simulate(level + 1);
        		for(int k=0;k<N;k++) {
            		for(int h=0;h<M;h++) {
            			map[k][h] = storeMap[k][h];
            		}
            	}
    			visited[i] = false;
    		}
    		
    	}
    }
    
    public static int calculate() {
    	int sum = 0;
    	int minSum = Integer.MAX_VALUE;
    	for(int row=0;row<N;row++) {
    		sum = 0;
    		for(int col=0;col<M;col++) {
    			sum += map[row][col];
    		}
    		minSum = Math.min(minSum, sum);
    	}
    	return minSum;
    }
    
    public static void rotate(int commandIdx) {
    	int r = command[commandIdx][0] - 1;
    	int c = command[commandIdx][1] - 1;
    	int s = command[commandIdx][2];
    	
    	//s번만큼, (r,c)에서 안쪽에서 바깥으로 이동하면서 회전을 진행할 것 입니다.
    	for(int t=1; t<=s;t++) {
    		int sr = r - t;
    		int sc = c - t;
    		
    		int er = r + t;
    		int ec = c + t;
    		
//    		System.out.println(sr+" "+sc);
    		//총 4번 처리할것입니다.
    		//첫번쨰 값은 Store해둡니다.
    		int firstValue = map[sr][sc];
    		
    		for(int row=sr; row<er; row++) {
    			map[row][sc] = map[row + 1][sc];
    		}
    		
    		for(int col = sc; col < ec; col ++) {
    			map[er][col] = map[er][col + 1];
    		}
    		
    		for(int row=er; row > sr; row--) {
    			map[row][ec] = map[row - 1][ec];
    		}
    		
    		for(int col = ec; col > sc; col--) {
    			map[sr][col] = map[sr][col - 1];
    		}
    		
    		//저장해두었던 첫번째 값 적절한 자리에 이동시킵니다.
    		map[sr][sc + 1] = firstValue;
    	}
    	
    	
    	
    }
    
}

 

 

회전시 위의 코드처럼 sr, sc, er, ec를 활용하지 않아 회전속도가 느린 코드입니다.

위에 처럼 변수선언을 줄여서 코드해야 빠릅니다.

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

public class Main {
	public static int N, M, K;
	public static int answer = 50 * 100 + 1;
	public static int[][] map;
	public static Rotate[] rotate;
	public static boolean[] visited;
	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());
		rotate = new Rotate[K];
		visited = new boolean[K];
		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());
			}
		}
		
		for(int i=0;i<K;i++) {
			st = new StringTokenizer(br.readLine());
			int r = Integer.parseInt(st.nextToken());
			int c = Integer.parseInt(st.nextToken());
			int s = Integer.parseInt(st.nextToken());
			rotate[i] = new Rotate(r - 1, c - 1, s);
		}
		simulate(0);
		System.out.println(answer);
	}
	
	public static void simulate(int level) {
		if(level == K) {
			answer = Math.min(answer, calculateMin());
			return ;
		}
		
		int[][] storeMap = new int[N][M];
		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++) {
				storeMap[i][j] = map[i][j];
			}
		}
		
		for(int i=0;i<K;i++) {
			if(visited[i] == false) {
				visited[i] = true;
				rotateBy(rotate[i]);
				//회전 작업 시작.
				simulate(level + 1);
				for(int j=0;j<N;j++) {
					for(int k=0;k<M;k++) {
						map[j][k] = storeMap[j][k];
					}
				}
				visited[i] = false;
			}
		}
		
	}
	
	public static void rotateBy(Rotate rotate) {
		int r= rotate.r;
		int c = rotate.c;
		int s = rotate.s;
		
		//s번 회전한다.
		for(int length=1; length <= s; length ++) {
			int firstNum = map[r-length][c-length];
			
			int startRow = r - length;
			int startCol = c - length;
			// 왼쪽변, 아래에서 위로 이동하도록 처리. 맨 처음 칸은 저장해두어야한다.
			// col은 그대로 있고, row만 변동됩니다.
			for(int i=0;i<length * 2; i++) {
				map[startRow][startCol] = map[startRow + 1][startCol];
				startRow += 1;
			}
			
			// 아랫변, 오른쪽에서 왼쪽으로.
			// row는 가만하 있고, col만 변동됩니다.
			startRow = r + length;
			startCol = c - length;
			for(int i=0;i<length * 2; i++) {
				map[startRow][startCol] = map[startRow][startCol + 1];
				startCol += 1;
			}
			
			
			// 오른쪽 변
			// row는 감소하고, col은 그대로.
			startRow = r + length;
			startCol = c + length;
			for(int i=0;i<length * 2; i++) {
				map[startRow][startCol] = map[startRow - 1][startCol];
				startRow -= 1;
			}
			
			//맨 위쪽 변
			//row는 그대로, col은 감소합니다.
			startRow = r - length;
			startCol = c + length;
			for(int i=0;i<length * 2; i++) {
				map[startRow][startCol] = map[startRow][startCol - 1];
				startCol -= 1;
			}
			
			map[r - length][c - length + 1] = firstNum; 
		}
	}
	
	public static int calculateMin() {
		int minSum = M * 100 + 1;
		for(int row=0;row<N;row++) {
			int sum = 0;
			for(int col = 0; col<M;col++) {
				sum += map[row][col];
			}
			minSum = Math.min(minSum, sum);
		}
		
		return minSum;
	}
	
}

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