[BOJ-13460]구슬탈출2 -Java

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

13460번: 구슬 탈출 2

package 시뮬레이션;

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

public class boj_13460_구슬탈출2 {
	static int N, M, result;
	static char copyMap[][];
	static boolean endFlag;
	static class Point{
		int x,y;
		public Point(int x, int y) {
			this.x = x;
			this.y = y;
		}
	}

	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());
		result = Integer.MAX_VALUE;
		endFlag = false;
		char[][] map = new char[N][M];
		Point red=null;
		Point blue=null;

		for (int i = 0; i < N; i++) {
			String input = br.readLine();
			map[i] = input.toCharArray();
		}

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				if (map[i][j] == 'R') red = new Point(i,j);
				else if (map[i][j] == 'B') blue = new Point(i,j);
			}
		}
		dfs(map, 0, 0, 0, red,blue);
		result = result == Integer.MAX_VALUE ? -1 : result;
		System.out.println(result);
	}

	private static void dfs(char[][] map, int cnt, int xMove, int yMove, Point red, Point blue) {
		if (cnt == 11) return;

		char copyMap[][] = copy(map); // 맵 복사
		if(!(xMove==0 && yMove==0)) {
			if(!move(copyMap, xMove, yMove, red, blue, cnt)) return ;
		}

		dfs(copyMap, cnt + 1, 0, -1, new Point(red.x,red.y), new Point(blue.x,blue.y)); //왼쪽
		dfs(copyMap, cnt + 1, 0, 1, new Point(red.x,red.y), new Point(blue.x,blue.y)); //오른쪽
		dfs(copyMap, cnt + 1, -1, 0, new Point(red.x,red.y), new Point(blue.x,blue.y)); //위
		dfs(copyMap, cnt + 1, 1, 0, new Point(red.x,red.y), new Point(blue.x,blue.y)); //아래
	}

	private static boolean move(char[][] map, int xMove, int yMove, Point red, Point blue, int cnt) {
		
		boolean redHoleFlag=false; //빨간공 골인 
		boolean blueHoleFlag=false; //파란공 골인
		boolean redStop=false; //빨간공 못움직임
		boolean blueStop=false; //파란공 못움직임 
		int rx=red.x;
		int ry=red.y;
		int bx=blue.x;
		int by=blue.y;
		
		while(true) { 
			redStop=false;
			blueStop=false;
			
			int nrx=rx+xMove; //빨간공 좌표이동
			int nry=ry+yMove;
			int nbx=bx+xMove; //파란공 좌표이동
			int nby=by+yMove;
			
			redStop=stopCheck(nrx,nry,map);
			
			if(!redStop && !redHoleFlag) { //빨강이 더 갈 수 있다면 && 구멍에 안들어갔다면 
				if(map[nrx][nry]=='O') { //만약 구멍이라면!
					redHoleFlag=true; //빨간공 구멍에 들어감
					map[rx][ry]='.'; //원래 있던 자리 초기화
				}
				else { //구멍 아니라면
					map[rx][ry]='.'; //원래 자리 초기화
					map[nrx][nry]='R'; //빨간공 위치 바꿔주고
					rx=nrx;
					ry=nry;
				}
			}
			
			blueStop=stopCheck(nbx,nby,map);
			
			if(!blueStop && !blueHoleFlag) { //파랑이 더 갈 수 있다면 && 구멍에 안들어갔다면 
				if(map[nbx][nby]=='O') { //만약 구멍이라면!
					blueHoleFlag=true; //파란공 구멍에 들어감
					map[bx][by]='.'; //원래 있던 자리 초기화
					break; // 파란공 들어가면 무조건 끝내기
				}
				else { //구멍 아니라면
					map[bx][by]='.'; //원래 자리 초기화
					map[nbx][nby]='B'; //파란공 위치 바꿔주고
					bx=nbx;
					by=nby;
				}
			}
			
			if(!redStop) redStop = redHoleFlag? true:false;
			if(!blueStop) blueStop = blueHoleFlag? true:false;
			if(redStop&&blueStop) break;
		}
		
		if(blueHoleFlag) return false; //파란공 들어가면  무조건 실패
		else if(redHoleFlag && !blueHoleFlag) { // 빨간공만 들어갔으면
			result=Math.min(result, cnt); //최솟값 구해주고
			return false; //끝내버림
		}
		red.x=rx; //공이 아무것도 안들어갔다면 -> 좌표를 바꿔서 들고가
		red.y=ry;
		blue.x=bx;
		blue.y=by;
		return true;
	}

	private static boolean stopCheck(int x, int y, char[][] map) {
		if (map[x][y] == '#' || map[x][y] == 'R' || map[x][y] == 'B') return true;
		return false;
	}

	private static char[][] copy(char[][] map) {
		char copyMap[][] = new char[N][M];
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < M; j++) {
				copyMap[i][j] = map[i][j];
			}
		}
		return copyMap;
	}
}

 

소요시간 : 2시간 10분

 

 

우선 문제가 생각할게 많아서 어려웠습니다..ㅜㅜ

최근 푼 문제 중 가장 어렵다고 생각했습니다.

 

알고리즘은 dfs를 사용하였습니다.

최솟값을 구하는 문제라 bfs가 더 좋을 거라고 생각하지만 뭔가 dfs로 푸는 게 더 쉬울 거 같아서 dfs로 풀었습니다..

 

우선 백트래킹을 하기 위해 map을 복사하여 사용했습니다.

 

로직을 살펴보면

 

1. 맵을 복사한다.

2. 현재 방향에 따라서 맵을 기울여준다.

 

가 끝입니다... 근데 2번에서 확인해줘야 할 사항이나 수행해야 할 사항이 좀 많습니다.

 

2-1 빨간 공, 파란 공 이동시켜주기

2-2 빨간공, 파란공 구멍에 들어가는지 확인하기

2-3 빨간공, 파란공 더 이상 못 가는지 확인하기

2-4 만약 공이 하나라도 들어갔다면 dfs 가지치기해주기

2-5 만약 공이 하나도 안 들어갔다면 좌표 업데이트해서 유지해주기

 

제 코드는 백준에 돌려본 결과.. 조금 느립니다...ㅜㅜ

위의 내용이 잘 이해 안 되시는 분들은 코드에 주석 꼼꼼하게 달아놨으니까 그거 보셔도 될 거 같습니다

 

끝~