[JAVA] BOJ 백준 13460번 - 구슬 탈출 2

목차

• 문제
• 내가 푼 방법
• 자바 코드
• 결과 및 회고

---

1. 문제

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

---

2. 내가 푼 방법

최소 몇 번 만에 정답을 구할 수 있는지를 물어보고 있다. 따라서 BFS 알고리즘을 사용하는 방법을 떠올렸다.

하지만 빨간 구슬과 파란 구슬이 동시에 어느 위치에 존재하는지를 알아야 하기 때문에 보드 모양을 arr에 저장하고, 큐에 빨간 구슬과 파란 구슬을 저장시켜 기울임에 따라 이동시키면서 구멍에 빠지는가를 확인했다.

 

먼저 보드 모양을 이차원 배열 arr에 넣는 코드이다. 빨간 구슬과 파란 구슬은 위치만 알아두고 빈칸 상태로 변경해준다.

N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());

arr = new char[N][M];
check = new boolean[N][M][N][M];

int redX = 0;
int redY = 0;
int blueX = 0;
int blueY = 0;

for (int i = 0; i < N; i++) {
    String line = br.readLine();

    for (int j = 0; j < M; j++) {
        arr[i][j] = line.charAt(j);

        if (arr[i][j] == 'R') {
            redX = i;
            redY = j;
            arr[i][j] = '.';
        }
        else if (arr[i][j] == 'B') {
            blueX = i;
            blueY = j;
            arr[i][j] = '.';
        }
    }
}

 

이제 BFS 알고리즘을 통해 두 개의 구슬을 이동시키면서 구멍에 골인시켜야 한다.

두 구슬의 위치를 담을 Tuple 클래스를 큐에 넣고 보드에서 이동하는 과정을 구현했다.

 

중요한 것은 구슬이 기울어야 할 방향으로 더 이상 이동할 수 없을 때까지 이동시켜야 하는 것이므로 move 함수를 만들었다. 그 후 이동한 파란 구슬이 구멍에 들어가는지 확인하여 들어가면 continue; 문으로 건너뛰어주고, 만약 안 들어가면 빨간 구슬이 구멍에 들어가는 확인해 break; 문으로 빠져나온다.

// main문 dfs 함수 호출
// bfs(redX, redY, blueX, blueY);

public static int bfs (int redX, int redY, int blueX, int blueY) {
    int result = -1;

    Queue<Tuple> queue = new LinkedList<>();
    queue.add(new Tuple(redX, redY, blueX, blueY, 0, 's'));

    while (!queue.isEmpty()) {
        Tuple tuple = queue.poll();
        int rx = tuple.rx;
        int ry = tuple.ry;
        int bx = tuple.bx;
        int by = tuple.by;
        int cnt = tuple.cnt;
        char direction = tuple.direction;

        if (rx < 0 || ry < 0 || rx >= N || ry >= M) continue;
        if (bx < 0 || by < 0 || bx >= N || by >= M) continue;
        if (cnt > 10) continue;

        Tuple movedTuple = move(rx, ry, bx, by, direction);

        if (check[movedTuple.rx][movedTuple.ry][movedTuple.bx][movedTuple.by]) continue;

        if (arr[movedTuple.bx][movedTuple.by] == 'O') continue;
        if (arr[movedTuple.rx][movedTuple.ry] == 'O') {
            result = cnt;
            break;
        }

        check[movedTuple.rx][movedTuple.ry][movedTuple.bx][movedTuple.by] = true;

        queue.add(new Tuple(movedTuple.rx, movedTuple.ry, movedTuple.bx, movedTuple.by, cnt+1, 'l'));
        queue.add(new Tuple(movedTuple.rx, movedTuple.ry, movedTuple.bx, movedTuple.by, cnt+1, 'r'));
        queue.add(new Tuple(movedTuple.rx, movedTuple.ry, movedTuple.bx, movedTuple.by, cnt+1, 'u'));
        queue.add(new Tuple(movedTuple.rx, movedTuple.ry, movedTuple.bx, movedTuple.by, cnt+1, 'd'));
    }

    return result;
}

public static class Tuple {
    int rx;
    int ry;
    int bx;
    int by;
    int cnt;
    char direction;

