[ 백준 / 13460 ] 구슬 탈출 2 ( 자바 )

www.acmicpc.net/problem/13460

13460번: 구슬 탈출 2

 

 

정답률 25.549%의 쉽지 않는 구현 문제였다. 다른 풀이는 생각보다 길이가 짧지만 나는 굉장히 긴 코드가 나왔다. 아무래도 효율적인 방법은 아닌 것 같다. 나는 모든 케이스를 검사하여 빨간구슬과 파란구슬을 옮겼으며 DFS, 백트래킹을 사용하였다.

 

나름 각 순서에 대해서 메소드를 구분하여서 만들었다.

 

상->하, 하->상, 좌->우, 우->좌로 이동을 하지 못하도록 변수를 만들어서 중복을 제거하였다. 그렇지 않다면 무한루프에 빠질 것이다.

 

한번 메소드에 들어가면 3번의 움직임이 있도록 하였다. 배열을 움직이기 때문에 매 순간마다 처음 모양의 배열로 백트래킹을 해야했다. 이 떄, 전체 배열을 백트래킹하지 않고 빨간구슬과 파란구슬이 움직이는 부분 총 2줄만 백트래킹을 하도록 하여서 별 차이는 없겠지만 좀 더 시간을 아끼기 위해 노력했다. DFS에서는.. 특히 배열에 관한 문제에서는 백 트래킹이 생명과도 같다. 새로운 변화를 주고 싶다면 그것에 대한 백트래킹도 바로 고려하고 작성해야만 실수를 줄일 수 있을 것이다.

 

파란 구슬이나 빨간 구슬 하나만 들어간 경우, 둘 다 들어간 경우, 둘 다 들어가지 않은 경우를 모두 고려하여 구분하였다. 이럴 때 주의할 것은 제대로 케이스마다 처리를 하지 않으면 문제가 꼬이게 된다. 따라서 어떻게 백트래킹하고 진행해야하는지 섬세하게 주석을 달고 시작하였다.

 

이 문제를 끝까지 풀고 한번에 맞추는 것은 성공했지만, 과연 시험에서 이 문제가 나왔을 때 내 방법으로 빠르게 풀 수 있는지 의문이 들었다. 엄청난 시간이 들 것이고 몇 개를 실수하면 무용지물이 되기 때문이다. DFS와 백트래킹에 대해서 더 실력이 쌓인다면 논리적인 로직을 금방 짤 수 있을 것이고 좀 더 빠른 코드작성을 할 것으로 기대한다.

 

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

public class Main {

