[BOJ 13460] 구슬 탈출2 (Java)

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

13460번: 구슬 탈출 2

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

public class Main_BOJ_13460 {
	static class Pos{
		int red_r, red_c, blue_r, blue_c, dist;
		Pos(int red_r, int red_c, int blue_r, int blue_c, int dist) {
			this.red_r = red_r;
			this.red_c = red_c;
			this.blue_r = blue_r;
			this.blue_c = blue_c;
			this.dist=dist;
		}	
	}
	static char[][] map;
	static int N, M;
	static boolean[][][][] visited;
	static int[] dr= {-1,1,0,0};
	static int[] dc= {0,0,-1,1};
	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());
		map=new char[N][M];
		visited=new boolean[N][M][N][M];
		int red_r=-1, red_c=-1, blue_r=-1, blue_c=-1;
		for (int i=0; i<N; i++) {
			String s=br.readLine();
			for (int j=0; j<M; j++) {
				map[i][j]=s.charAt(j);
				if (map[i][j]=='B') {
					blue_r=i;
					blue_c=j;
				}
				else if (map[i][j]=='R') {
					red_r=i;
					red_c=j;
				}
				
			}
		}
		System.out.println(bfs(new Pos(red_r, red_c, blue_r, blue_c, 0)));

	}
	private static int bfs(Pos pos) {
		Queue<Pos> q=new LinkedList<>();
		q.add(pos);
		visited[pos.red_r][pos.red_c][pos.blue_r][pos.blue_c]=true;
		while (!q.isEmpty()) {
			Pos p=q.poll();
			if (p.dist>10) break;
			if (map[p.red_r][p.red_c]=='O') return p.dist;
			for (int i=0; i<4; i++) {
				int[] red=move(p.red_r, p.red_c, i);
				int[] blue=move(p.blue_r, p.blue_c, i);
				Pos next=adjust(red[0], red[1], blue[0], blue[1], i, p);	//움직인 위치 
				if (map[next.blue_r][next.blue_c]!='O' && !visited[next.red_r][next.red_c][next.blue_r][next.blue_c]) {
					q.add(new Pos(next.red_r, next.red_c, next.blue_r, next.blue_c, p.dist+1));
					visited[next.red_r][next.red_c][next.blue_r][next.blue_c]=true;
				}
			}
		}
		
		return -1;
	}

	private static int[] move(int start_r, int start_c, int d) {
		int[] loc=new int[2];
		int r=start_r, c=start_c;
		while (true) {
			r+=dr[d];
			c+=dc[d];
			if (map[r][c]=='#') {
				r-=dr[d];
				c-=dc[d];
				break;
			}
			if (map[r][c]=='O') {
				break;
			}	
		}
		loc[0]=r; loc[1]=c;
		return loc;
	}
	
	
	private static Pos adjust(int rr, int rc, int br, int bc, int d, Pos before) {
		Pos curr=new Pos(rr, rc, br, bc, -1);
		if (rr==br && rc==bc) {			//같을 때는 조정시키기
			if (map[rr][rc]=='O') return curr;
			if (d==0) {
				if (before.red_r<before.blue_r) {
					curr.blue_r+=1;
				}
				else{
					curr.red_r+=1;
				}
			}
			else if (d==1) {
				if (before.red_r<before.blue_r) {
					curr.red_r-=1;
				}
				else {
					curr.blue_r-=1;
				}
			}
			else if (d==2) {
				if (before.red_c<before.blue_c) {
					curr.blue_c+=1;
				}
				else {
					curr.red_c+=1;
				}
			}
			else if (d==3) {
				if (before.red_c<before.blue_c) {
					curr.red_c-=1;
				}
				else {
					curr.blue_c-=1;
				}
			}			
		}
		return curr;
	}
	
	

}

BFS 로 풀었다.

visited[빨간공 행][빨간공 열][파란공 행][파란공 열] 이런 식으로 방문 배열을 구현했다.

 

일단 빨간 공, 파란 공을 쭉 굴려준 뒤 만약 두 공의 위치가 같다면, hole 인 경우 그대로 리턴하고 그렇지 않은 경우 위치를 재조정해준다.

예를 들어, 직전에 R 00 B 이런 식으로 있었는데 왼쪽으로 굴린 경우라면, 파란 공 열의 위치를 +1 로 해서 재조정해주는 방식이다..