[골드1] 13460. 구슬 탈출 2(Java)

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

13460번: 구슬 탈출 2

싸피 탈출,,?

---

※  문제를 요약하면 아래와 같습니다.

▶ 세로 N, 가로 M 크기의 보드에 빨간 구슬, 파란 구슬, 구멍, 벽이 존재

▶ 구슬의 이동을 위해서는 보드를 왼쪽, 오른쪽, 위쪽, 아래쪽으로 기울여 움직여야함. 

▶ 한 번 기울일 때는 해당 방향으로 더 이상 구슬이 움직이지 않을 때 까지 동작

▶ 빨간 구슬이 구멍을 통과하면 성공, 파란 구슬이 구멍으로 들어가면 무조건 실패

▶ 10회 미만으로 기울기 방향을 바꿀 때, 최소 몇 번만에 성공 가능한지 출력

▶ Input : 첫째 줄에 세로 크기 N과 가로 크기 M이 입력, 이후 N 줄에 보드의 정보 입력

▶ Output : 최소 몇 번만에 빨간 구슬이 구멍을 통해 빠져나올 수 있는 지 출력, 10번 이상시 -1 출력

---

◈ Input - 1

5 5
#####
#..B#
#.#.#
#RO.#
#####

◈ Output - 1

1

◈ Input - 2

7 7
#######
#...RB#
#.#####
#.....#
#####.#
#O....#
#######

◈ Output - 2

5

◈ Input - 3

7 7
#######
#..R#B#
#.#####
#.....#
#####.#
#O....#
#######

◈ Output - 3

5

◈ Input - 4

10 10
##########
#R#...##B#
#...#.##.#
#####.##.#
#......#.#
#.######.#
#.#....#.#
#.#.#.#..#
#...#.O#.#
##########

◈ Output - 4

-1

◈ Input - 5

3 7
#######
#R.O.B#
#######

◈ Output - 5

1

◈ Input - 6

10 10
##########
#R#...##B#
#...#.##.#
#####.##.#
#......#.#
#.######.#
#.#....#.#
#.#.##...#
#O..#....#
##########

◈ Output - 6

7

---

 ◎  코드 작성 전, 아래와 같이 솔루션을 정리하였습니다.

▶ 보드의 정보를 int 형 2차원 배열로 저장

▶ BFS 활용,  빨간 구슬이 구멍에 도달하는 최소 경우의 수 탐색

▶ BFS 중, 빨간 구슬과 파란 구슬을 동시에 움직이기 위해 Point 클래스의 두 구슬의 좌표 및 기울인 횟수 저장

▶ 델타 탐색 활용, 각 방향에서 빨간 구슬과 파란 구슬이 벽이나 홀에 도착할 때 까지 해당 방향 탐색

▶ 빨간 구슬과 파란 구슬이 기울인 후의 움직임이 끝난 좌표로 방문 처리 진행 ( 4차원 배열 방문처리 진행 )

▶ 두 구슬이 동일한 위치에 있을 경우, 빨간 구슬과 파란 구슬의 위치를 비교하여 먼저 굴러간 구슬을 탐색 

     나중에 굴러간 구슬을 반대방향으로 한 칸 다시 이동

    ex ) 아래와 같이 파란 구슬이 각 방향에서 빨간 구슬 진로 앞에 있을 때, 구슬을 기울일 경우 파란 구슬 먼저 도착

           이에 따라 나중에 굴러온 구슬을 해당 반대 방향으로 한 칸 후퇴  ( 코드 내 bRedFirst 활용 참조 )

▶ 파란 구슬이 구멍에 도달 했을 경우 무조건 실패 => 다음 BFS 탐색

▶ 10회 이내에서 빨간 구슬만 구멍에 도달 했을 경우 기울인 횟수 출력, 탐색 실패시 -1 출력

---

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Point {
	int m_nRedRow;
	int m_nRedCol;
	int m_nBlueRow;
	int m_nBlueCol;
	int m_nCount;

	public Point() {
		// TODO Auto-generated constructor stub
	}

	public Point(int m_nRedRow, int m_nRedCol, int m_nBlueRow, int m_nBlueCol, int m_nCount) {
		super();
		this.m_nRedRow = m_nRedRow;
		this.m_nRedCol = m_nRedCol;
		this.m_nBlueRow = m_nBlueRow;
		this.m_nBlueCol = m_nBlueCol;
		this.m_nCount = m_nCount;
	}

	@Override
	public String toString() {
		return "Point [m_nRedRow=" + m_nRedRow + ", m_nRedCol=" + m_nRedCol + ", m_nBlueRow=" + m_nBlueRow
				+ ", m_nBlueCol=" + m_nBlueCol + ", m_nCount=" + m_nCount + "]";
	}
}

public class Main {

	static int N, M;
	static boolean[][][][] barrVisit;
	static int[][] narrMap;

	static int[] dr = { 0, 0, 1, -1 };
	static int[] dc = { 1, -1, 0, 0 };

	static final int WALL = 0;
	static final int EMPTY = 1;
	static final int RED = 2;
	static final int BLUE = 3;
	static final int HOLE = 4;

