[백준] 13459 / 13460 / 15653. 구슬 탈출(골드1) - BFS

Kiefer Sol·2024년 8월 10일
알고리즘

알고리즘

목록 보기
26/35

13459. 구슬 탈출 (골드1) - 횟수 10회이하, 성공유무

시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초512 MB122504276311834.998%

13460. 구슬 탈출 2 (골드1) - 횟수 10회이하, 최소 횟수

시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초512 MB95026289131663328.092%

15653. 구슬 탈출 4 (골드1) - 횟수제한 x, 최소 횟수

시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초512 MB46032088164448.126%


문제

스타트링크에서 판매하는 어린이용 장난감 중에서 가장 인기가 많은 제품은 구슬 탈출이다. 구슬 탈출은 직사각형 보드에 빨간 구슬과 파란 구슬을 하나씩 넣은 다음, 빨간 구슬을 구멍을 통해 빼내는 게임이다.

보드의 세로 크기는 N, 가로 크기는 M이고, 편의상 1×1크기의 칸으로 나누어져 있다. 가장 바깥 행과 열은 모두 막혀져 있고, 보드에는 구멍이 하나 있다. 빨간 구슬과 파란 구슬의 크기는 보드에서 1×1크기의 칸을 가득 채우는 사이즈이고, 각각 하나씩 들어가 있다. 게임의 목표는 빨간 구슬을 구멍을 통해서 빼내는 것이다. 이때, 파란 구슬이 구멍에 들어가면 안 된다.

이때, 구슬을 손으로 건드릴 수는 없고, 중력을 이용해서 이리 저리 굴려야 한다. 왼쪽으로 기울이기, 오른쪽으로 기울이기, 위쪽으로 기울이기, 아래쪽으로 기울이기와 같은 네 가지 동작이 가능하다.

각각의 동작에서 공은 동시에 움직인다. 빨간 구슬이 구멍에 빠지면 성공이지만, 파란 구슬이 구멍에 빠지면 실패이다. 빨간 구슬과 파란 구슬이 동시에 구멍에 빠져도 실패이다. 빨간 구슬과 파란 구슬은 동시에 같은 칸에 있을 수 없다. 또, 빨간 구슬과 파란 구슬의 크기는 한 칸을 모두 차지한다. 기울이는 동작을 그만하는 것은 더 이상 구슬이 움직이지 않을 때 까지이다.

13459) 보드의 상태가 주어졌을 때, 10번 이하로 빨간 구슬을 구멍을 통해 빼낼 수 있는지 구하는 프로그램을 작성하시오.

13460) 보드의 상태가 주어졌을 때, 10번 이하로 빨간 구슬을 구멍을 통해 빼낼 수 있는지 구하는 프로그램을 작성하시오.

15653) 보드의 상태가 주어졌을 때, 최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' 로 이루어져 있다. '.'은 빈 칸을 의미하고, '#'은 공이 이동할 수 없는 장애물 또는 벽을 의미하며, 'O'는 구멍의 위치를 의미한다. 'R'은 빨간 구슬의 위치, 'B'는 파란 구슬의 위치이다.

입력되는 모든 보드의 가장자리에는 모두 '#'이 있다. 구멍의 개수는 한 개 이며, 빨간 구슬과 파란 구슬은 항상 1개가 주어진다.

출력

13459) 파란 구슬을 구멍에 넣지 않으면서 빨간 구슬을 10번 이하로 움직여서 빼낼 수 있으면 1을 없으면 0을 출력한다.
13460) 최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 출력한다. 만약, 10번 이하로 움직여서 빨간 구슬을 구멍을 통해 빼낼 수 없으면 -1을 출력한다.
15653) 최소 몇 번 만에 빨간 구슬을 구멍을 통해 빼낼 수 있는지 출력한다. 만약, 어떻게 움직여도 빨간 구슬을 구멍을 통해 빼낼 수 없으면 -1을 출력한다.

13459. 예제 입력 1
7 7
#######
#..R#B#
#.#####
#.....#
#####.#
#O....#
#######

13459. 예제 출력 1
1

