13460 구슬 탈출 2 - 삼성 sw 역량 기출

구슽탈출

N * M의 보드에 빨간구슬, 파란구슬, 구멍이 하나 씩 있을 때 회전을 통한 중력으로 빨간 구슬을 빼야한다.
파란 구슬이 빠지거나, 동시에 빠져도 실패이다.
이 때, 최소 몇번의 회전을 통해 빨간 구슬을 꺼낼 수 있을까?

---

1. 맵을 돌리지 않고 방향마다 중력이 적용되도록 함

   gravity 함수에서 구멍을 통과한 구슬의 색을 저장하는 배열 result를 리턴해준다

   result[0] : 빨간색, result[1] : 파란색

   ​

2. 모든 경우의 수를 구하는 powerset구현

   result[1]이 이미 채워진경우, 회전이 10번이 넘은경우, 현재 저장된 답보다 오래걸리는 경우를 가지치기 해준다

   백트래킹을 하면서 방향마다 돌려본다

   result[0]이 채워진 경우 카운트 값을 리턴

​

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

public class Main구슬탈출2 {
	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());

		char[][] map = new char[N][M];
		int[] R = new int[2];
		int[] B = new int[2];
		int[] O = new int[2];


		for(int i = 0; i < N; i++) {
			String str = br.readLine();
			for(int j = 0; j < M; j++) {
				map[i][j] = str.charAt(j);
				if(map[i][j] == 'B') {
					B[0] = i;
					B[1] = j;
				}else if(map[i][j] == 'R') {
					R[0] = i;
					R[1] = j;
				}else if(map[i][j] == 'O') {
					O[0] = i;
					O[1] = j;
				}
			}
		}

		ans = 11;
		power(map, new int[2], 0);
		if(ans == 11) {
			ans = -1;
		}

		System.out.println(ans);


	}
	static int N;
	static int M;
	static int ans;

	static void power(char[][] map, int[] result, int cnt) {

		if(result[1] == 1) {
			return;
		}

		if(cnt > ans) {
			return;
		}

		if(cnt > 10) {
			return;
		}


		if(result[0] == 1) {
			ans = Math.min(cnt, ans);
			return;
		}


		char[][] copy = new char[N][M];

		for(int k = 0;k < 4; k++) {
			for(int i = 0; i < N; i++) {
				for(int j = 0; j < M; j++) {
					copy[i][j] = map[i][j];
				}
			}
			power(copy, gravity(copy, k), cnt+1);
		}

	}

	static int[] gravity(char[][] map, int d) {
		int[] result = new int[2];
		switch(d) {
		case 0:
			for(int j = 0; j < M; j++) {
				for(int i = 0; i < N-1; i++) {
					if(map[i][j]=='.') {
						for(int k = i+1; k < N; k++ ) {
							if(map[k][j]=='R' || map[k][j]=='B') {
								char temp = map[i][j];
								map[i][j] = map[k][j];
								map[k][j] = temp;
								break;
							}
							if(map[k][j]!='.')break;
						}
					}
					if(map[i][j]=='O') {
						for(int k = i+1; k < N; k++ ) {
							if(map[k][j]=='#')break;
							if(map[k][j]=='R') {
								result[0]++;
								map[k][j] = '.';
							}
							else if(map[k][j]=='B') {
								result[1]++;
								map[k][j] = '.';
							}
						}
					}
				}
			}
			break;
		case 1:
			for(int j = 0; j < M; j++) {
				for(int i = N-1; i > 0; i--) {
					if(map[i][j]=='.') {
						for(int k = i-1; k >= 0; k--) {
							if(map[k][j]=='R' || map[k][j]=='B') {
								char temp = map[i][j];
								map[i][j] = map[k][j];
								map[k][j] = temp;
								break;
							}
							if(map[k][j]!='.')break;
						}
					}
					if(map[i][j]=='O') {
						for(int k = i-1; k >= 0; k--) {
							if(map[k][j]=='#')break;
							if(map[k][j]=='R') {
								result[0]++;
								map[k][j] = '.';
							}else if(map[k][j]=='B'){
								result[1]++;
								map[k][j] = '.';
							}
						}
					}
				}
			}
			break;
		case 2:
			for(int i = 0; i < N; i++) {
				for(int j = 0 ; j < M-1; j++) {
					if(map[i][j]=='.') {
						for(int k = j+1; k < M; k++) {
							if(map[i][k]=='R' || map[i][k]=='B') {
								char temp = map[i][j];
								map[i][j] = map[i][k];
								map[i][k] = temp;
								break;
							}
							if(map[i][k]!='.')break;
						}
					}
					if(map[i][j]=='O') {
						for(int k = j+1; k < M; k++) {
							if(map[i][k]=='#')break;
							if(map[i][k]=='R') {
								result[0]++;
								map[i][k]='.';
							}else if(map[i][k]=='B') {
								result[1]++;
								map[i][k]='.';
							}
						}
					}
				}
			}
			break;
		case 3:
			for(int i = 0; i < N; i++) {
				for(int j = M-1; j > 0; j--) {
					if(map[i][j]=='.') {
						for(int k = j-1; k >= 0; k--) {
							if(map[i][k]=='R' || map[i][k]=='B') {
								char temp = map[i][j];
								map[i][j] = map[i][k];
								map[i][k] = temp;
								break;
							}
							if(map[i][k]!='.')break;
						}
					}
					if(map[i][j]=='O') {
						for(int k = j-1; k >= 0; k--) {
							if(map[i][k]=='#')break;
							if(map[i][k]=='R') {
								result[0]++;
								map[i][k]='.';
							}else if(map[i][k]=='B') {
								result[1]++;
								map[i][k]='.';
							}
						}
					}
				}
			}
		}

		return result;
	}
}