[백준] 13460 구슬 탈출 2 (삼성SW역량테스트 기출 문제) -JAVA

www.acmicpc.net/problem/13460

13460번: 구슬 탈출 2

처음으로 한 시간 만에 푼 문제...

그간의 성장세가 눈에 보여 좋았다!

 

풀이

알고리즘 파악

 

최단거리 bfs 문제 + 구현

 

구현

 

1. queue에는 빨간구슬과 파란 구슬의 위치를 저장한다. 

이를 배열로 표현하였다. marble 배열의 0 = 빨간 구슬의 x , 1=  빨간 구슬의 y , 3= 파란 구슬의 x ,4= 파란 구슬의 y 

 

2. bfs를 통해 구슬을 움직인다. 방향은 상하좌우. 이것을 dx, dy 배열로 표현하였다.

 

3. 구슬을 움직일시

   1) 파란구슬과 빨간 구슬 둘 다 더이상 움직일 수 없다 ->다음 턴으로 넘어감

   2) 파란구슬이 구멍에 들어감, 실패-> 다음 턴으로 넘어가지 않음

   3) 빨간구슬이 골인, 성공 -> 종료

   세가지 케이스로 구분하였고 각 케이스의 경우를 return 하도록 check_status 함수로 구현하였다.

 

4. check_status 함수의 while 반복문 속 check_move는 구슬의 위치정보를 파악한다. 

   1) 이동위치에 장애물이 있거나 다른 구슬이 있다 -> 이동 불가

   2) 구멍이 있다. -> 구멍에 들어감  

   3) 그 외 -> 이동 가능

  check_status 함수와 마찬가지로 각각의 경우를 return 하도록 하였다. 이때 빨간 구슬과 파란 구슬의 위치정보를 각각     파악하도록 한다. 

 

5. 중복된 위치 이동을 제거하디 위해 HashSet을 이용하였다. 각각의 좌표를 문자열로 치환하여 저장하였고, 중복 방문을 방지하였다. (다른사람들은 주로 4차원 배열을 사용하였다. 이 방법이 더욱 효율적인듯 하다) 

 

특이사항

 

 1. 턴은 10번 이하여야 한다. cnt <10 일 때 다음 턴으로 넘어가도록 하였다. 이를 처음에 cnt <=10으로 표현하는 실수를  했다... 

 2. 빨간 구슬과 파란 구슬이 동시에 구멍에 빠져도 실패이다.

빨간 구슬이 구멍에 빠지더라도 같은 턴에 파란 구슬이 빠지면 실패다. 이를 boolean 값인 r_goal을 통해서 구현하였다. 빨간 구슬이 구멍이 빠지면 r_goal를 true로 만들고 빨간 구슬을 제거한다. 이후 파란 구슬만 이동하는데 파란 구슬이 구멍에 빠지지 않고 장애물을 만나면 성공, 구멍에 빠지면 실패이다.  

   

 

 

import java.io.*;
import java.util.Queue;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.StringTokenizer;
import java.util.HashSet;

public class Main {
	static int n,m;
	static int answer = -1;
	static int[] dx = {-1,1,0,0};
	static int[] dy = {0,0,-1,1};
	static HashSet<String> set = new HashSet<>();
	static char[][] map;
    public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
    	 BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	 BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    	 StringTokenizer st = new StringTokenizer(br.readLine()," ");
    	 n = Integer.parseInt(st.nextToken());
    	 m = Integer.parseInt(st.nextToken());
    	 map = new char[n][m];
    	 int[] marble = new int[4];
    	
    	 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] =='R') 
    			 {
    				 marble[0] = i;
    				 marble[1] = j;
    			 }
    			 else if(map[i][j] == 'B')
    			 {
    				 marble[2] = i;
    				 marble[3] = j;
    			 }
    		 }
    	 }
    	 Queue<int[]> queue = new LinkedList<>();
    	 queue.offer(marble);
    	 set.add(intToStr(marble[0],marble[1],marble[2],marble[3]));
    	 bfs(queue,1);
    	 
    	 bw.write(Integer.toString(answer));
         bw.flush();
         bw.close();
         br.close();
	}
    
    static void bfs(Queue<int[]> queue,int cnt)
    {
    	Queue<int[]> newQueue = new LinkedList<>();
    	boolean end=false;

    	while(!queue.isEmpty())
    	{
    		int[] marble = queue.poll();
    		
    		int[] up = Arrays.copyOf(marble, marble.length); //상
    	    int up_result = check_status(up,0);
            if(up_result==0 && set.add(intToStr(up[0],up[1],up[2],up[3]))) newQueue.offer(up);
            else if(up_result==2) {end = true; break;} 
            
            int[] down = Arrays.copyOf(marble, marble.length); //하
    	    int down_result = check_status(down,1);
            if(down_result==0  && set.add(intToStr(down[0],down[1],down[2],down[3]))) newQueue.offer(down); 
            else if(down_result==2) {end = true; break;} 
    	    
            int[] left = Arrays.copyOf(marble, marble.length); //좌
    	    int left_result = check_status(left,2);
            if(left_result==0 && set.add(intToStr(left[0],left[1],left[2],left[3]))) newQueue.offer(left); 
            else if(left_result==2) {end = true; break;} 
            
            int[] right = Arrays.copyOf(marble, marble.length); //우
    	    int right_result = check_status(right,3);
            if(right_result==0 && set.add(intToStr(right[0],right[1],right[2],right[3]))) newQueue.offer(right); 
            else if(right_result==2) {end = true; break;} 
    	}
    	
    	if(end) answer = cnt;
    	else if(cnt<10) bfs(newQueue,++cnt);
    }
    
    static int check_status(int[] marble , int d) // 0-삽입o 1-삽입x 2-골인 d-방향
    {
    	int rx = marble[0];
    	int ry = marble[1];
    	int bx = marble[2];
    	int by = marble[3];
    	boolean r_goal=false;
    	while(true)
    	{
    		int r=0;
    		int b=0;
           
    		if(!r_goal)
    		{
    		r = check_move(rx+dx[d],ry+dy[d],bx,by); //r
    		if(r==0) {rx+=dx[d]; ry+=dy[d];}	
    		else if(r==2) { rx=0; ry=0; r_goal=true;} //red는 통과
    		}
    		
    		b = check_move(bx+dx[d],by+dy[d],rx,ry); //b
    		if(b==0) {bx+=dx[d]; by+=dy[d];}	
    		else if(b==2) return 1; //삽입x
    		
    		if(r==1 && b==1)
    		{
    			marble[0] = rx;
    			marble[1] = ry;
    			marble[2] = bx;
    			marble[3] = by;
    			return 0;
    		}
    		else if(r_goal && b==1)
    		{
    			return 2;
    		}
    	}
    }

    static int check_move(int x, int y,int other_x,int other_y) //0 - 이동 가능 , 1 - 이동 불가 , 2 - 골
    {
    	if(map[x][y] == '#' || (x==other_x && y == other_y)) return 1; //# 이거나 서로 겹침
    	else if(map[x][y] == 'O') return 2;
    	else return 0;
    }
    
    static String intToStr(int x1, int y1, int x2, int y2)
    {
    	return new StringBuilder().append(x1+","+y1+","+x2+","+y2).toString();
    }
}