알고리즘 - 구슬 탈출2

문제

• 링크

코드

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

public class BOJ_13640 {
	// 상, 하, 좌, 우
	private static int[] dr = {-1, 1, 0, 0};
	private static int[] dc = {0, 0, -1, 1};
	
	static int redR = 0; 
	static int redC = 0;
	static int blueR = 0;
	static int blueC = 0;
	static int endR = 0;
	static int endC = 0;
	static char[][] arr;
	static boolean[][][][] visited;
	static int N,M;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stk = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(stk.nextToken());
		M = Integer.parseInt(stk.nextToken());
		
		arr = new char[N][M];
		visited = new boolean[N][M][N][M];
		for(int i = 0; i < N ; i++) {
			
			char[] line = br.readLine().toCharArray();
			
			for(int j = 0; j < M ; j++) {
				
				arr[i][j] = line[j];
				if(arr[i][j] == 'R') {
					redR = i; 
					redC = j;
				}
				if(arr[i][j] == 'B') {
					blueR = i;
					blueC = j;
				}
				if(arr[i][j] == 'O') {
					endR = i;
					endC = j;
				}
				
				
			}
			
		}
		
		System.out.print(bfs());
		
	}
	
	private static int bfs() {
		// TODO Auto-generated method stub
		Queue<int[]> queue = new LinkedList<>();
		queue.add(new int[] {redR,redC,blueR,blueC, 1});
		visited[redR][redC][blueR][blueC] = true;

		while(!queue.isEmpty()) {
			
			int[] pop = queue.poll();
			if(pop[4] > 10) {
				return -1;
			}
			
			for(int i = 0 ; i < 4 ; i++) {
				int nRr = pop[0];
				int nRc = pop[1];
				int nBr = pop[2];
				int nBc = pop[3];
				
				boolean isRedOut = false;
				boolean isBlueOut = false;
				
				while(arr[nRr+dr[i]][nRc+dc[i]] != '#') {
					nRr += dr[i];
					nRc += dc[i];
					
					if(nRr == endR && nRc == endC) {
						isRedOut = true;
						break;
					}
					
				}
				
				while(arr[nBr+dr[i]][nBc+dc[i]] != '#') {
					nBr += dr[i];
					nBc += dc[i];
					
					if(nBr == endR && nBc == endC) {
						isBlueOut = true;
						break;
					}
					
				}
				
				if(isBlueOut) {
					continue;
				}
				else if(isRedOut & !isBlueOut) {
					return pop[4];
				}
				
				if(nRr == nBr && nRc == nBc) {
//					System.out.println(Arrays.toString(pop));
//					System.out.println(nRr+","+nRc+ " " + nBr + ","+nBc);
					switch(i) {
						case 0:
							
							if(pop[0] >= pop[2]) {
								nRr -= dr[i];
							}
							else {
								nBr -= dr[i]; 
							}
								
							break;
							
						case 1:
							
							if(pop[0] <= pop[2]) {
								nRr -= dr[i];
							}
							else {
								nBr -= dr[i]; 
							}
								
							break;
							
						case 2:
							
							if(pop[1] >= pop[3]) {
								nRc -= dc[i];
							}
							else {
								nBc -= dc[i]; 
							}
								
							break;
							
						case 3:
							
							if(pop[1] <= pop[3]) {
								nRc -= dc[i];
							}
							else {
								nBc -= dc[i]; 
							}
								
							break;
					}
					
				}
				
				if(!visited[nRr][nRc][nBr][nBc]) {
					visited[nRr][nRc][nBr][nBc] = true;
					queue.add(new int[] {
							nRr, nRc, nBr, nBc, pop[4]+1
					});
				}
				
				
					
			}
			
		}
		
		return -1;
		
	}
	
}

회고

• 어우 생각하다가 도저히 edge를 못찾겠어서 블로그를 참고 링크

  • Java를 통해 문제를 풀어야 함 ㅠㅠㅠ => 많이 까먹음

    	- Eclipse에 익숙해져야 함 

  • 와.. 얼마나 정확하고 모든 경우를 생각해서 개발해야 하는지 잘 알려주는 듯!

  • 꾸준히 SWER 문제를 풀어보자!