[백준] 13460 구슬 탈출 2, java

13460번: 구슬 탈출 2

백준의 삼성 SW 역량 테스트 기출 문제 문제집에 포함된 문제입니다.

주로 빡센 구현 문제를 내는 삼성 SW 역량 테스트 문제인 만큼 어려운 알고리즘 보다는 정확한 구현을 하는 문제였던 것 같습니다.

 

문제를 읽어보면 구슬을 최대 10번 이동시켜보고 그 이상의 횟수가 필요하다면 -1 을 반환하라고 나타나 있습니다. 그렇기 때문에 최악의 경우의 수가 4^10 정도라고 생각이 되었고, 2초의 시간 제한을 가진 문제였기에 완전 탐색을 해도 괜찮다고 판단하고 문제를 풀기 시작하였습니다.

 

아래 코드를 보면 알 수 있겠지만, print 문이 굉장히 많은데 아무리 생각해도 이상하게 예상치 못한 값들이 계속 나오고 이론상 나올 수 없는 ArrayIndexOutOfBoundsException 가 나타나고 있었습니다. 코드를 완성했다고 생각한 뒤 약 1시간 넘게 원인을 찾아 헤매었고 move() 함수를 실행시키는 부분이었습니다.

 

저는 red, blue를 static으로 선언을 해놓고 이를 move 함수에 넣어주며 탐색을 하려고 했는데, Java의 얕은 복사 덕분에 매번 순수한(?) red, blue의 좌표가 들어가야 했는데 이 red, blue의 좌표가 매번 바뀌면서 들어갔기 때문에 계속해서 틀린 답을 뱉어내고 있었던 것입니다.

 

위의 수정사항을 수정하고 난 뒤 이번에는 또 다른 오답을 뱉어내고 있었는데, 결국 찾아낸 이번 오류 역시도 얕은 복사의 문제였습니다. move() 함수에서 재귀를 통해서 접근하게 되는 다음 move()에게 전달해주기 위한 nred, nblue 역시 얕은 복사를 하며 입력을 해주고 있었고 이를 new int[]{} 를 이용하여 새로운 값으로 넣어주니 깔끔하게 문제가 해결되었습니다.

 

결정적으로 문제를 푸는데 걸린 시간은 30분 ~ 1시간 이었던 것 같았는데, 얕은 복사와 깊은 복사에 대한 개념이 부족했는지 이 때문에 거의 두배의 시간을 디버깅하는데만 시간을 쏟았던 것 같습니다. 앞으로는 배열을 파라미터로 넘기거나 계속 변경하며 사용하게 될 때에 문제가 생긴다면 이 부터 확인을 해봐야 겠습니다.

package com.bj;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main_BJ_13460_G1_구슬탈출2 {
	
	static int Y, X, result;
	static int[] dy = {-1, 1, 0, 0};
	static int[] dx = {0, 0, -1, 1};
	static int[] red, blue, goal;
	static char[][] board;
	
	static void move(int d, int cnt, int[] nred, int[] nblue) {
//		System.out.println("=============================================");
//		System.out.println("현재좌표 >> " + Arrays.toString(nred)+ Arrays.toString(nblue)+" 현재방향 >> " +d);
		if(cnt>10) {return;}
		if(cnt>result) {return;}
		
		//각 구슬이 움직인 횟수! 더 많이 움직인 쪽이 더 뒤에 있었다는 의미가 됩니다.
		int rcnt = 0;
		int bcnt = 0;
		boolean rGoal = false;
		boolean bGoal = false;
		
		//빨간공 움직이기
		while(true) {
			nred[0] += dy[d];
			nred[1] += dx[d];
			
			rcnt++;
			//움직이는 도중에 goal에 들어갔다면
			if(nred[0] == goal[0] && nred[1] == goal[1]) {
//				System.out.println("redGoal >> " + rcnt);
				rGoal = true;
				break;
			//벽을 만났다면
			} else if(board[nred[0]][nred[1]] == '#') {
				nred[0] -= dy[d];
				nred[1] -= dx[d];
				rcnt--;
				break;
			}
		}
		
		//파란공 움직이기
		while(true) {
			nblue[0] += dy[d];
			nblue[1] += dx[d];
			
			bcnt++;
			//움직이는 도중에 goal에 들어갔다면
			if(nblue[0] == goal[0] && nblue[1] == goal[1]) {
//				System.out.println("blueGoal >> " + bcnt);
				bGoal = true;
				break;
				
			//벽을 만났다면
			} else if(board[nblue[0]][nblue[1]] == '#') {
				nblue[0] -= dy[d];
				nblue[1] -= dx[d];
				bcnt--;
				break;
			}
		}
		//만약 빨간공은 들어가고 파란공은 안들어갔다면!!
//		System.out.println("1blueGoal >> " + bGoal + " redGoal >> " + rGoal );
		if(rGoal && !bGoal) {
//			System.out.println("찾았따!! >> " + cnt);
			result = Math.min(cnt, result);
			return;
		} else if(!rGoal && !bGoal){

//			System.out.println("2blueGoal >> " + bGoal + " redGoal >> " + rGoal );
			//만약 같은 위치에서 멈췄다면 더 많이 움직인 공을 뒤로 한칸 옮겨줍니다.
			if(nred[0] == nblue[0] && nred[1] == nblue[1]) {
				if(rcnt > bcnt) {
					nred[0] -= dy[d];
					nred[1] -= dx[d];
				} else {
					nblue[0] -= dy[d];
					nblue[1] -= dx[d];
				}
			}
			
			for (int i = 0; i < 4; i++) {
				if(i != d) {
//					System.out.println("TEST111!!");
					int[] nRed = new int[] {nred[0], nred[1]};
					int[] nBlue= new int[] {nblue[0], nblue[1]};
					move(i, cnt+1, nRed, nBlue);
//					System.out.println("TEST222!!");
				}
			}
		}
			
	}
	
	//각각의 필요한 오브젝트를 찾아냅니다.
	static void findObj() {
		goal = new int[2];
		red = new int[2];
		blue = new int[2];
		
		for (int i = 0; i < Y; i++) {
			for (int j = 0; j < X; j++) {
				if(board[i][j] == 'R') {
					red[0] = i;
					red[1] = j;
				} else if(board[i][j] == 'B') {
					blue[0] = i;
					blue[1] = j;
				} else if(board[i][j] == 'O') {
					goal[0] = i;
					goal[1] = j;
				}
			}
		}
	}

	public static void main(String[] args) throws Exception{
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		Y = Integer.parseInt(st.nextToken());
		X = Integer.parseInt(st.nextToken());
		board = new char[Y][X];
		result = 11;
		
		for (int i = 0; i < Y; i++) {
			board[i] = br.readLine().toCharArray();
		}
		
		findObj();
		for (int i = 0; i < 4; i++) {
//			System.out.println("스타트 방향 변경!!");
//			System.out.println("goal >> " + Arrays.toString(goal));
			int[] nRed = new int[] {red[0], red[1]};
			int[] nBlue= new int[] {blue[0], blue[1]};
			move(i, 1, nRed, nBlue);
		}
		
//		move(2, 1, red, blue);
//		move(3, 1, red, blue);
//		move(1, 1, red, blue);
//		move(0, 1, red, blue);
		
		if(result>10) result = -1;
		System.out.println(result);
	}
}