백준 13459번 : 구슬 탈출

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

13459번: 구슬 탈출

 

 

 

 

 

 

문제

• 게임의 목표는 빨간 구슬을 구멍을 통해서 빼내는 것이다. 이때, 파란 구슬이 구멍에 들어가면 안 된다.
• 보드에서 왼쪽으로 기울이기, 오른쪽으로 기울이기, 위쪽으로 기울이기, 아래쪽으로 기울이기와 같은 네 가지 동작이 가능
• 공은 동시에 움직인다. 빨간 구슬이 구멍에 빠지면 성공이지만, 파란 구슬이 구멍에 빠지면 실패이다. 빨간 구슬과 파란 구슬이 동시에 구멍에 빠져도 실패
• 빨간 구슬과 파란 구슬은 동시에 같은 칸에 있을 수 없다.

 

• 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)
• '.'은 빈 칸, '#'은 공이 이동할 수 없는 장애물 또는 벽, 'O'는 구멍의 위치, 'R'은 빨간 구슬의 위치, 'B'는 파란 구슬의 위치
• 보드의 가장자리에는 모두 '#', 구멍의 개수는 한 개, 빨간 구슬과 파란 구슬은 항상 1개
• 파란 구슬을 구멍에 넣지 않으면서 빨간 구슬을 10번 이하로 움직여서 빼낼 수 있으면 1을 없으면 0을 출력

 

 

 

 

 

풀이

각 칸이 있고, 왼쪽, 오른쪽, 위, 아래로 이동하는 네 가지 동작이 있고, 움직이는 횟수를 알아야 하므로 그래프 탐색 문제이다.  그리고 1회, 2회, 3회..10회 움직이기로 봐야하므로 BFS(너비우선탐색) 문제이다. 

 

 

기존의 BFS를 활용한 탐색 유형에서 심화된 풀이가 요구된다. '구슬이 동시에 움직인다는 것'과 '한 칸만 움직이는 것이 아니라 한 방향으로 계속 움직인다는 것', 성공과 실패 조건이 까다롭다는 거..

 

 

• 공이 동시에 움직인다고 하지만.. 파랑을 먼저 굴려야 한다!
  • 같은 칸에도 있을 수도 없고, 파란 구슬이 먼저 빠지거나, 두 구슬이 동시에 구멍에 들어가게 되면 실패기 때문이다. 그렇기 때문에 파랑 구슬을 굴리는 동안에 
    • 1) 빨강 구슬이 있는지 확인한다.
      • 앞에 빨강 구슬이 있다면, 먼저 굴리더라도 최종 위치는 빨강 구슬보다 한 칸 뒤가 되어야 한다.
    • 2) 구멍에 빠지는지 확인한다.
      • 하지만 빠진다고 게임을 종료시키면 안된다. 파란색 구슬이 먼저 빠져도, 다음 회에는 성공할 수도 있기 때문이다.

5 5
#####
#..R#
#.#.#
#BO.#
#####

(1회에서 오른쪽으로 기울인다면 파랑이 빠진다. 하지만 아래, 왼쪽 순으로 움직인다면 빨강 구슬을 넣는게 가능하다.)

 

 

 

 

• 종료 조건
  • 파랑 먼저 이동하고 빨강 구슬을 이동시킬 때, 빨강 구슬이 빠짐 -> 리턴 1
  • 이동 횟수가 10회가 넘음 -> 리턴 0
  • 큐에 들어간 원소가 없음 ex) 갇힌 경우 -> 리턴 0
  • 파랑 구슬이 먼저 빠짐 -> 바로 리턴을 줄 수 없다. 다음 탐색에서 찾을 수도 있기 때문에 그냥 넘긴다. 어차피 뒤에서 빨강을 못찾으면 이동 횟수가 10회 초과해 끝나게 되어있다.

 

 

 

 

• 큐 구현
  • 공은 동시에 움직이므로, 파랑 구슬과 빨강 구슬의 좌표를 Point라는 객체로 생성해 큐에 넣었다.
    • 구슬의 구분없이 통합해서 큐에 두 번 따로 넣을 수도 있지만, 구슬을 굴리게 될 때 2개씩 끊어서 빼주는 작업이 별도로 들어가서 한 번에 처리하는 게 더 편하겠다고 생각했다.
  • Point(bx, by, rx, ry)

 

 

• 방문 체크 배열
  
  • visited[bx][by][rx][ry] : 4차원의 배열로 표현해준다.
  • 파랑(1, 2)와 빨강(1, 1)을 이전에 방문하고, 다음에는 파랑(1, 2)와 빨강(3, 1)을 방문한다고 하자. 파랑이 이전에 (1, 2)을 방문했어도, 빨강의 좌표가 다르므로 다른 경우의 수로 봐야 한다.

 

 

