[백준 *Java] - 구슬 탈출 2(13460)

구슬 탈출2

13460번: 구슬 탈출 2

👇 접근 방식

이 문제는 처음에 전에 풀었떤 두 동전(16197) 문제와 유사해서 1차 로직 설계는 금방 했던 거 같습니다.
제 생각은 이 문제 풀기 전에, 두 동전 문제 풀고 오시면, 훨씬 이해하기도 쉽고 계단식의 문풀을 경험할 수 있을 거 같아요.

1차 로직 설계는
1. 두 구슬 위치를 저장해 놓기. (R, B 구분을 해주어야합니다. 따라서, 구슬 한 객체에 두 구슬 위치 값을 넣습니다)
2. 두 구슬의 최초 위치를 담고 있는 객체를 queue에 집어 넣습니다.
3. bfs 로직을 돌려줍니다.
  3-1. 현재 위치의 구슬의 기웃 횟수가 10일 경우? return
  3-2. 기울려서 구슬이 움직이기 때문에, 두 구슬이 한 번 기울 때마다, 벽을 만날 때까지 계속 위치가 변해야합니다. (while)
  3-3. 굴러가는 도중에 구슬이 둘 다 빠지면 continue, 한 구슬만 빠진다면 기운 횟수+1 해서 return
  3-4. 현재 구슬이 while문을 통해 이동했다면? offer하면서 기울기 횟수 +1 아닐 시, offer하면서 기울기 횟수 +0(고정)

이렇게 로직을 설계하고 구현 했을 때, 테케 값을 넣었을 때, 몇 개의 테케가 값과 차이가 큰 수가 나와서 로직 상 문제가 생겼다는 걸 알았습니다.

로직 구현할 때, 문제가 됐던 점은 visited 처리를 하면서, 최소를 찾아주게끔 수정하면서,
while문을 타서, 구슬이 이동하다가 R과 B가 같은 위치에 있을 시, R과 B 구슬은 동일 위치에 있을 수 없기 때문에 위치 재조정이 필요하다는 걸 알았습니다. 이 로직 부분 때문에 골드1인 거 같게 느껴졌습니다.
이 부분을 고민하느라 시간을 많이 썼던 거 같습니다.
이 부분은 아래 그림으로 그려놓았으니, 보면서 코드를 보시면 더 이해하기 쉬울 거 같습니다.
제 로직은 북-> 동 -> 남 -> 서 로 사방면이 움직입니다.

 

아래의 그림은 bfs 로직 내에서 사방면으로 구슬이 굴러  R구슬과 B구슬의 위치가 같을 시를 그림으로 case를 정리해둔 것입니다.

 

아래는 성공한 코드입니다.

 

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 Main {
    private static int[] dx = {-1, 0, 1, 0}; // 북동남서
    private static int[] dy = {0, 1, 0, -1};
    private static final int fourDirection = 4;
    private static int N, M; // 세로(row), 가로(column)
    private static char[][] board;
    private static Queue<Bead> qu = new LinkedList<>();
    private static boolean[][][][] visited;
    private static int min = -1;

    private static class Bead {
        int redX;
        int redY;
        int blueX;
        int blueY;
        int cnt;
        
        public Bead(int redX, int redY, int blueX, int blueY, int cnt) {
            this.redX = redX;
            this.redY = redY;
            this.blueX = blueX;
            this.blueY = blueY;
            this.cnt = cnt;
        }
    }

    private static void bfs() {
        while (!qu.isEmpty()) {
            Bead bead = qu.poll();

            if (bead.cnt == 10) {
                min = -1;
                return;
            }

            for (int i = 0; i < fourDirection; i++) {
                int red_nx = bead.redX;
                int red_ny = bead.redY;
                int blue_nx = bead.blueX;
                int blue_ny = bead.blueY;

                //checking a bead falls into a hole
                boolean redBead = false;
                boolean blueBead = false;


                while (board[red_nx + dx[i]][red_ny + dy[i]] != '#') {
                    red_nx += dx[i];
                    red_ny += dy[i];
                    if (board[red_nx][red_ny] == 'O') {
                        redBead = true;
                        break;
                    }
                }

                while (board[blue_nx + dx[i]][blue_ny + dy[i]] != '#') {
                    blue_nx += dx[i];
                    blue_ny += dy[i];
                    if (board[blue_nx][blue_ny] == 'O') {
                        blueBead = true;
                        break;
                    }
                }

                if (blueBead) continue;
                if (redBead || blueBead) {
                    min = bead.cnt + 1;
                    return;
                }

                // 기울렸을 때, 구슬이 동일 위치에 있을 경우, 구슬 조정
                if (red_nx == blue_nx && red_ny == blue_ny) {
                    switch (i) {

                        case 0 :
                            if(bead.redX > bead.blueX) red_nx -= dx[i];
                            else blue_nx -= dx[i]; // 위치조정
                            break;
                        case 1 :
                            if (bead.redY < bead.blueY) red_ny -= dy[i];
                            else blue_ny -= dy[i]; // 위치조정
                            break;
                        case 2 :
                            if(bead.redX < bead.blueX) red_nx -= dx[i];
                            else blue_nx -= dx[i]; // 위치조정
                            break;
                        case 3 :
                            if (bead.redY > bead.blueY) red_ny -= dy[i];
                            else blue_ny -= dy[i]; // 위치조정
                            break;
                    }
                }
                if (!visited[red_nx][red_ny][blue_nx][blue_ny]) {
                    visited[red_nx][red_ny][blue_nx][blue_ny] = true;
                    qu.offer(new Bead(red_nx, red_ny, blue_nx, blue_ny, bead.cnt + 1));
                }
            }
        }
    }

    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];
        visited = new boolean[N][M][N][M];
        int rx = 0, ry = 0, bx = 0, by =  0;
        for (int i = 0; i < N; i++) {
            String line = br.readLine();
            for (int j = 0; j < M; j++) {
                board[i][j] = line.charAt(j);
                if (board[i][j] == 'R') {
                    rx = i;
                    ry = j;
                }else if(board[i][j] == 'B') {
                    bx = i;
                    by = j;
                }
            }
        }
        visited[rx][ry][bx][by] = true;
        qu.offer(new Bead(rx, ry, bx, by, 0));
        bfs();
        System.out.println(min);
    }
}

 

 

사실 10이라는 기울기라는 제한이 있어서, 방문처리를 하지 않더라도 문제가 통과가 될것입니다.

하지만, 메모리사용과 시간복잡도의 차이가 있으니,

방문처리를 이용하여 방문했던 곳은 반복되는 루프를 돌지 않게 끔 코드를 짜는게 좋은 거 같습니다.

 

방문처리 할 경우,

방문처리 하지 않을 경우,

 

후기

이번 문제를 풀면서, 어느정도 bfs 문제에 적응 됐다고 많이 느꼈으며,

bfs 문제에서 조금 더 고민이 필요한 문제를 해결해 나아가는 과정을 겪으며 충분히 변화된 문제를 풀수 있을 거 같다는 자신감을 얻었습니다. 단, 시간이 걸리네요ㅜ