	public static void main(String[] args) throws IOException {
		BufferedReader bReader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bWriter = new BufferedWriter(new OutputStreamWriter(System.out));

		StringTokenizer st = new StringTokenizer(bReader.readLine());

		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		// 방문 체크
		barrVisit = new boolean[N][M][N][M];
		// 보드값 입력받자
		// # : 0
		// . : 1
		// R : 2
		// B : 3
		// O : 4
		Point pMarble = new Point();
		narrMap = new int[N][M];
		for (int i = 0; i < N; i++) {
			String strTemp = bReader.readLine();
			// 맵의 정보 입력
			for (int j = 0; j < M; j++) {
				if (strTemp.charAt(j) == '.') {
					narrMap[i][j] = EMPTY;
				} else if (strTemp.charAt(j) == 'R') {
					pMarble.m_nRedRow = i;
					pMarble.m_nRedCol = j;
					narrMap[i][j] = RED;
				} else if (strTemp.charAt(j) == 'B') {
					pMarble.m_nBlueRow = i;
					pMarble.m_nBlueCol = j;
					narrMap[i][j] = BLUE;
				} else if (strTemp.charAt(j) == 'O') {
					narrMap[i][j] = HOLE;
				}

			}
		}
		barrVisit[pMarble.m_nRedRow][pMarble.m_nRedCol][pMarble.m_nBlueRow][pMarble.m_nBlueCol] = true;
		int nResult = marble(pMarble);

		bWriter.write(String.valueOf(nResult));
		bWriter.close();
	}

	private static int marble(Point pStart) {
		Queue<Point> queueBFS = new LinkedList<>();
		queueBFS.add(pStart);

		while (!queueBFS.isEmpty()) {
			Point pBFS = queueBFS.poll();
			// 10회가 넘어가면 멈춰
			if (pBFS.m_nCount >= 10)
				break;
//			System.out.println(pBFS);
//			System.out.println("==============");
			for (int i = 0; i < dr.length; i++) {
				boolean bRedFirst = true;
				// blue랑 red 중 뭐가 먼저굴러갈까유
				if (i == 0 && pBFS.m_nRedCol < pBFS.m_nBlueCol)
					bRedFirst = false;
				if (i == 1 && pBFS.m_nRedCol > pBFS.m_nBlueCol)
					bRedFirst = false;
				if (i == 2 && pBFS.m_nRedRow < pBFS.m_nBlueRow)
					bRedFirst = false;
				if (i == 3 && pBFS.m_nRedRow > pBFS.m_nBlueRow)
					bRedFirst = false;

				// 구슬을 델타 방향으로 굴려보자
				Point pTemp = Rolling(pBFS, i, bRedFirst);
				
				// 파랑 구슬이 들어왔다??? 이 케이스는 넘어가자
				if(narrMap[pTemp.m_nBlueRow][pTemp.m_nBlueCol] == HOLE) {
					continue;
				}
				// 빨강 구슬이 들어왔다 ??? 성공해부려따
				if(narrMap[pTemp.m_nRedRow][pTemp.m_nRedCol] == HOLE) {
					return pTemp.m_nCount;
				}
				
				// 이미 방문했던 곳이면 돌아가자
				if(barrVisit[pTemp.m_nRedRow][pTemp.m_nRedCol][pTemp.m_nBlueRow][pTemp.m_nBlueCol])
					continue;

				barrVisit[pTemp.m_nRedRow][pTemp.m_nRedCol][pTemp.m_nBlueRow][pTemp.m_nBlueCol] = true;
				
//				System.out.println(pTemp);
//				System.out.println("==============End");
				queueBFS.add(pTemp);
			}

		}

		// 경우의 수가 읎다
		return -1;
	}

	// 구슬을 굴려볼까유
	private static Point Rolling(Point pTemp, int nDirection, boolean bRedFirst) {
		//
		int[] narrMarble = new int[4];

		narrMarble[0] = pTemp.m_nRedRow;
		narrMarble[1] = pTemp.m_nRedCol;
		narrMarble[2] = pTemp.m_nBlueRow;
		narrMarble[3] = pTemp.m_nBlueCol;

		int nCount = pTemp.m_nCount;

		// 구슬을 굴리자
		
		for (int i = 0; i < 4; i += 2) {
			// 빨강 갯수만 필요
			// 인덱스 체크 범위 불필요~ 가장자리는 어차피 벽이다
			while (narrMap[narrMarble[i]][narrMarble[i + 1]] != HOLE
					&& narrMap[narrMarble[i] + dr[nDirection]][narrMarble[i + 1] + dc[nDirection]] != WALL) {
				narrMarble[i] += dr[nDirection];
				narrMarble[i + 1] += dc[nDirection];
			}
		}

		// 구슬의 위치기 같다면 ???
		// 둘다 홀이면 그냥 보내
		if (narrMarble[0] == narrMarble[2] && narrMarble[1] == narrMarble[3]
				&& narrMap[narrMarble[0]][narrMarble[1]] != HOLE) {
			if (bRedFirst) {
				// 빨강 구슬부터 굴렸다
				// 파랑 구슬을 방향의 반대쪽으로 한칸 보내자
				narrMarble[2] -= dr[nDirection];
				narrMarble[3] -= dc[nDirection];
				
			} else {
				// 파랑 구슬부터 굴렸다
				// 빨강 구슬을 방향의 반대쪽으로 한칸 보내자
				narrMarble[0] -= dr[nDirection];
				narrMarble[1] -= dc[nDirection];
			}
		}
		
		return (new Point(narrMarble[0], narrMarble[1], narrMarble[2], narrMarble[3], pTemp.m_nCount+1 ));
	}
}

---

Good Luck! (피드백 감사합니다!)