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

SW 역량테스트 기출문제는 이전에 한 번씩 쭉 풀었었는데 다시 한 번 풀어보면서 오늘부터 감을 잃지 않으려고 한다!

 

이번에 푼 문제는 구슬 탈출 2 문제다.

 

 

문제보기

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

13460번: 구슬 탈출 2

나의 풀이

 

빨간 구슬을 구멍으로 빼낼 수 있는 최소의 움직임 횟수를 구하는 것이므로 BFS 문제이다.

여기서의 key point는 빨간 구슬과 파란 구슬이 동시에 움직이므로 BFS 방문여부를 저장하는 배열은 4차원이 된다.

 

int [][][][] c = new int[N][M][N][M];

[빨간 구슬의 i위치][빨간 구슬의 j위치][파란 구슬의 i위치][파란 구슬의 j위치]

 

구현 시나리오

 

1. 빨간 구슬의 시작 위치와 파란 구슬의 시작 위치에 대한 방문 여부를 체크하고 Queue에 넣는다.

 

2. Queue에 요소가 다 없어질 때까지 무한 루프를 돌면서 BFS 실행한다.

• 이 때, Queue에서 요소를 뽑았는데 10번 이상 이동을 한 경우는 실패로 간주하기 때문에 break;
• 만약, 빨간 공이 구멍에 위치한 경우 더 이상 게임을 진행할 필요가 없으므로 break;
• 파란 공이 구멍에 빠진 경우에 대해서는 실패로 간주하므로 그 case에 대한 여부는 더 이상 생각해주지 않아도 되기 때문에 continue;

3. Bfs 실행 과정은 다음과 같다.

•  빨간 구슬과 파란 구슬 각각 이동 (이동 방향은 상, 하, 좌, 우이며, 빨간 구슬과 파란 구슬은 같은 방향으로만 이동   할 수 밖에 없다)
• 이동한 빨간 구슬의 위치와 파란 구슬의 위치가 전에 방문한 적이 없는 위치라면 Queue에 넣고 방문 체크를 해준다.
• 예외 처리 | 빨간 구슬과 파란 구슬이 같은 위치로 이동한 경우(그러나 그 위치가 구멍이 아닌 경우) -> 각 빨간 구슬과 파란 구슬이 이동해온 거리를 구해서 이동 거리가 더 긴 구슬을 한 칸 옆으로 후퇴시킨다.

 

코드

 

//최단거리 BFS 문제
import java.io.*;
import java.util.*;

public class N_13460 {
	static class Status { // 큐에 현재 상태 저장
		int ri; // 빨간 공의 위치
		int rj;
		int bi; // 파란 공의 위치
		int bj;
		int cnt; // 움직인 횟수

		Status(int ri, int rj, int bi, int bj, int cnt) {
			this.ri = ri;
			this.rj = rj;
			this.bi = bi;
			this.bj = bj;
			this.cnt = cnt;
		}
	}
	
	static int [] dx = {0, 0, -1, 1};
	static int [] dy = {-1, 1, 0, 0};
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		try {
			String [] input = br.readLine().split(" ");
			int N = Integer.parseInt(input[0]);
			int M = Integer.parseInt(input[1]);
			
			int rsi = 0;      //빨간 공 시작 위치
			int rsj = 0;
			int bsi = 0;     //파란 공 시작 위치
			int bsj = 0;
			
			char [][] A = new char[N][M];
			for(int i=0;i<N;i++) {
				String str = br.readLine();
				
				for(int j=0;j<M;j++) {
					A[i][j] = str.charAt(j);
					if(A[i][j] == 'R') {
						rsi = i;
						rsj = j;
					}
					if(A[i][j] == 'B') {
						bsi = i;
						bsj = j;
					}
				}
			}
			
			//bfs
			Queue<Status> q = new LinkedList<Status>();
			int [][][][] c = new int[N][M][N][M];    //방문 여부 저장(빨간공 위치(i, j), 파란공 위치(i, j))
			
			c[rsi][rsj][bsi][bsj] = 1;
			q.offer(new Status(rsi, rsj, bsi, bsj, 0));
			
			while(!q.isEmpty()) {
				Status s = q.poll();
				
				if(s.cnt > 10) {    //10번이하로 움직일 수 없는 경우
					System.out.println(-1);
					System.exit(0);
				}
				if(A[s.bi][s.bj] == 'O') {   //파란 공이 빠지는 경우 실패
					continue;
				}
				if(A[s.ri][s.rj] == 'O' && A[s.bi][s.bj] != 'O') {    //완료 조건
					System.out.println(s.cnt);
					System.exit(0);
				}
				for(int i=0;i<dx.length;i++) {
					//빨간 공 이동
					int rni = s.ri;    //빨간 공의 다음 위치
					int rnj = s.rj;
					
					while(true) {
						rni += dx[i];
						rnj += dy[i];
						
						if(A[rni][rnj] == 'O' || A[rni][rnj] == '#') break;  //탈출 조건
					}
					
					if(A[rni][rnj] == '#') {
						rni -= dx[i];
						rnj -= dy[i];
					}
					
					//파란 공 이동 
					int bni = s.bi;   //파란 공의 다음 위치
					int bnj = s.bj;
					
					while(true) {
						bni += dx[i];
						bnj += dy[i];
						
						if(A[bni][bnj] == 'O' || A[bni][bnj] == '#') break;
					}
					
					if(A[bni][bnj] == '#') {
						bni -= dx[i];
						bnj -= dy[i];
					}
					
					//예외처리) 빨간 공과 파란 공이 같은 칸에 위치한 경우
					if(rni == bni && rnj == bnj && A[rni][rnj] != 'O') {
						//각 공의 이동 거리 계산
						int red_distance = Math.abs(rni - s.ri) + Math.abs(rnj - s.rj);
						int blue_distance = Math.abs(bni - s.bi) + Math.abs(bnj - s.bj);
						
						if(red_distance > blue_distance) {
							rni -= dx[i];
							rnj -= dy[i];
						}else {
							bni -= dx[i];
							bnj -= dy[i];
						}
					}
					
					//아직 방문하지 않았다면 queue에 넣기
					if(c[rni][rnj][bni][bnj] == 0) {
						c[rni][rnj][bni][bnj] = 1;
						q.offer(new Status(rni, rnj, bni, bnj, s.cnt+1));
					}
				}
				
			}
			System.out.println(-1);
		}catch(IOException e) {
			e.printStackTrace();
		}
	}

}

 

결과

 

백준 채점결과!