• 횟수 계산
  • 큐에서 객체를 뽑아 사방탐색을 하기 전, 큐의 size를 계산해 그만큼만 탐색을 돌리도록 했다.
  • 횟수 계산을 객체에 따로 변수를 둬서 큐에 넣을 때마다 +1 해서 할 수도 있다.

 

 

 

 

몇 번의 실패 끝에 성공했다... 예제 입출력은 다 맞는데 채점만 돌리면 7%대 42%대에서 틀렸다. 질문 게시판에 있는 반례  다 맞는데도 틀린다고 하면 이동 횟수에서 틀렸을 가능성이 높다. 구슬탈출2(https://www.acmicpc.net/problem/13460)는 완전 같은 문제인데 출력이 0, 1이 아니라 최소 이동 횟수를 묻는다. 정답 부분을 1이 아니라 count로 바꿔서 예제를 돌려보니 내 코드에서 횟수 계산 부분이 잘못되었음을 알 수 있었다. 

 

 

 

 

 

코드

package algorithm;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class BOJ구슬탈출 {
	static int N, M;
	static char[][] board;
	static boolean[][][][] visited;
	static int[] dx = { -1, 1, 0, 0 };
	static int[] dy = { 0, 0, -1, 1 };

	static class Point {
		int bx, by, rx, ry; // 파랑 행렬 좌표, 빨강 행렬 좌표
		
		Point() {};

		Point(int bx, int by, int rx, int ry) {
			this.bx = bx;
			this.by = by;
			this.rx = rx;
			this.ry = ry;
		}
	}

	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());

		board = new char[N][M];

		Point start = new Point(); // 구슬의 시작 위치

		for (int i = 0; i < N; i++) {
			board[i] = br.readLine().toCharArray();

			// 구슬과 구멍의 위치 저장
			for (int j = 0; j < M; j++) {
				if (board[i][j] == 'R') {
					start.rx = i;
					start.ry = j;
				} else if (board[i][j] == 'B') {
					start.bx = i;
					start.by = j;
				}
			}
		}

		// 처리, 결과
		visited = new boolean[N][M][N][M]; // 파랑, 빨강

		System.out.println(bfs(start));
	}

	public static int bfs(Point start) {
		Queue<Point> queue = new LinkedList<>();

		queue.add(start);
		visited[start.bx][start.by][start.rx][start.ry] = true;

		int count = 0;
		while (!queue.isEmpty()) {
			count++;
			
			if (count > 10) { // 10회 넘으면 종료
				return 0;
			}
			
			int size = queue.size();
			for(int s = 0; s < size; s++) {
				Point point = queue.poll();
				
				for (int d = 0; d < 4; d++) {
					int nbx = point.bx;
					int nby = point.by;
					int nrx = point.rx;
					int nry = point.ry;

					// 파랑 이동
					boolean isFail = false; // 실패 여부
					boolean isRed = false; // 빨강을 만났는지
					while (board[nbx][nby] != '#') { // 벽에 닿기 전까지
						nbx += dx[d];
						nby += dy[d];

						if (board[nbx][nby] == 'O') { // 구멍에 빠짐
							isFail = true;
							break;
						} else if (nbx == nrx && nby == nry) { // 빨강 만났는지 학인
							isRed = true;
						}
					}
					nbx -= dx[d];
					nby -= dy[d];

					//파랑이 구멍에 빠졌으면 일단 넘김(다음 탐색에서 찾을 수도 있고, 어차피 뒤에서 빨강 못찾으면 중단됨)
					if (isFail) {
						continue;
					}

					if (isRed) { //빨강을 만난적이 있었으므로 한칸 뒤로
						nbx -= dx[d];
						nby -= dy[d];
					}

					// 빨강 이동
					while (board[nrx][nry] != '#') { // 벽 닿기 전까지
						nrx += dx[d];
						nry += dy[d];

						// 성공
						if (board[nrx][nry] == 'O') { // 빨강 구슬이 빠짐
							return 1;
						}
					}
					nrx -= dx[d];
					nry -= dy[d];
					
					if (nrx == nbx && nry == nby) { // 파랑 있으면 뒤로 미룸
						nrx -= dx[d];
						nry -= dy[d];
					}
					

					if (!visited[nbx][nby][nrx][nry]) { // 방문한적 없으면 이동
						queue.add(new Point(nbx, nby, nrx, nry));
						visited[nbx][nby][nrx][nry] = true;
					}
				}
			}
		}
		return 0;
	}

}

 

 

 

 

 

결과

 

 

 

 

 

배운점

• 조건에 맞게 꼼꼼하게 경우의 수를 나눠야 한다.
• 자잘한 실수를 줄이자..