백준_구슬 탈출2[Java]_도움요청

문제

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

13460번: 구슬 탈출 2

열심히 참고해서 풀었는데 아래와 같이 풀면 계속 틀렸습니다 가 뜬다.

나는 언제쯤 맞았습니다가 나올까..?

이유를 모르니 답답하다 !!!! ㅜㅜㅜㅜㅜ

 

풀이

틀렸습니다가 나오는 코드입니다. 참고만 해주세요.

package bj.test.ex02;

import java.util.Scanner;

public class EscapeMarble2 {
	static int N, M;
	static char[][] board;
	static int[] visit = new int[10];
	static Pair t, t2;
	static boolean end;
	static char[][] copy;
	
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		N = scan.nextInt();
		M = scan.nextInt();
		
		board = new char[10][10];
		copy = new char[10][10];
		t = new Pair(0, 0, 0, 0);
		t2 = new Pair(0, 0, 0, 0);
		for(int i = 0; i < N; i++) {
			String s = scan.next();
			for(int j = 0; j < M; j++) {
				board[i][j] = s.charAt(j);
				
				if(s.charAt(j) == 'R') {
					t.rx = i;
					t.ry = j;
				}
				if(s.charAt(j) ==  'B') {
					t.bx = i;
					t.by = j;
				}
			}
		}
		
//		for(int i = 0; i < N; i++) {
//			for(int j = 0; j < M; j++) {
//				System.out.print(board[i][j] + " ");
//			}
//			System.out.println("");
//		}
		
		
		solution(0, -1);
		if(result >= 11) result = -1;
		System.out.println(result);
		// 10번 초과되면 -1로 출력
		// 최소 몇 번 만에 빨간 구슬이 구멍으로 빠져나올 수 있는지 출력 
		// 파란 공 구멍으로 빠지면 실패 
		
		// 왼, 오른쪽, 위, 아래쪽 
		// 기울이는 동작을 그만하는 것은 더 이상 구슬이 움직이지 않을 때까지 
		scan.close();
	}
	
	static int result = 11;
	private static void solution(int idx, int prev) {
		// idx = 현재 몇번째인지 prev : 이전 동작 
		// dfs 
		if(idx == 10) {
			init();
			for(int i = 0; i < 10; i++) {
				if(result <= i+1) return; // 이건 뭐쥬 
				
				if(lean(visit[i])) {
					result = Math.min(result, i+1);
					return;
				}
				if(end) break;
			}
			return;
		}
		
		// 연속적으로 같은 동작을 할 필요가 없다 *****
		// 동작을 쫙 만들어준다. 
		for(int i = 0; i < 4; i++) {
			if(i == prev) continue;
			visit[idx] = i;
			solution(idx+1,i);
		}
		
	}

    private static void init() {
        // R B 위치 초기화
        t2.rx = t.rx; t2.ry = t.ry;
        t2.bx = t.bx; t2.by = t.by;
        end = false; // 게임끝 초기화
        // 맵  복사
        for(int i=0;i<N;i++) {
            for(int j=0;j<M;j++) 
                copy[i][j] = board[i][j];
        }
    }
    
	static int[][] dir = {{1,0}, {0,1}, {-1,0}, {0,-1}};
	// 왼, 오른쪽, 위, 아래쪽 
	private static boolean lean(int d) {
		int rx = t2.rx, ry = t2.ry, bx = t2.bx, by = t2.by;
		boolean flagR=false,flagRB=false,
                flagBR=false,flagB=false;
		
		// 빨간 구슬 
		while(true)	{
			// 위치를 이동시켜본다. 
			rx = rx + dir[d][0]; ry = ry + dir[d][1];
			// . 계속 이동
			
			if(copy[rx][ry] != '.') {
				if(copy[rx][ry] == 'O') { // O 구멍 숑
					flagR = true;
				}else if(copy[rx][ry] == 'B') { // B 파랑공이랑 마주침 
					flagRB = true;
					// B일 경우 안멈추는 이유는
					// B가 같이 이동하기 떄문이다. 일단 쭉 옮기고 나중에 한칸 물러나서 B자리 남겨준다. 
					continue;
				}
				// # 벽에 가로막힘 이동 중단 
				rx = rx- dir[d][0]; ry = ry - dir[d][1];
				break;
			}
			
		}
		
		if(flagRB) {
			rx = rx- dir[d][0]; ry = ry - dir[d][1];
		}
		
		while(true)	{
			// 위치를 이동시켜본다. 
			bx = bx + dir[d][0]; by = by + dir[d][1];
			// . 계속 이동
			
			if(copy[bx][by] != '.') {
				if(copy[bx][by] == 'O') { // O 구멍 숑
					flagB = true;
				}else if(copy[bx][by] == 'R') { // B 파랑공이랑 마주침 
					flagBR = true;
					continue;
				}
				// # 벽에 가로막힘 이동 중단 
				bx = bx- dir[d][0]; by = by - dir[d][1];
				break;
			}
		}
		if(!flagRB && flagBR) {
			bx = bx- dir[d][0]; by = by - dir[d][1];
		}
		
		if(flagB) {
			end = true;
			return false;
		}
		
		if(flagR) return true;
		
		copy[rx][ry] = 'R';
		copy[bx][by] = 'B';
		copy[t2.rx][t2.ry] = '.';
		copy[t2.bx][t2.by] = '.';
		
		t2.rx = rx;
		t2.bx = bx;
		t2.ry = ry;
		t2.by = by;
		
		return false;
	}

	static class Pair {
		int rx, ry, bx, by;
		Pair(int rx, int ry, int bx, int by){
			this.rx = rx;
			this.ry = ry;
			this.bx = bx;
			this.by = by;
		}
	}
	
}

 

 

흐름

dfs 방식으로 구현하였다.

bfs가 더 빠르다고 하여 그 방식으로도 해봐야겠다. 

빨간 구슬과 파란 구슬이 만났을 때 처리 방식을 잘 살펴보자. 

 

 

참고 

https://whereisusb.tistory.com/222

[백준] 13460번 구슬 탈출2

 

- 여기 참고해보자 !!!

C++은 코드가 참 간단해보이네 !!! ,,,

https://jason9319.tistory.com/217

BOJ)13460 구슬탈출2