[Baekjoon] 13459_구슬 탈출

Gold I

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

---

<구슬 탈출 >

 

문제 풀이

 

bfs를 활용하여 구슬을 상하좌우로 움직인다. 이동한 빨간 구슬과 파란 구슬이 같은 위치라면 위치 조정을 해준다. 

같은 위치가 아니라면 각 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 _13459_ {
	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 = 0;
		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=0;
						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=1;
								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==1)break;
			}
			if(result==1)break;
		}
	}
}

 

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

---

생각🤔

 

구슬 탈출 2 문제와 똑같이 풀려다가 시간을 줄이고 싶어서 다른 방향으로 풀었다. 그 결과 시간을 단축할 수 있었다.

 

---