[BOJ] 13460 구슬 탈출 2

 

 

[문제]

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

 

 

[소스 코드]

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

public class Main {
	static int n,m;
	static char[][] map;
	static int blueR,blueC,redR,redC;
	static int[] dr = {-1,1,0,0};
	static int[] dc = {0,0,-1,1};
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		map = new char[n][m];
		for(int i=0;i<n;i++) {
			String str = br.readLine();
			for(int j=0;j<m;j++) {
				map[i][j] = str.charAt(j);
				if(map[i][j]=='B') {
					blueR = i;
					blueC = j;
				}
				if(map[i][j]=='R') {
					redR = i;
					redC = j;
				}
			}
		}
		System.out.println(bfs(redR,redC,blueR,blueC));
	}
	private static int bfs(int redR,int redC,int blueR,int blueC) {
		Queue<int[]> q = new LinkedList<>();
		boolean[][][][] visit = new boolean[n][m][n][m];
		q.offer(new int[] {redR,redC,blueR,blueC,0});
		visit[redR][redC][blueR][blueC] = true;
		int rR,rC,bR,bC;
		while(!q.isEmpty()) {
			int[] curr = q.poll();
			if(curr[4]>=10) {
				return -1;
			}
			for(int d=0;d<4;d++) {
				int nrR = curr[0];
				int nrC = curr[1];
				int nbR = curr[2];
				int nbC = curr[3];
				boolean blue = false;
				boolean red = false;
				while(true) {
					nbR += dr[d];
					nbC += dc[d];
					if(map[nbR][nbC]=='O') {
						blue = true;
						break;
					}
					if(map[nbR][nbC]=='#') {
						nbR -= dr[d];
						nbC -= dc[d];
						break;
					}
				}
				while(true) {
					nrR += dr[d];
					nrC += dc[d];
					if(map[nrR][nrC]=='O') {
						red = true;
						break;
					}
					if(map[nrR][nrC]=='#') {
						nrR -= dr[d];
						nrC -= dc[d];
						break;
					}
				}
				if(blue) continue;
				if(red) return curr[4]+1;
				if(nrR==nbR && nrC==nbC) {
					if(d==0) {
						if(curr[0]<curr[2]) nbR -= dr[d];
						else nrR -= dr[d];
					}
					else if(d==1) {
						if(curr[2]<curr[0]) nbR -= dr[d];
						else nrR -= dr[d];
					}
					else if(d==2) {
						if(curr[1]<curr[3]) nbC -= dc[d];
						else nrC -= dc[d];
					}
					else {
						if(curr[3]<curr[1]) nbC -= dc[d];
						else nrC -= dc[d];
					}
				}
				if(!visit[nrR][nrC][nbR][nbC]) {
					q.offer(new int[] {nrR,nrC,nbR,nbC,curr[4]+1});
					visit[nrR][nrC][nbR][nbC] = true;
				}
			}
		}
		return -1;
	}
}

 

brute force: 고정되어 있을 경우, 모든 경우 실행

bfs: 가능한 작은 횟수로 실행