[BOJ 13459] 구슬 탈출 (Java)

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

13459번: 구슬 탈출

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_13459 {
	static class Info{
		int red_r, red_c, blue_r, blue_c;
		int cnt;
		public Info(int red_r, int red_c, int blue_r, int blue_c, int cnt) {
			this.red_r = red_r;
			this.red_c = red_c;
			this.blue_r = blue_r;
			this.blue_c = blue_c;
			this.cnt = cnt;
		}
	}
	static int[] dr= {-1,1,0,0};
	static int[] dc= {0,0,-1,1};
	static int N, M;
	static int[][] map;
	static boolean[][][][] visited;
	static int hole_r, hole_c, r_r, r_c, b_r, b_c;
	static int answer=0;
	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 int[N][M];
		visited=new boolean[N][M][N][M];
		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]=='O') {
					hole_r=i;
					hole_c=j;
				}
				else if (map[i][j]=='R') {
					r_r=i;
					r_c=j;
				}
				else if (map[i][j]=='B') {
					b_r=i;
					b_c=j;
				}
			}
		}
		bfs();
		System.out.println(answer);
	}
	private static void bfs() {
		Queue<Info> q=new LinkedList<>();
		q.add(new Info(r_r, r_c, b_r, b_c, 0));
		visited[r_r][r_c][b_r][b_c]=true;
		while (!q.isEmpty()) {
			Info curr=q.poll();
			if (curr.cnt>10) break;
			if (curr.red_r==hole_r && curr.red_c==hole_c) {
				answer=1;
				break;
			}
			for (int i=0; i<4; i++) {
				int[] pos=move(curr.red_r, curr.red_c, curr.blue_r, curr.blue_c, i);
				if (pos!=null) {
					int nrr=pos[0];
					int nrc=pos[1];
					int nbr=pos[2];
					int nbc=pos[3];
					if (!visited[nrr][nrc][nbr][nbc]) {
						visited[nrr][nrc][nbr][nbc]=true;
						q.add(new Info(nrr, nrc, nbr, nbc, curr.cnt+1));
					}
				}
				
			}
		}
		
	}
	private static int[] move(int red_r, int red_c, int blue_r, int blue_c, int d) {
		int[] pos=null;
		int start_rr=red_r, start_rc=red_c, start_br=blue_r, start_bc=blue_c;
		boolean rFlag=false;
		boolean bFlag=false;
		while (true) {
			int nr=red_r+dr[d];
			int nc=red_c+dc[d];
			if (map[nr][nc]=='#') break;
			red_r=nr;
			red_c=nc;
			if (map[red_r][red_c]=='O') {
				rFlag=true;
				break;
			}
		}
		while (true) {
			int nr=blue_r+dr[d];
			int nc=blue_c+dc[d];
			if (map[nr][nc]=='#') break;
			blue_r=nr;
			blue_c=nc;
			if (map[blue_r][blue_c]=='O') {
				bFlag=true;
				break;
			}
		}
		//blue가 hole, red,blue 같이 hole이면 그건 탐색하지 않음
		if (bFlag || (rFlag && bFlag)) return pos;
		if (red_r==blue_r && red_c==blue_c) {	//겹친 경우 재조정
			if (start_rc==start_bc) {
				if (d==0) {
					if (start_rr<start_br) blue_r-=dr[d];
					else red_r-=dr[d];
				}
				else if (d==1) {
					if (start_rr<start_br) red_r-=dr[d];
					else blue_r-=dr[d];
				}
			}
			else if (start_rr==start_br) {
				if (d==2) {
					if (start_rc<start_bc) blue_c-=dc[d];
					else red_c-=dc[d];
				}
				else if (d==3) {
					if (start_rc<start_bc) red_c-=dc[d];
					else blue_c-=dc[d];
				}
			}
		}
		pos=new int[4];
		pos[0]=red_r; pos[1]=red_c; pos[2]=blue_r; pos[3]=blue_c;
		return pos;
	}

}

BFS, 시뮬레이션 문제

 

다음과 같이 동작한다:

1) 초기 빨간공, 파란공 위치를 큐에 넣고 BFS를 돌린다

2)BFS 돌릴 때, 인접 4방향으로 공들을 움직인다. 

  -움직일 때는 move 함수를 사용한다

  -빨간공, 파란공을 벽이나 구멍을 만날때까지 움직여준다

  -빨간공과 파란공이 모두 hole에 들어갔거나, 파란공이 hole에 들어가있으면 탐색을 하지 않으므로 바로 리턴해준다

  -위와 같은 경우가 아니면, 빨간공, 파란공 위치를 재조정해준다 (겹칠 case 고려)

      - 움직이는 방향, 초기 위치에 따라 재조정을 해준다

  -재조정이 완료되면 새로 변경된 공들의 위치를 배열에 넣어서 리턴한다

3) 새로 변경된 공들의 위치가 visit 배열(visited[빨간공의 현재 행 번호][빨간공의 현재 열 번호][파란공의 현재 행 번호][파란공의 현재 열 번호])에서 미방문 상태이면, 큐에 그것을 넣어주고 방문 표시를 해준다. 

4)BFS 종료 조건은 빨간공이 현재 hole 위치에 있거나 혹은 10번 초과로 굴렸을 경우이다.

 

 

이 문제의 포인트는 BFS로 가능한 경우의 수를 탐색해주는 것이다.