[Baekjoon] 13460_구슬 탈출 2

Gold I

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

---

<구슬 탈출 2>

 

문제 풀이

 

bfs를 활용하여 구슬을 상하좌우로 움직인다. 여기서 생각해야 하는 부분은 파란 구슬과 빨간 구슬의 위치를 고려해야 한다! 상하좌우로 움직일 때 어느 구슬이 앞에 있는지를 확인하며 구슬을 움직여준다. 또한, 파란 구슬이 구멍에 빠진 경우도 고려해주어야 한다. 

 

 - 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 _13460_ {
	static int dx[] = { -1, 1, 0, 0 };
	static int dy[] = { 0, 0, -1, 1 };
	static Queue<int[]> R, B;
	static char map[][];
	static int result = -1, x1, x2, y1, y2;
	static boolean flag, choice;

	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];

		R = new LinkedList<>();
		B = new LinkedList<>();

		for (int i = 0; i < n; i++) { // input
			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 });
				} else if (map[i][j] == 'B') {
					B.add(new int[] { i, j, 0 });
				}
			}
		}
		search();
		System.out.println(result);
	}

	private static void R_move(int temp, int dx, int dy) {
		while (true) {
			x1 += dx;
			y1 += dy;
			if (map[x1][y1] == '#' || (choice && x2 == x1+dx  && y2 == y1+dy  && map[x2][y2] != 'O')) {
				if(choice) {
					R.add(new int[] { x1 - dx, y1 - dy, temp });
					B.add(new int[] { x2 - dx, y2 - dy, temp });
				}
				break;
			} else if (map[x1][y1] == 'O') {
				result = temp;
				if(choice) flag=true;
				break;
			}
		}
	}

	private static void B_move(int temp, int dx, int dy) {
		while (true) {
			x2 += dx;
			y2 += dy;
			if (map[x2][y2] == '#' || (!choice && x1 == x2 + dx && y1 == y2 + dy && map[x1][y1] != 'O')) {
				if (!choice) {
					if (result != -1)
						break;
					R.add(new int[] { x1 - dx, y1 - dy, temp });
					B.add(new int[] { x2 - dx, y2 - dy, temp });
					break;
				}else if(map[x1][y1]=='O') {
					flag=true;
					break;
				}else {
					break;
				}
			} else if (map[x2][y2] == 'O') {
				if(choice) flag=true;
				result = -1;
				break;
			}
		}
	}

	private static void search() {

		while (!R.isEmpty()) {
			int r_temp[] = R.poll();
			int b_temp[] = B.poll();

			int temp = 0;
			flag = false; 

			for (int i = 0; i < 4; i++) {

				x1 = r_temp[0];
				y1 = r_temp[1];
				x2 = b_temp[0];
				y2 = b_temp[1];
				choice=false;
				
				temp = r_temp[2];
				temp += 1;
				if(temp>10) break;
				if (i == 0) { // up
					if (r_temp[1] == b_temp[1] && r_temp[0] > b_temp[0]) { // 파란 구슬이 더 위에 있다면
						choice=true;
						B_move(temp, dx[i], dy[i]);
						if(flag)continue;
						R_move(temp, dx[i], dy[i]);
					} else {
						R_move(temp, dx[i], dy[i]);
						B_move(temp, dx[i], dy[i]);
					}
				} else if (i == 1) { // down
					if (r_temp[1] == b_temp[1] && r_temp[0] < b_temp[0]) {
						choice=true;
						B_move(temp, dx[i], dy[i]);
						if(flag)continue;
						R_move(temp, dx[i], dy[i]);
					} else {
						R_move(temp, dx[i], dy[i]);
						B_move(temp, dx[i], dy[i]);
					}
				} else if (i == 2) { // left
					if (r_temp[0] == b_temp[0] && r_temp[1] > b_temp[1]) {
						choice=true;
						B_move(temp, dx[i], dy[i]);
						if(flag)continue;
						R_move(temp, dx[i], dy[i]);
					} else {
						R_move(temp, dx[i], dy[i]);
						B_move(temp, dx[i], dy[i]);
					}
				} else { // right
					if (r_temp[0] == b_temp[0] && r_temp[1] < b_temp[1]) {
						choice=true;
						B_move(temp, dx[i], dy[i]);
						if(flag)continue;
						R_move(temp, dx[i], dy[i]);
					} else {
						R_move(temp, dx[i], dy[i]);
						B_move(temp, dx[i], dy[i]);
					}
				}
				if(result!=-1)break;
			}
			if(result!=-1)break;
		}
	}
}

 

