[백준온라인] 13460번 구슬 탈출 2

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

13460번: 구슬 탈출 2

 

문제 요약 : 판 위에 빨간구슬과 파란구슬이 있고 최소로 기울여서 빨간구슬만 빼내는 횟수

입력	출력
첫째 줄에 세로, 가로 크기 N, M (3 ≤ N, M ≤ 10) N개의 줄에 길이 M의 문자열 ['.', '#', 'O', 'R', 'B'] '.' 빈 칸 '#' 장애물 'O'는 구멍 [1개] 'R' 빨간 구슬 [1개] 'B'는 파란 구슬 [1개] 보드의 가장자리에는 모두 '#'	빨간 구슬을 구멍을 통해 빼낼 수 있는는 최소 횟수 출력 10번 초과 또는 불가능 하면 -1을 출력

 

JAVA

채점 번호	아이디	문제 번호	결과	메모리	시간	언어	코드 길이
16324321	cbkpar	13460	맞았습니다!!	17396KB	100ms	Java	4049B

import java.io.*;

public class Main {
	static int[][] map; // 보드판
	static int y,x,gy,gx; // 보드판 넓이, 구멍 위치
	static int move = 11; // 최대 횟수 지정

	public static void main(String args[]) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int i,j;
		int y1 = 0,x1 = 0 ,y2 = 0,x2 = 0;
		
		String str = "";
		
