algorithms 백준 (BOJ)

[BOJ]백준 13460번: 구슬 탈출 2 (baekjoon 13460)

2019.08.21 ·

(BOJ)백준 13460 - 13460번: 구슬 탈출 2

목차

• 코드
• 설명

13460번: 구슬 탈출 2

[BOJ] 백준 (13460)

백준 13460 - 13460번: 구슬 탈출 2

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

코드

import java.io.*;
import java.util.ArrayList;
import java.util.List;

public class BaekJoon13460 {
    static int n, m, dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1}, answer = Integer.MAX_VALUE, callCnt = 0;
    static String ins[];
    static Point R, B, G;
    static char[][] map = new char[11][];
    public static void main(String[] args) throws IOException, CloneNotSupportedException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        ins = br.readLine().split(" ");
        n = Integer.parseInt(ins[0]);
        m = Integer.parseInt(ins[1]);
        for (int i = 0; i < n; i++) {
            map[i] = br.readLine().toCharArray();
            for (int j = 0; j < m; j++) {
                if (map[i][j] == 'R') R = new Point(i, j);
                if (map[i][j] == 'B') B = new Point(i, j);
                if (map[i][j] == 'O') G = new Point(i, j);
            }
        }
        dfs(-1, 0, new ArrayList<>());
        bw.write(answer == Integer.MAX_VALUE ? "-1\n" : answer + "\n");
        bw.flush();bw.close();
    }

    private static void dfs(int prev, int cnt, List<Integer> dirs) throws CloneNotSupportedException {
        if (cnt == 10) {
            answer = Math.min(process(dirs), answer);
            return;
        }
        for (int i = 0; i < 4; i++) {
            if (i == prev) continue;
            dirs.add(i);
            dfs(i,cnt + 1, dirs);
            dirs.remove(dirs.size() - 1);
        }
    }

    private static int process(List<Integer> dir) throws CloneNotSupportedException {
        Point r, b, g;
        r = (Point)R.clone();
        b = (Point)B.clone();
        g = (Point)G.clone();
        char tmap[][] = new char[n][m];
        for (int i = 0; i < n; i++) {
            System.arraycopy(map[i], 0,tmap[i], 0, m);
        }
        int ans = 0;
        List<Integer> dirs = new ArrayList<>();
        dirs.addAll(dir);

        while (!dirs.isEmpty()) {
            int d = dirs.remove(0);
            if (isRedFirst(d, r, b)) {
                moveBead(r, d, 'R', tmap);
                moveBead(b, d, 'B', tmap);
            } else {
                moveBead(b, d, 'B', tmap);
                moveBead(r, d, 'R', tmap);
            }
            ans++;
            if (b.isFall) return Integer.MAX_VALUE;
            if (r.equals(g) && !b.equals(g)) {
                return ans;
            }
        }

        return Integer.MAX_VALUE;
    }

    private static boolean isRedFirst(int d, Point r, Point b) {
        switch (d) {
            case 0 : return r.x < b.x;
            case 1 : return r.x > b.x;
            case 2 : return r.y < b.y;
            case 3 : return r.y > b.y;
            default: throw new IllegalArgumentException();
        }
    }

    private static void moveBead(Point p, int d, char c, char[][] map) {
        int rx = p.x + dx[d], ry = p.y + dy[d];
        while (map[rx][ry] == '.') {
            rx += dx[d];
            ry += dy[d];
        }
        if (map[rx][ry] == '#' || map[rx][ry] == 'R' || map[rx][ry] == 'B') {
            rx -= dx[d];
            ry -= dy[d];
        }
        if (map[rx][ry] != 'O') map[rx][ry] = c;
        if (!(rx == p.x && ry == p.y)) map[p.x][p.y] = '.';
        p.x = rx;
        p.y = ry;
        if (p.equals(G)) p.isFall = true;
    }

    private static class Point implements Cloneable {
        int x, y;
        boolean isFall = false;
        @Override
        protected Object clone() throws CloneNotSupportedException {
            return super.clone();
        }

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

        public boolean equals(Point o) {
            return (this.x == o.x && this.y == o.y);
        }
    }

}

설명