[BOJ] 13460 구슬 탈출2 Java 풀이

 

 

 

하루종일 문제를 잡고 늘어지다가, 결국 다른 분의 풀이를 참조해 해결할 수 있었다.

 

참조 : https://ghkvud2.tistory.com/40

 

스스로 풀 때는 DFS로 먼저 접근했었는데, 문제에서 원하는 답은 최소 이동 횟수이기에 DFS로 구현하면 이를 찾기가 어려웠다. 예를 들면 다음과 같은 상황 때문이다. (ex) 예제입력 3 좌-좌-좌-좌-좌-좌-하-우-하-좌

 

물론 턴 수를 기반으로 작은 턴 수를 계속해서 업데이트시키는 방식으로 해결할 수는 있어 보였다. 실제로 다른 분들의 풀이 중 DFS로 해결한 풀이도 있었다. 하지만 이와 같은 최소 이동 개수를 카운트하는 문제에서는 BFS가 더욱 간편하기에 풀이를 변경했다.

 

최종 풀이 구성을 요약하면 다음과 같다.

 

 

• Node 클래스
  • int rRow, rCol, bRow, bCol : 각각 red, blue 구슬의 위치
  • int cnt : 몇 번 이동했는지 정보

 

• int bfs(Node ball) 메서드
  • 처음 입력정보를 바탕으로 Node를 받아, bfs 방식으로 조건을 만족시키는 최소이동횟수를 탐색한다.
  • Queue와 while문을 활용해 최대 10번까지 구슬을 굴려본다
  • Node의 정보를 토대로 visited를 확인하며 red, blue 각 구슬의 위치가 이전에 동일한 적이 있다면 다시 방문하지 않는다
  • blue 구슬이 구멍에 들어가면 실패
  • blue 구슬은 들어가지 않고 red 구슬만 들어가면 성공
  • 각각 구슬을 굴린 결과 구멍에 들어가지 않았는데, 서로 구슬의 위치가 같다면 위치를 조정

 

• int[] rollBlue(int bRow, int bCol, int dir) 메서드
  • blue 구슬을 굴리는 메서드

 

• int[] rollRed(int rRow, int rCol, int dir) 메서드
  • red 구슬을 굴리는 메서드

 

 

 

Red, Blue 구슬의 위치를 기준으로 방문한 적이 있는지를 확인하기 위해 boolean 배열 visited를 4차원으로 생성해 활용하는 기술이 시간복잡도를 줄이는데 큰 역할을 한다. 이런 방식으로 차원을 많이 높여 사용해본적이 없어 떠올리지 못했는데, 잘 기억해두면 유용하게 쓸 수 있겠다.

 

 

 

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 Main {
	static int N, M;
	static char[][] map;
	static boolean[][][][] visited;
	static int[] dirX = new int[] {0, 0, 1, -1};
	static int[] dirY = new int[] {1, -1, 0, 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 char[N][M];
		visited = new boolean[10][10][10][10];
		
		Node node = new Node();
		node.cnt = 0;
		
		// map 정보 입력
		for(int i = 0; i < N; i++) {
			String line = br.readLine();
			for(int j = 0; j < M; j++) {
				map[i][j] = line.charAt(j);
				if(map[i][j] == 'R') {
					node.rRow = i;
					node.rCol = j;
				}else if(map[i][j] == 'B') {
					node.bRow = i;
					node.bCol = j;
				}
			}
		}
		
		bfs(node);
	}
	
	public static void bfs(Node ball) {
		Queue<Node> q = new LinkedList<>();
		q.offer(ball);
		
		while(!q.isEmpty()) {
			Node node = q.poll();
			visited[node.rRow][node.rCol][node.bRow][node.bCol] = true;
			
			// 11번 이상 굴린 경우 -1을 출력(0부터 시작하기 때문에 10으로 설정)
			if(node.cnt >= 10) {
				System.out.println(-1);
				return;
			}
			
			// 현재 두 구슬의 위치를 기준으로 동, 서, 남, 북으로 굴려봄
			for(int dir = 0; dir < 4; dir++) {
				int[] bn = rollBlue(node.bRow, node.bCol, dir);
				int[] rn = rollRed(node.rRow, node.rCol, dir);
				
				if(map[bn[0]][bn[1]] == 'O')
					continue;
				if(map[rn[0]][rn[1]] == 'O') {
					System.out.println(node.cnt + 1);
					return;
				}
				// 두 구슬의 위치가 같다면, 위치를 조정한다.
				if(rn[0] == bn[0] && rn[1] == bn[1]) {
					if(dir == 0) {
						if(node.rCol > node.bCol) {
							bn[1] -= 1;
						}else {
							rn[1] -= 1;
						}
					}else if(dir == 1) {
						if(node.rCol > node.bCol) {
							rn[1] += 1;
						}else {
							bn[1] += 1;
						}
					}else if(dir == 2) {
						if(node.rRow > node.bRow) {
							bn[0] -= 1;
						}else {
							rn[0] -= 1;
						}
					}else if(dir == 3) {
						if(node.rRow > node.bRow) {
							rn[0] += 1;
						}else {
							bn[0] += 1;
						}
					}
				} // end of roll
				
				// 두 구슬을 굴린 후의 각각 위치가 처음 탐색하는 모양이면 큐에 넣음
				if(!visited[rn[0]][rn[1]][bn[0]][bn[1]]) {
					q.offer(new Node(rn[0], rn[1], bn[0], bn[1], node.cnt + 1));
				}
			} // end of for(동,서,남,북)
		} // end of while
		System.out.println(-1);
	}
	
	// 파란색 구슬을 굴린다
	public static int[] rollBlue(int bRow, int bCol, int dir) {
		int[] nxtB = new int[2];
		int bnRow = bRow;
		int bnCol = bCol;
		
		while(map[bnRow + dirX[dir]][bnCol + dirY[dir]] != '#') {
			bnRow += dirX[dir];
			bnCol += dirY[dir];
			if(map[bnRow][bnCol] == 'O') {
				break;
			}
		}
		nxtB[0] = bnRow;
		nxtB[1] = bnCol;
		return nxtB;
	}
	
	// 빨간색 구슬을 굴린다
	public static int[] rollRed(int rRow, int rCol, int dir) {
		int[] nxtR = new int[2];
		int rnRow = rRow;
		int rnCol = rCol;
		
		while(map[rnRow+dirX[dir]][rnCol + dirY[dir]] != '#') {
			rnRow += dirX[dir];
			rnCol += dirY[dir];
			if(map[rnRow][rnCol] == 'O') {
				break;
			}
		}
		nxtR[0] = rnRow;
		nxtR[1] = rnCol;
		return nxtR;
	}
}

class Node{
	int rRow; int rCol;
	int bRow; int bCol;
	int cnt;
	
	public Node(int rRow, int rCol, int bRow, int bCol, int cnt) {
		this.rRow = rRow;
		this.rCol = rCol;
		this.bRow = bRow;
		this.bCol = bCol;
		this.cnt = cnt;
	}

	public Node() {
	}
}