[Baekjoon] 15644_구슬 탈출 3

Gold I

문제(출처: https://www.acmicpc.net/problem/15644)

---

<구슬 탈출 3 >

 

문제 풀이

 

구슬 탈출 2 (https://melody-coding.tistory.com/266)에서 추가로 어떻게 기울여야 하는지를 구해준다.

기울기를 저장하기 위해 String을 저장하는 queue를 추가로 선언해 준다.

 

 - my solution (Java)

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

public class _15644_ {

	static char map[][];
	static Queue<int[]> R, B;
	static Queue<String> cmd;
	static String cmdresult;
	static int result;
	static int dx[] = { -1, 1, 0, 0 };
	static int dy[] = { 0, 0, -1, 1 };

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());

		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

		map = new char[n][m];
		result = -1;
		R = new LinkedList<>();
		B = new LinkedList<>();
		cmd=new LinkedList<>();
		for (int i = 0; i < n; i++) {
			String s = bf.readLine();
			for (int j = 0; j < m; j++) {
				map[i][j] = s.charAt(j);
				if (map[i][j] == 'R') {
					R.add(new int[] { i, j, 0 });
					cmd.add("");
				}
				else if (map[i][j] == 'B')
					B.add(new int[] { i, j, 0 });
			}
		}
		search();
		System.out.println(result);
		if(result!=-1)System.out.println(cmdresult);
	}

	private static void search() {
		boolean check = false;

		while (!R.isEmpty()) {
			int[] R_temp = R.poll();
			int[] B_temp = B.poll();
			String a=cmd.poll();
			int x1, y1, x2, y2;
			for (int i = 0; i < 4; i++) {
				cmdresult=a;
				int temp = R_temp[2] + 1;
				if(i==0)cmdresult+="U";
				else if(i==1) cmdresult+="D";
				else if(i==2) cmdresult+="L";
				else cmdresult+="R";
				if (temp > 10)
					break; // 10번 이하가 아니면 x
				x1 = R_temp[0];
				y1 = R_temp[1];
				check = false;
				while (true) { // 빨간 구슬
					x1 += dx[i];
					y1 += dy[i];

					if (map[x1][y1] == '#') {
						break;
					}
					if (map[x1][y1] == 'O') { // 구멍
						check = true;
						break;
					}
				}
				x2 = B_temp[0];
				y2 = B_temp[1];
				while (true) { // 파란 구슬
					x2 += dx[i];
					y2 += dy[i];
					if (map[x2][y2] == 'O') { // 파란구슬이  구멍에 빠지면 실패
						result = -1;
						break;
					}
					if (map[x2][y2] == '#') {
						if (x1 == x2 && y1 == y2) { // 빨간 구슬과 파란 구슬 좌표가 같으면 위치 조정
							if (i == 0) {
								if (B_temp[0] < R_temp[0]) {
									x2 -= dx[i];
									x1 = x2 - dx[i];
								} else {
									x1 -= dx[i];
									x2 = x1 - dx[i];
								}
							} else if (i == 1) {
								if (B_temp[0] < R_temp[0]) {
									x1 -= dx[i];
									x2 = x1 - dx[i];
								} else {
									x2 -= dx[i];
									x1 = x2 - dx[i];
								}
							} else if (i == 2) {
								if (B_temp[1] < R_temp[1]) {
									y2 -= dy[i];
									y1 = y2 - dy[i];
								} else {
									y1 -= dy[i];
									y2 = y1 - dy[i];
								}
							} else {
								if (B_temp[1] < R_temp[1]) {
									y1 -= dy[i];
									y2 = y1 - dy[i];
								} else {
									y2 -= dy[i];
									y1 = y2 - dy[i];
								}
							}
						} else {
							x1 -= dx[i];
							y1 -= dy[i];
							x2 -= dx[i];
							y2 -= dy[i];
							if (check) { // 최소 횟수
								result = temp;
								break;
							}
						}
						if (!(R_temp[0] == x1 && R_temp[1] == y1 && B_temp[0] == x2 && B_temp[1] == y2)) { // 원래 위치와 동일하지 않으면 
							R.add(new int[] { x1, y1, temp });
							B.add(new int[] { x2, y2, temp });
							cmd.add(cmdresult);
						}
						break;
					}
				}
				if (result > 0)
					break;
			}
			if (result > 0)
				break;
		}
	}
}

 

• 변수 설명
  • map: 보드 
  • R, B: 각각 빨간 구슬, 파란 구슬의 [x 좌표, y 좌표, count]
  • result: 최소 횟수
  • check: 빨간 구슬이 구멍에 들어간 여부 확인
  • cmd: 기울기를 저장하는 queue
  • cmdresult: 기울기
• main
  • 보드 입력 후 빨간 구슬과 파란 구슬의 위치를 각 queue에 저장
  • search 함수 호출
  • result 출력
• search
  • 빨간 구슬 queue가 빌 때까지 반복
  • 기울기를 저장해둔 queue인 cmd에서 하나 뽑은 후 상하좌우 경우에 맞게 기울기 추가
  • 각각 구슬 queue에서 하나씩 뽑은 후 상하좌우 이동
    • 빨간 구슬을 움직이며 더 이상 이동할 수 없는 위치라면 탈출
    • 구멍에 빠졌다면 check를 true로 바꾼 후 탈출
    • 파란 구슬을 움직이며 구멍에 빠졌다면 result를 0으로 바꾼 후 탈출
    • 파란 구슬이 더 이상 이동할 수 없는 위치이고 빨간 구슬과 파란 구슬 좌표가 같다면 각각 위치 조정(예를 들어 위로 움직인 경우 파란 구슬이 더 위에 있다면 파란 구슬보다 빨간 구슬이 한 칸 더 밑에 있도록 조정) but 빨간 구슬과 파란 구슬 좌표가 같지 않다면 빨간 구슬이 구멍에 빠진 지 확인 후 빠졌으면 탈출! 구멍에 빠지지 않았다면 이동하기 전 위치와 비교해서 같지 않은 경우에만 queue에 저장 및 기울기 queue에 저장

---

생각🤔

 

구슬 문제 2에서 기울기 구하는 것만 추가했더니 쉽게 통과할 수 있었다.

 

---