    public Tuple (int rx, int ry, int bx, int by, int cnt, char direction) {
        this.rx = rx;
        this.ry = ry;
        this.bx = bx;
        this.by = by;
        this.cnt = cnt;
        this.direction = direction;
    }
}

 

move 함수 코드는 아래와 같다.

처음 시작인 direction이 s인 상태는 이동할 필요가 없으므로 바로 리턴해주고, 그 외에는 moveUntilWall 함수에 빨간 구슬 혹은 파란 구슬을 넣어준다. 각각의 if와 else 문은 같은 행, 열에 있을 경우에 먼저 기울임에 따라 먼저 이동해야 하는 구슬이 존재하므로 다음과 같이 나눠줬다.

public static Tuple move(int rx, int ry, int bx, int by, char direction) {
    if (direction == 's') return new Tuple(rx, ry, bx, by, 0, direction);

    miniTuple tr;
    miniTuple tb;

    if ((direction == 'l' && ry > by) || (direction == 'r' && ry < by) || (direction == 'u' && bx < rx) ||  (direction == 'd' && bx > rx)) {
        tb = moveUntilWall(bx, by, direction);
        if (arr[tb.x][tb.y] != 'O') arr[tb.x][tb.y] = 'B';
        tr = moveUntilWall(rx, ry, direction);
        if (arr[tb.x][tb.y] != 'O') arr[tb.x][tb.y] = '.';
    }
    else {
        tr = moveUntilWall(rx, ry, direction);
        if (arr[tr.x][tr.y] != 'O') arr[tr.x][tr.y] = 'R';
        tb = moveUntilWall(bx, by, direction);
        if (arr[tr.x][tr.y] != 'O') arr[tr.x][tr.y] = '.';
    }

    return new Tuple(tr.x, tr.y, tb.x, tb.y, 0, direction);
}

public static miniTuple moveUntilWall (int x, int y, char direction) {
    if (direction == 'l') {
        while (arr[x][y-1] == '.' || arr[x][y-1] == 'O') {
            y--;
            if (arr[x][y] == 'O') break;
        }
    }
    else if (direction == 'r') {
        while (arr[x][y+1] == '.' || arr[x][y+1] == 'O') {
            y++;
            if (arr[x][y] == 'O') break;
        }
    }
    else if (direction == 'u') {
        while (arr[x-1][y] == '.' || arr[x-1][y] == 'O') {
            x--;
            if (arr[x][y] == 'O') break;
        }
    }
    else {
        while (arr[x+1][y] == '.' || arr[x+1][y] == 'O') {
            x++;
            if (arr[x][y] == 'O') break;
        }
    }

    return new miniTuple(x, y);
}

---

3. 자바 코드

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

class Main {
    static int N;
    static int M;
    static char[][] arr;

    static boolean[][][][] check;

    public static void main (String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        arr = new char[N][M];
        check = new boolean[N][M][N][M];

        int redX = 0;
        int redY = 0;
        int blueX = 0;
        int blueY = 0;

        for (int i = 0; i < N; i++) {
            String line = br.readLine();

            for (int j = 0; j < M; j++) {
                arr[i][j] = line.charAt(j);

                if (arr[i][j] == 'R') {
                    redX = i;
                    redY = j;
                    arr[i][j] = '.';
                }
                else if (arr[i][j] == 'B') {
                    blueX = i;
                    blueY = j;
                    arr[i][j] = '.';
                }
            }
        }

        bw.write(bfs(redX, redY, blueX, blueY)+"");

        br.close();
        bw.flush();
        bw.close();
    }