		str = br.readLine();
		String[] arr = str.split(" ");
		y = Integer.parseInt(arr[0]);
		x = Integer.parseInt(arr[1]);
		map = new int[y][x]; // 보드판 크기 설정
		for(i=0;i<y;i++) {
			str = br.readLine();
			for(j=0;j<x;j++) {
				if(str.charAt(j)=='#') {
					map[i][j] = 0; // 0은 이동불가
				}else if(str.charAt(j)=='.') {
					map[i][j] = 1; // 1은 이동가능
				}else if(str.charAt(j)=='R') {
					y1 = i; //빨간구슬 y좌표
					x1 = j; //빨간구슬 x좌표
					map[i][j] = 0;
				}else if(str.charAt(j)=='B') {
					y2 = i; //파란구슬 y좌표
					x2 = j; //파란구슬 x좌표
					map[i][j] = 0;
				}else {
					gy = i; //구멍 y좌표
					gx = j; //구멍 x좌표
					map[i][j] = 1;
				}
			}
		}
		dfs(y1,x1,y2,x2,0); // 깊이우선검색
		if(move==11) { //10번 초과나 불가능하다면
			System.out.println("-1");
		}else {
			System.out.println(move);
		}
	}
	static void dfs(int ry, int rx, int by, int bx, int k) {
		if(k>=move) return; //지금까지 찾은 최소횟수보다 크다면 리턴
		if(by==gy&&bx==gx) return; // 파란공이 빠졌다면 리턴
		if(ry==gy&&rx==gx) {  // 파란공이 빠지지 않고 빨간공이 빠졌다면
			move = Math.min(move, k); // 최소횟수 수정 후 리턴
			return;
		}
		
        
        //공이 위로 갈때
		int ir = ry; // 빨간공 y좌표
		int ib = by; // 파란공 y좌표
		while(true) {
			if(ir==gy&&rx==gx) break; // 구멍이면 종료
			if(map[ir-1][rx]==1) { // 이동가능 하다면
				map[ir][rx] = 1;
				ir-=1;
				map[ir][rx] = 0;
				if(ir==gy&&rx==gx) map[ir][rx] = 1; //구멍이면 다시 이동가능하게 설정
			}else { //이동이 불가능하면 종료
				break;
			}
		}
		while(true) {
			if(ib==gy&&bx==gx) break;
			if(map[ib-1][bx]==1) {
				map[ib][bx] = 1;
				ib-=1;
				map[ib][bx] = 0;
				if(ib==gy&&bx==gx) map[ib][bx] = 1;
			}else {
				break;
			}
		}
        //빨간공 파란공 빨간공 순서로 한번더 해주어서 예외상황 방지
        //파란공 빨간공 파란공 순서로 해도 결과 같음
		while(true) {
			if(ir==gy&&rx==gx) break;
			if(map[ir-1][rx]==1) {
				map[ir][rx] = 1;
				ir-=1;
				map[ir][rx] = 0;
				if(ir==gy&&rx==gx) map[ir][rx] = 1;
			}else {
				break;
			}
		}
		if(ir!=ry||ib!=by) dfs(ir,rx,ib,bx,k+1); // 횟수증가후 탐색
		//이동 했던 공들 원위치
        map[ir][rx]=1;
		map[ib][bx]=1;
		map[ry][rx]=0;
		map[by][bx]=0;

		//아래로 공이 이동할때
		ir = ry;
		ib = by;
		while(true) {
			if(ir==gy&&rx==gx) break;
			if(map[ir+1][rx]==1) {
				map[ir][rx] = 1;
				ir+=1;
				map[ir][rx] = 0;
				if(ir==gy&&rx==gx) map[ir][rx] = 1;
			}else {
				break;
			}
		}
		while(true) {
			if(ib==gy&&bx==gx) break;
			if(map[ib+1][bx]==1) {
				map[ib][bx] = 1;
				ib+=1;
				map[ib][bx] = 0;
				if(ib==gy&&bx==gx) map[ib][bx] = 1;
			}else {
				break;
			}
		}
		while(true) {
			if(ir==gy&&rx==gx) break;
			if(map[ir+1][rx]==1) {
				map[ir][rx] = 1;
				ir+=1;
				map[ir][rx] = 0;
				if(ir==gy&&rx==gx) map[ir][rx] = 1;
			}else {
				break;
			}
		}
		if(ir!=ry||ib!=by) dfs(ir,rx,ib,bx,k+1);
		map[ir][rx]=1;
		map[ib][bx]=1;
		map[ry][rx]=0;
		map[by][bx]=0;
		
        //왼쪽으로 공이 이동할때
		ir = rx;
		ib = bx;
		while(true) {
			if(ry==gy&&ir==gx) break;
			if(map[ry][ir-1]==1) {
				map[ry][ir] = 1;
				ir-=1;
				map[ry][ir] = 0;
				if(ry==gy&&ir==gx) map[ry][ir] = 1;
			}else {
				break;
			}
		}
		while(true) {
			if(by==gy&&ib==gx) break;
			if(map[by][ib-1]==1) {
				map[by][ib] = 1;
				ib-=1;
				map[by][ib] = 0;
				if(by==gy&&ib==gx) map[by][ib] = 1;
			}else {
				break;
			}
		}
		while(true) {
			if(ry==gy&&ir==gx) break;
			if(map[ry][ir-1]==1) {
				map[ry][ir] = 1;
				ir-=1;
				map[ry][ir] = 0;
				if(ry==gy&&ir==gx) map[ry][ir] = 1;
			}else {
				break;
			}
		}
		if(ir!=rx||ib!=bx) dfs(ry,ir,by,ib,k+1);
		map[ry][ir]=1;
		map[by][ib]=1;
		map[ry][rx]=0;
		map[by][bx]=0;
		
        //오른쪽으로 공이 이동 할 때
		ir = rx;
		ib = bx;
		while(true) {
			if(ry==gy&&ir==gx) break;
			if(map[ry][ir+1]==1) {
				map[ry][ir] = 1;
				ir+=1;
				map[ry][ir] = 0;
				if(ry==gy&&ir==gx) map[ry][ir] = 1;
			}else {
				break;
			}
		}
		while(true) {
			if(by==gy&&ib==gx) break;
			if(map[by][ib+1]==1) {
				map[by][ib] = 1;
				ib+=1;
				map[by][ib] = 0;
				if(by==gy&&ib==gx) map[by][ib] = 1;
			}else {
				break;
			}
		}
		while(true) {
			if(ry==gy&&ir==gx) break;
			if(map[ry][ir+1]==1) {
				map[ry][ir] = 1;
				ir+=1;
				map[ry][ir] = 0;
				if(ry==gy&&ir==gx) map[ry][ir] = 1;
			}else {
				break;
			}
		}
		if(ir!=rx||ib!=bx) dfs(ry,ir,by,ib,k+1);
		map[ry][ir]=1;
		map[by][ib]=1;
		map[ry][rx]=0;
		map[by][bx]=0;
	}
}