13459. 예제 입력 2
10 10
##########
#R#...##B#
#...#.##.#
#####.##.#
#......#.#
#.######.#
#.#....#.#
#.#.#.#..#
#...#.O#.#
##########

13459. 예제 출력 2
0

13460/15653. 예제 입력 1
10 10
##########
#R#...##B#
#...#.##.#
#####.##.#
#......#.#
#.######.#
#.#....#.#
#.#.##...#
#O..#....#
##########

13460/15653. 예제 출력 1
7

13460/15653. 예제 입력 2
3 10
##########
#.O....RB#
##########

13460/15653. 예제 출력 2
-1

풀이

  1. 좌표이동 배열, Point 클래스 (빨간공과 파란공의 x,y축) 마련
  2. 배열 입력받을 때 빨간공, 파란공의 시작위치 확인해서 BFS 메소드에 매개변수로 전달
  3. 빨간공과 파란공의 시작위치를 큐에 넣고, 시작위치를 방문배열에 체크
  4. 시도횟수 만큼 반복문 돌기 / 시작점 마다 반복문 돌기 (que.size) / 시작점에서 방향 확인해 다음 위치 파악하기 => 3중 반복문
  5. 방향에 따라 빨간공과 파란공의 어떤게 앞서서 이동하나 확인하고 함수 호출
    5.1. 같은 y축에 있고 && (방향이 북쪽이고 파란공이 더 위쪽에 있을 때 || 방향이 남쪽에 있고 파란공에 더 아래쪽에 있을 때) => 파란색 공이 더 앞서서 이동
    5.2. 같은 y축에 있고 && (방향이 북쪽이고 빨간공이 더 위쪽에 있을 때 || 방향이 남쪽에 있고 빨간공에 더 아래쪽에 있을 때) => 빨간색 공이 더 앞서서 이동
    5.3. 같은 x축에 있고 && (방향이 서쪽이고 파란공이 더 왼쪽에 있을 때 || 방향이 동쪽에 있고 파란공에 더 오른쪽에 있을 때) => 파란색 공이 더 앞서서 이동
    5.4. 같은 x축에 있고 && (방향이 서쪽이고 빨간공이 더 왼쪽에 있을 때 || 방향이 동쪽에 있고 빨간공이 더 오른쪽에 있을 때) => 빨간공이 더 앞서서 이동
    5.5. 둘이 x축 y축 서로 다르면 어떤 공이 먼저 움직이든 상관없다. (방향이 북,남이면 y축 고정, x축 이동 / 방향이 서,동이면 x축 고정, y축 이동)
  6. 빨간공, 파란공이 이동함수를 호출 후
    6.1. 방문했거나, 파란공이 먼저 빠지면 넘어감
    6.2. 빨간공이 빠지면 최소횟수 계산 후 리턴
    6.3. 위의 조건아니면 다음 점을 큐에 넣고, 방문배열 체크
  7. 시도횟수 증가
  8. 이동함수는 방향을 매개변수로 받아 방향배열을 사용하여 지정된 방향으로 이동
    8.1. 벽이 아닐 때까지 이동하고 구멍에 빠지면 현재 시점 리턴
    8.2. 벽에 도달하거나 다른 공과 만나면 현재 시점보다 하나 후퇴한 점 리턴

코드

13459 기준으로 코드를 작성하고 13460과 15653은 주석으로 적어놓았다.

import java.io.*;
import java.util.*;

public class Main {
	public static int N, M;
	public static char[][] arr;
    /*
     최솟값을 찾기위해 초기값은 가장 큰 값으로 지정- 13460, 15653
     public static int answer = Integer.MAX_VALUE; 
    */
    
	// 북(0), 남(1), 서(2), 동(3) 
	public static int[] dx = { -1, 1, 0, 0 };
	public static int[] dy = { 0, 0, -1, 1 };

	public static class Point { //빨간공, 파란공 위치
		int red_x;
		int red_y;
		int blue_x;
		int blue_y;