    public static int bfs (int redX, int redY, int blueX, int blueY) {
        int result = -1;

        Queue<Tuple> queue = new LinkedList<>();
        queue.add(new Tuple(redX, redY, blueX, blueY, 0, 's'));

        while (!queue.isEmpty()) {
            Tuple tuple = queue.poll();
            int rx = tuple.rx;
            int ry = tuple.ry;
            int bx = tuple.bx;
            int by = tuple.by;
            int cnt = tuple.cnt;
            char direction = tuple.direction;

            if (rx < 0 || ry < 0 || rx >= N || ry >= M) continue;
            if (bx < 0 || by < 0 || bx >= N || by >= M) continue;
            if (cnt > 10) continue;

            Tuple movedTuple = move(rx, ry, bx, by, direction);

            if (check[movedTuple.rx][movedTuple.ry][movedTuple.bx][movedTuple.by]) continue;

            if (arr[movedTuple.bx][movedTuple.by] == 'O') continue;
            if (arr[movedTuple.rx][movedTuple.ry] == 'O') {
                result = cnt;
                break;
            }

            check[movedTuple.rx][movedTuple.ry][movedTuple.bx][movedTuple.by] = true;

            queue.add(new Tuple(movedTuple.rx, movedTuple.ry, movedTuple.bx, movedTuple.by, cnt+1, 'l'));
            queue.add(new Tuple(movedTuple.rx, movedTuple.ry, movedTuple.bx, movedTuple.by, cnt+1, 'r'));
            queue.add(new Tuple(movedTuple.rx, movedTuple.ry, movedTuple.bx, movedTuple.by, cnt+1, 'u'));
            queue.add(new Tuple(movedTuple.rx, movedTuple.ry, movedTuple.bx, movedTuple.by, cnt+1, 'd'));
        }

        return result;
    }

    public static Tuple move(int rx, int ry, int bx, int by, char direction) {
        if (direction == 's') return new Tuple(rx, ry, bx, by, 0, direction);

        miniTuple tr;
        miniTuple tb;

        if ((direction == 'l' && ry > by) || (direction == 'r' && ry < by) || (direction == 'u' && bx < rx) ||  (direction == 'd' && bx > rx)) {
            tb = moveUntilWall(bx, by, direction);
            if (arr[tb.x][tb.y] != 'O') arr[tb.x][tb.y] = 'B';
            tr = moveUntilWall(rx, ry, direction);
            if (arr[tb.x][tb.y] != 'O') arr[tb.x][tb.y] = '.';
        }
        else {
            tr = moveUntilWall(rx, ry, direction);
            if (arr[tr.x][tr.y] != 'O') arr[tr.x][tr.y] = 'R';
            tb = moveUntilWall(bx, by, direction);
            if (arr[tr.x][tr.y] != 'O') arr[tr.x][tr.y] = '.';
        }

        return new Tuple(tr.x, tr.y, tb.x, tb.y, 0, direction);
    }

    public static miniTuple moveUntilWall (int x, int y, char direction) {
        if (direction == 'l') {
            while (arr[x][y-1] == '.' || arr[x][y-1] == 'O') {
                y--;
                if (arr[x][y] == 'O') break;
            }
        }
        else if (direction == 'r') {
            while (arr[x][y+1] == '.' || arr[x][y+1] == 'O') {
                y++;
                if (arr[x][y] == 'O') break;
            }
        }
        else if (direction == 'u') {
            while (arr[x-1][y] == '.' || arr[x-1][y] == 'O') {
                x--;
                if (arr[x][y] == 'O') break;
            }
        }
        else {
            while (arr[x+1][y] == '.' || arr[x+1][y] == 'O') {
                x++;
                if (arr[x][y] == 'O') break;
            }
        }

        return new miniTuple(x, y);
    }

    public static class Tuple {
        int rx;
        int ry;
        int bx;
        int by;
        int cnt;
        char direction;

        public Tuple (int rx, int ry, int bx, int by, int cnt, char direction) {
            this.rx = rx;
            this.ry = ry;
            this.bx = bx;
            this.by = by;
            this.cnt = cnt;
            this.direction = direction;
        }
    }

    public static class miniTuple {
        int x;
        int y;

        public miniTuple (int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
}

---

4. 결과 및 회고

코드가 꽤 길어져서 당황했는데, N과 M의 크기가 크지 않아서 제대로 구현만 한다면 BFS 알고리즘으로 풀릴 수 있을 것 같았다. 다행히 내 생각이 맞았던 것 같다 ㅎㅎ move 함수에서 direction 상태가 s일 경우에만 이동할 필요가 없었다는 것을 놓치고 있었어서 시간이 좀 걸렸다. 세세한 부분에 신경써보장.