	static int answer = Integer.MAX_VALUE;
	static int N;
	static int M;
	static char[][] array;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] line = br.readLine().split(" ");
		N = Integer.parseInt(line[0]);
		M = Integer.parseInt(line[1]);

		array = new char[N][M];
		for (int i = 0; i < N; i++) {
			array[i] = br.readLine().toCharArray();
		}
		
		recursive(1,'O');
		
		if (answer == Integer.MAX_VALUE) {
			System.out.println(-1);
		} else
			System.out.println(answer);
	}
	
	public static int[] find(char c) {
		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++) {
				if(array[i][j]==c) {
					return new int[] {i,j};
				}
			}
		}
		return null;
	}
	
	public static void move(char c, int dir, int x, int y) {
		if(dir=='L') {
			for(int j=y-1;j>=0;j--) {
				if(array[x][j]=='.') { //이동이 가능하다면
					array[x][j]=c;
					array[x][j+1]='.';
				} else if(array[x][j]=='O') { //빠지는 경우
					array[x][j+1]='.';
					return;
				} else { //장애물이 있어서 더이상 진행못할 경우
					return;
				}
			}
		}
		
		if(dir=='R') {
			for(int j=y+1;j<M;j++) {
				if(array[x][j]=='.') { //이동이 가능하다면
					array[x][j]=c;
					array[x][j-1]='.';
				} else if(array[x][j]=='O') { //빠지는 경우
					array[x][j-1]='.';
					return;
				} else { //장애물이 있어서 더이상 진행못할 경우
					return;
				}
			}
		}
		
		if(dir=='U') {
			for(int i=x-1;i>=0;i--) {
				if(array[i][y]=='.') { //이동이 가능하다면
					array[i][y]=c;
					array[i+1][y]='.';
				} else if(array[i][y]=='O') { //빠지는 경우
					array[i+1][y]='.';
					return;
				} else { //장애물이 있어서 더이상 진행못할 경우
					return;
				}
			}
		}
		
		if(dir=='D') {
			for(int i=x+1;i<N;i++) {
				if(array[i][y]=='.') { //이동이 가능하다면
					array[i][y]=c;
					array[i-1][y]='.';
				} else if(array[i][y]=='O') { //빠지는 경우
					array[i-1][y]='.';
					return;
				} else { //장애물이 있어서 더이상 진행못할 경우
					return;
				}
			}
		}
	}
	
	public static int check() {
		boolean isRFinished = true;
		boolean isBFinished = true;
		
		for(int i=0;i<N;i++) {
			for(int j=0;j<M;j++) {
				if(array[i][j]=='R') {
					isRFinished=false;
				}
				
				if(array[i][j]=='B') {
					isBFinished =false;
				}
			}
		}
		
		if(isRFinished==true && isBFinished==false) {
			return 1;
		} else if(isRFinished==false && isBFinished==false) {
			return 3;
		} else
			return 2;
	}
	
	public static void backtracking(char dir, int index, char[] copyed){
		if(dir=='N') { //가로
			for(int j=0;j<M;j++) {
				array[index][j] = copyed[j];
			}
		} else if(dir=='M') { //세로
			for(int i=0;i<N;i++) {
				array[i][index] = copyed[i];
			}
		}
	}
	
	public static void recursive(int cnt, char dir) {
		if(cnt>10 || cnt>answer) return;
		
		int[] locR = find('R');
		int[] locB = find('B');
		
		if(dir!='L') { //R로 이동
			//backtracking을 위한 초기화
			
			int NR = locR[0];
			char[] arrayR = new char[M];
			
			int NB = locB[0]; 
			char[] arrayB = new char[M];
			
			for(int j=0;j<M;j++) {
				arrayR[j] = array[NR][j];
				arrayB[j] = array[NB][j];
			}
			
			//move
			if(locR[1]<=locB[1]) { //무조건 B먼저 시작한다.
				move('B' , 'R', locB[0], locB[1]);
				move('R' , 'R', locR[0], locR[1]);
			} else { //무조건 R먼저 시작한다.
				move('R' , 'R', locR[0], locR[1]);
				move('B' , 'R', locB[0], locB[1]);
			}
			
			int val = check();
			if(val==1) { //성공 = 종료
				if(cnt<answer) answer = cnt;
				backtracking('N',NR,arrayR);
				backtracking('N',NB,arrayB);
				//backtracking 복귀
				return;
			} else if(val==2) { // 비정상종료
				backtracking('N',NR,arrayR);
				backtracking('N',NB,arrayB);
				//backtracking 복귀
			} else { //그대로 진행
				recursive(cnt+1,'R');
				backtracking('N',NR,arrayR);
				backtracking('N',NB,arrayB);
				//backtracking 복귀
			}
		}
		
		if(dir!='R') { //L로 이동
			int NR = locR[0];
			char[] arrayR = new char[M];
			
			int NB = locB[0]; 
			char[] arrayB = new char[M];
			
			for(int j=0;j<M;j++) {
				arrayR[j] = array[NR][j];
				arrayB[j] = array[NB][j];
			}
			
			//move
			if(locR[1]<=locB[1]) { //무조건 R먼저 시작한다.
				move('R' , 'L', locR[0], locR[1]);
				move('B' , 'L', locB[0], locB[1]);
			} else { //무조건 B먼저 시작한다.
				move('B' , 'L', locB[0], locB[1]);
				move('R' , 'L', locR[0], locR[1]);
			}
			
			int val = check();
			if(val==1) { //성공 = 종료
				if(cnt<answer) answer = cnt;
				backtracking('N',NR,arrayR);
				backtracking('N',NB,arrayB);
				//backtracking 복귀
				return;
			} else if(val==2) { // 비정상종료
				backtracking('N',NR,arrayR);
				backtracking('N',NB,arrayB);
				//backtracking 복귀
			} else { //그대로 진행
				recursive(cnt+1,'L');
				backtracking('N',NR,arrayR);
				backtracking('N',NB,arrayB);
				//backtracking 복귀
			}
		}
		
		if(dir!='U') { //D로 이동
			int MR = locR[1];
			char[] arrayR = new char[N];
			
			int MB = locB[1]; 
			char[] arrayB = new char[N];
			
			for(int i=0;i<N;i++) {
				arrayR[i] = array[i][MR];
				arrayB[i] = array[i][MB];
			}
			
			if(locR[0]<=locB[0]) { //무조건 B먼저 시작한다.
				move('B' , 'D', locB[0], locB[1]);
				move('R' , 'D', locR[0], locR[1]);
			} else { //무조건 R먼저 시작한다.
				move('R' , 'D', locR[0], locR[1]);
				move('B' , 'D', locB[0], locB[1]);
			}
			
			int val = check();
			if(val==1) { //성공 = 종료
				if(cnt<answer) answer = cnt;
				backtracking('M',MR,arrayR);
				backtracking('M',MB,arrayB);
				//backtracking 복귀
			} else if(val==2) { // 비정상종료
				backtracking('M',MR,arrayR);
				backtracking('M',MB,arrayB);
				//backtracking 복귀
			} else { //그대로 진행
				recursive(cnt+1,'D');
				backtracking('M',MR,arrayR);
				backtracking('M',MB,arrayB);
				//backtracking 복귀
			}
		}
		
		if(dir!='D') { //U로 이동
			int MR = locR[1];
			char[] arrayR = new char[N];
			
			int MB = locB[1]; 
			char[] arrayB = new char[N];
			
			for(int i=0;i<N;i++) {
				arrayR[i] = array[i][MR];
				arrayB[i] = array[i][MB];
			}
			
			if(locR[0]<=locB[0]) { //무조건 R먼저 시작한다.
				move('R' , 'U', locR[0], locR[1]);
				move('B' , 'U', locB[0], locB[1]);
			} else { //무조건 B먼저 시작한다.
				move('B' , 'U', locB[0], locB[1]);
				move('R' , 'U', locR[0], locR[1]);
			}
			
			int val = check();
			if(val==1) { //성공 = 종료
				if(cnt<answer) answer = cnt;
				backtracking('M',MR,arrayR);
				backtracking('M',MB,arrayB);
				//backtracking 복귀
				return;
			} else if(val==2) { // 비정상종료
				backtracking('M',MR,arrayR);
				backtracking('M',MB,arrayB);
				//backtracking 복귀
			} else { //그대로 진행
				recursive(cnt+1,'D');
				backtracking('M',MR,arrayR);
				backtracking('M',MB,arrayB);
				//backtracking 복귀
			}
		}
	}
}