		public Point(int red_x, int red_y, int blue_x, int blue_y) {
			this.red_x = red_x;
			this.red_y = red_y;
			this.blue_x = blue_x;
			this.blue_y = blue_y;
		}
	}

	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());
		arr = new char[N][M];
		
        // 빨간, 파란공 시작 위치 저장
		int redR = 0;
		int redC = 0;
		int blueR = 0;
		int blueC = 0;
		
        // 입력받으면서 빨간공과 파란공의 시작 위치 파악
		for (int r = 0; r < N; r++) {
			String input = br.readLine();
			for (int c = 0; c < M; c++) {
				arr[r][c] = input.charAt(c);
				if (arr[r][c] == 'R') {
					redR = r;
					redC = c;
				} else if (arr[r][c] == 'B') {
					blueR = r;
					blueC = c;
				}
			}

		}

		BFS(redR, redC, blueR, blueC);
        System.out.println(answer); // 최소시도횟수 출력 - 13460, 15653
	}

	public static void BFS(int rx, int ry, int bx, int by) {
		Queue<Point> queue = new LinkedList<>();
        //공의 시작위치 받아서 큐에 넣기
		queue.offer(new Point(rx, ry, bx, by));
		boolean[][][][] visited = new boolean[N][M][N][M]; // 방문 4차원 배열
		visited[rx][ry][bx][by] = true; // 시작위치 방문
		int cnt = 1; // 처음시도 ( cnt=0을 하려면 밑에 반복문에서 cnt<10해야함)

		while (!queue.isEmpty() && cnt <= 10) { // 10의 시도
        // while (!queue.isEmpty()) { //15653. 횟수제한 없음
        
			int size = queue.size();
            
			// 다른 시작점의 경우의 수를 모두 검사
			for (int s = 0; s < size; s++) {
				Point current = queue.poll();
				// System.out.println("현재 위치 : "+current.red_x+" "+current.red_y+" "+current.blue_x+" "+current.blue_y);

				for (int d = 0; d < 4; d++) {
                	// 다음 공의 위치
					int nrx = current.red_x;
					int nry = current.red_y;
					int nbx = current.blue_x;
					int nby = current.blue_y;

					/*
					boolean redfirst = false;
					if(d==0 && nrx < nbx) redfirst = true; //북
					if(d==1 && nrx > nbx) redfirst = true; //남
					if(d==2 && nry < nby) redfirst = true; //서
					if(d==3 && nry > nby) redfirst = true; //동
					=> 사용안하는 이유: 위에서 하나를 만족해서 redfirst가 true됬다고 해서 밑에서 방향과 좌표가 맞다고 단정할 수 없음 
					 */
					
                    // 빨간광과 파란공의 이동방향에 따라 선후관계 파악하기
					if (nby == nry && ((d == 0 && nbx < nrx) || (d == 1 && nbx > nrx))) {
                    // 같은 y축에 있고  && (방향이 북쪽이고 파란공이 더 위쪽에 있을 때 || 방향이 남쪽에 있고 파란공에 더 아래쪽에 있을 때)
                    // 파란색 공이 더 앞서서 이동
						nbx = slideX(nbx, nby, nrx, nry, d);
						nrx = slideX(nrx, nry, nbx, nby, d);
					} else if (nby == nry && (((d == 0 && nbx > nrx) || d == 1 && nbx < nrx))) {
                    // 같은 y축에 있고  && (방향이 북쪽이고 빨간공이 더 위쪽에 있을 때 || 방향이 남쪽에 있고 빨간공에 더 아래쪽에 있을 때)
                    // 빨간색 공이 더 앞서서 이동
						nrx = slideX(nrx, nry, nbx, nby, d);
						nbx = slideX(nbx, nby, nrx, nry, d);
					} else if (nbx == nrx && ((d == 2 && nby < nry) || (d == 3 && nby > nry))) {
                    // 같은 x축에 있고  && (방향이 서쪽이고 파란공이 더 왼쪽에 있을 때 || 방향이 동쪽에 있고 파란공에 더 오른쪽에 있을 때)
                    // 파란색 공이 더 앞서서 이동
						nby = slideY(nbx, nby, nrx, nry, d);
						nry = slideY(nrx, nry, nbx, nby, d);
					} else if (nbx == nrx && ((d == 2 && nby > nry) || (d == 3 && nby < nry))) {
                     // 같은 x축에 있고  && (방향이 서쪽이고 빨간공이 더 왼쪽에 있을 때 || 방향이 동쪽에 있고 빨간공이 더 오른쪽에 있을 때)
                    // 빨간공이 더 앞서서 이동
						nry = slideY(nrx, nry, nbx, nby, d);
						nby = slideY(nbx, nby, nrx, nry, d);

					} else {
                    	// 둘이 x축 y축 서로 다르면 어떤 공이 먼저 움직이든 상관없다.
                        /*
						 위에 조건문을 nbx == nrx 와 nby == nry로 먼저 묶지 않는 이유는 else문 처리 때문이다.
						 &&문 만족하지 않으면 다 else로 넘어온다. => &&로 묶으면 else로 넘어오는 케이스가 많아진다.
                         */
						if (d == 0 || d == 1) { 
                        	// 방향이 북,남이면 y축 고정, x축 이동
							nbx = slideX(nbx, nby, nrx, nry, d);
							nrx = slideX(nrx, nry, nbx, nby, d);
						} else {
                            // 방향이 서,동이면 x축 고정, y축 이동
							nby = slideY(nbx, nby, nrx, nry, d);
							nry = slideY(nrx, nry, nbx, nby, d);
						}
					}

					// System.out.println("다음 위치 : "+nrx+" "+nry+" // "+nbx+" "+nby);

					// 방문했거나, 파란공이 먼저 빠지면 넘어감
					if (visited[nrx][nry][nbx][nby] || (arr[nbx][nby] == 'O'))
						continue;
					// 빨간공이 빠지면 리턴
					if (arr[nrx][nry] == 'O') {
                    	/*
                    		13460, 15653 - 바로 출력하지 않고 최솟값 계산
                    		answer = Math.min(cnt, answer)
                        */
						System.out.println("1");
						return;
					}
					// System.out.println("다음 위치 안넘어감 : "+nrx+" "+nry+" // "+nbx+" "+nby);
					queue.offer(new Point(nrx, nry, nbx, nby));
					visited[nrx][nry][nbx][nby] = true;
				}
			}
            
            // 맨 끝에 시도횟수 증가
			cnt++;
		} // while문의 끝 - 밑은 시도했지만 불가능함
        
        
        
		/*
        	13460, 15653 - 탈출 불가능 할 때 -1 출력
        	System.out.println(-1);
			System.exit(0);
        */
		System.out.println(0);
	}

	public static int slideX(int currentR, int currentC, int diffR, int diffC, int d) {

		while (arr[currentR][currentC] != '#') { //벽이 아닐 때까지 이동
			currentR = currentR + dx[d];

			if (arr[currentR][currentC] == 'O') { // 구멍에 빠짐
				return currentR;
			}

			if (currentR == diffR && currentC == diffC) { //다른 공에 도착하면 하나 뒤로 가기
				return currentR - dx[d];
			}

		}
		
		//벽에 도달하면 하나 뒤로가기
		return currentR - dx[d];
	}

	public static int slideY(int currentR, int currentC, int diffR, int diffC, int d) {

		while (arr[currentR][currentC] != '#') { //벽이 아닐 때까지 이동
			currentC = currentC + dy[d];

			if (arr[currentR][currentC] == 'O') { // 구멍에 빠짐
				return currentC;
			}

			if (currentR == diffR && currentC == diffC) { //다른 공에 도착하면 하나 뒤로 가기
				return currentC - dy[d];
			}

		}
		
        //벽에 도달하면 하나 뒤로가기
		return currentC - dy[d];

	}

}

* BFS 사용

* 시도 횟수, 시간에 따른 큰 반복문 실행, 그 안에서 각 시작점에 대한 반복문 실행 (que.size())

* 방향에 따라 x축, y축의 이동 변화 / 선후순서 확인

profile
Kiefer Sol
여유를 가지고 Deep Dive
이전 포스트

[백준] 6593. 상범빌딩 (골드5) - BFS

다음 포스트

[백준] 12851 / 13913. 숨바꼭질 (골드4) - BFS, Stack

0개의 댓글