•  Main
  • 보드(map)의 세로, 가로 크기 n, m 및 보드(map) 입력
  • Queue R과 B는 빨간 구슬과 파란 구슬을 저장한다. [x좌표, y좌표, count]
  • search() : bfs 탐색
  •  
• R_move(count, 상하좌우 이동 중 하나)
  • x좌표와 y좌표를 상하좌우 중 하나로 무한 이동
    • 이동할 좌표가 구슬이 이동할 수 없는 위치이지만 빨간 구슬이 먼저 움직인 것이라면 그대로 반복문 탈출
    • 파란 구슬이 먼저 움직였으며, 빨간 구슬이 다음에 이동할 위치와 좌표가 같다면 R, B에 저장 및 탈출
    • 만약 빨간 구슬이 구멍에 들어갔다면 result에 count를 저장 및  탈출 but 파란 구슬이 먼저 움직였다면 flag를 true로 설정  
• B_move(count, 상하좌우 이동 중 하나)
  • x좌표와 y좌표를 상하좌우 중 하나로 무한 이동
    • if
      • 이동할 좌표가 구슬이 이동할 수 없는 위치이지만 파란 구슬이 먼저 움직인 것이라면 그대로 반복문 탈출
      • 빨간 구슬이 먼저 움직였으며, 파란 구슬이 다음에 이동할 위치와 좌표가 같다면 R, B에 저장 및 탈출
      • 빨간 구슬이 먼저 이동 후 파란 구슬이 이동할 좌표가 구슬이 이동할 수 없는 위치이지만 빨간 구슬은 이미 구멍에 들어갔다면 flag를 true로 바꾼 후 탈출
      • 그 외에는 그냥 탈출
    • else if
      • 파란 구슬이 구멍에 떨어져 버렸는데 파란 구슬이 먼저 움직인 거라면 flag를 true로 바꿈. 파란 구슬은 같이 떨어지면 안 되므로 resut를 -1로 바꾸고 탈출
• search()
  • 빨간 구슬과 파란 구슬을 queue에서 빼내 옴
  • 상하좌우 반복
    • 먼저 구슬의 위치와 count를 저장해줌
    • 10번 이하로 움직여서 빨간 구슬을 빼낼 수 없다면 탈출
    • 각각 상하좌우로 움직일 때 어느 구슬이 먼저 움직여야 하는지 판단 후 각각 구슬 움직이는 함수 호출
    • choice: 파란 구슬을 먼저 움직일 경우 true로 저장
    • flag: 파란 구슬이 구멍에 빠진 경우 true로 저장
  • 최소 횟수를 출력하는 것이므로 result가 -1이 아니면 (초기값이 아니면) 탈출 후 출력

 

 

+ 시간 단축 코드

   (설명은 https://melody-coding.tistory.com/267 참고 )

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 _13460_ {
	static char map[][];
	static Queue<int[]> R, B;
	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<>();
		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 });
				else if (map[i][j] == 'B')
					B.add(new int[] { i, j, 0 });
			}
		}
		search();
		System.out.println(result);
	}

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

		while (!R.isEmpty()) {
			int[] R_temp = R.poll();
			int[] B_temp = B.poll();
			int x1, y1, x2, y2;
			for (int i = 0; i < 4; i++) {
				int temp = R_temp[2] + 1;
				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 });
						}
						break;
					}
				}
				if (result > 0)
					break;
			}
			if (result > 0)
				break;
		}
	}
}

---

생각🤔

 

이 문제... 성공 못할 뻔했다.. 포기할 뻔했다..!

처음에 틀렸을 때는 파란 공이 먼저 움직이는 경우를 고려하지 못했기 때문이다. 그래서 일단 포기하고 다음 날 다시 도전했다. 하지만 계속해서 틀렸습니다가 떴고... 반례를 찾아.. 떠났다..  왜 난 반례를 찾아내지 못하는가..

힘들게 힘들게 찾아서.. 겨우 통과했다. 겨우 통과한 만큼 시간은 엄청났고... 일단 오늘은 여기서 만족(?)해야겠다.

 

 

+ 13459번 구슬 탈출을 풀며 시간을 단축할 수 있었다.

---