백준 13460

문제

Code

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

public class P13460 {

	static int[][] move = { { 1, 0 }, { -1, 0 }, { 0, -1 }, { 0, 1 } };	// 상하좌우 이동
	static char[][] board;
	static boolean[][][][] visited;	// 방문여부

	static int red_row, red_col, blue_row, blue_col; // 빨간 구슬, 파란 구슬 좌표
	static int result; // 결과(보드를 기울인 횟수)
	
	static class Pos {
		int red_x;	// 빨간 구슬 가로 좌표
		int red_y;	// 빨간 구슬 세로 좌표
		int blue_x;	// 파란 구슬 가로 좌표
		int blue_y;	// 파란 구슬 세로 좌표
		int count;	// 보드를 기울인 횟수

		Pos(int red_x, int red_y, int blue_x, int blue_y, int count) {
			this.red_x = red_x; 	
			this.red_y = red_y; 	
			this.blue_x = blue_x; 	
			this.blue_y = blue_y; 	
			this.count = count; 	
		}
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");

		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		board = new char[N][M];
		visited = new boolean[N][M][N][M];

		for(int i = 0; i < N; i++) {
			String input = br.readLine();
			for(int j = 0; j < M; j++) {
				board[i][j] = input.charAt(j);

				// 빨간구슬, 파란구슬일 경우 좌표 저장하고 보드에는 '.'으로 기록
				if(board[i][j] == 'R') {
					red_row = i;
					red_col = j;
					board[i][j] = '.';
				}
				else if(board[i][j] == 'B') {
					blue_row = i;
					blue_col = j;
					board[i][j] = '.';
				}
			}
		}
		bfs();
		
		if(result == -1 || result == 0 || result > 10) {
			result = -1;
		}
		
		bw.write(String.valueOf(result));
		br.close();
		bw.flush();
		bw.close();
	}
	private static void bfs() {
		Queue<Pos> q = new LinkedList<>();
		q.add(new Pos(red_row, red_col, blue_row, blue_col, 0));
		
		while(!q.isEmpty()) {
			Pos now = q.poll();
			if(now.count > 10) {
				result = -1;
				return;
			}
			// 상하좌우 기울이기
			for(int i = 0; i < 4; i++) {
				int temp_red_x = now.red_x;
				int temp_red_y = now.red_y;
				int temp_blue_x = now.blue_x;
				int temp_blue_y = now.blue_y;
				int temp_count = now.count;


				// 빨간 구슬 - 벽을 만날 때까지 기울이기
				while(board[temp_red_x + move[i][0]][temp_red_y + move[i][1]] != '#') {
					temp_red_x += move[i][0];
					temp_red_y += move[i][1];
					// 구멍을 만나면 끝
					if(board[temp_red_x][temp_red_y] == 'O') {
						break;
					}
				}
				// 파란 구슬 - 벽을 만날 때까지 기울이기
				while(board[temp_blue_x + move[i][0]][temp_blue_y + move[i][1]] != '#') {
					temp_blue_x += move[i][0];
					temp_blue_y += move[i][1];
					// 구멍을 만나면 끝
					if(board[temp_blue_x][temp_blue_y] == 'O') {
						break;
					}
				}
				// 빨간 구슬, 파란 구슬 동시에 구멍에 빠질 때 --> 중단
				if(board[temp_red_x][temp_red_y] == '0' && board[temp_blue_x][temp_blue_y] == 'O') {
					continue;
				}
				//  파란 구슬 먼저 구멍에 빠질 때 --> 중단
				else if(board[temp_blue_x][temp_blue_y] == 'O') {
					continue;
				}
				//  빨간 구슬 먼저 구멍에 빠질 때 --> 끝
				else if(board[temp_red_x][temp_red_y] == 'O') {
					result = now.count + 1;
					return;
				}
				// 문제조건 : "빨간 구슬과 파란 구슬은 동시에 같은 칸에 있을 수 없다."
				// 문제조건 : "또, 빨간 구슬과 파란 구슬의 크기는 한 칸을 모두 차지한다."
				
				// 빨간 구슬과 파란 구슬이 같은 장소에 있는 경우
				else if(temp_red_x == temp_blue_x && temp_red_y == temp_blue_y) {
					double red_dist = Math.pow(temp_red_x - now.red_x, 2) + Math.pow(temp_red_y - now.red_y, 2);
					double blue_dist = Math.pow(temp_blue_x - now.blue_x, 2) + Math.pow(temp_blue_y - now.blue_y, 2);
					
					if(red_dist > blue_dist) {
						temp_red_x -= move[i][0];
						temp_red_y -= move[i][1];
					}
					else {
						temp_blue_x -= move[i][0];
						temp_blue_y -= move[i][1];
					}
					
				}
				// 해당 사항 없는 경우 --> 큐에 저장하고 다시 기울이기
				if(!visited[temp_red_x][temp_red_y][temp_blue_x][temp_blue_y]) {
					visited[temp_red_x][temp_red_y][temp_blue_x][temp_blue_y] = true;
					q.add(new Pos(temp_red_x, temp_red_y, temp_blue_x, temp_blue_y, temp_count + 1));
				}
			}
		}

	}
}