BOJ 13459: 구슬 탈출

문제 풀이

생각보다 문제 푸는데 좀 걸렸다....ㅋㅋ

빨간 구슬과 파란 구슬을 관리하기 위해 Queue를 이용했다.
이동 방향에 따라 먼저 움직여야하는 구슬을 정해주고 moveRed(), moveBlue() 함수를 통해 먼저 움직여야 하는 구슬 먼저 이동시켰다.
이동할때 탈출 구멍을 만나면 무조건 거기서 중지시켰다.
파란 구슬은 탈출 하면 무조건 fail이므로 파란 구슬이 탈출하는 경우는 탐색하지 않도록 Queue에서 제외한다.
빨간 구슬 혼자 탈출했다면 무조건 success이므로 함수를 빠져나와 1을 출력한다.

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 {
    static int r, c;
    static char map[][];
    static char target = 'O';
    static char wall = '#';
    static Queue<BallIndex> redQ = new LinkedList<>();
    static Queue<BallIndex> blueQ = new LinkedList<>();
    static int answer = 0;
    public static void main(String[] args) throws IOException {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        r = Integer.parseInt(st.nextToken());
        c = Integer.parseInt(st.nextToken());
        map = new char[r][c];

        for(int i = 0; i < r; i++) {
            String temp = br.readLine();
            for(int j = 0; j < c; j++) {
                char t= temp.charAt(j);
                if(t == 'R') {
                    redQ.add(new BallIndex(i, j));
                    continue;
                }
                if(t == 'B') {
                    blueQ.add(new BallIndex(i, j));
                    continue;
                }
                map[i][j] = t;
            }
        }

        int count = 0;
        while(!redQ.isEmpty()) {
            if(count >= 10) {
                answer = 0;
                break;
            }
            int len = redQ.size();
            for(int i = 0; i < len; i++) {
                move();
                if(answer == 1) {
                    break;
                }
            }
            if(answer == 1) {
                break;
            }
            count++;
        }
        System.out.println(answer);
    }

    static int[] dirI = {0, 0, 1, -1};
    static int[] dirJ = {1, -1, 0, 0};
    public static void move() {
        BallIndex curRed = redQ.poll();
        BallIndex curBlue = blueQ.poll();

        for(int i = 0; i < 4; i++) {
            BallIndex tempRed = new BallIndex(curRed.i, curRed.j);
            BallIndex tempBlue = new BallIndex(curBlue.i, curBlue.j);
            switch (i) {
                case 0:
                    if(curRed.j > curBlue.j) {
                        tempRed = moveRed(tempRed, tempBlue, i);
                        tempBlue = moveBlue(tempRed, tempBlue, i);
                    }
                    else {
                        tempBlue = moveBlue(tempRed, tempBlue, i);
                        tempRed = moveRed(tempRed, tempBlue, i);
                    }
                    break;
                case 1:
                    if(curRed.j < curBlue.j) {
                        tempRed = moveRed(tempRed, tempBlue, i);
                        tempBlue = moveBlue(tempRed, tempBlue, i);
                    }
                    else {
                        tempBlue = moveBlue(tempRed, tempBlue, i);
                        tempRed = moveRed(tempRed, tempBlue, i);
                    }
                    break;
                case 2:
                    if(curRed.i > curBlue.i) {
                        tempRed = moveRed(tempRed, tempBlue, i);
                        tempBlue = moveBlue(tempRed, tempBlue, i);
                    }
                    else {
                        tempBlue = moveBlue(tempRed, tempBlue, i);
                        tempRed = moveRed(tempRed, tempBlue, i);
                    }
                    break;
                case 3:
                    if(curRed.i < curBlue.i) {
                        tempRed = moveRed(tempRed, tempBlue, i);
                        tempBlue = moveBlue(tempRed, tempBlue, i);
                    }
                    else {
                        tempBlue = moveBlue(tempRed, tempBlue, i);
                        tempRed = moveRed(tempRed, tempBlue, i);
                    }
                    break;
            }

            if(map[tempBlue.i][tempBlue.j] == target) {
                continue;
            }
            if(map[tempRed.i][tempRed.j] == target) {
                answer = 1;
                return;
            }
            if(curRed.i == tempRed.i && curRed.j == tempRed.j && curBlue.j == tempBlue.j && curBlue.i == tempBlue.i) {
                continue;
            }
            redQ.add(tempRed);
            blueQ.add(tempBlue);
        }
    }

    public static BallIndex moveRed(BallIndex red, BallIndex blue, int index) {
        while(true) {
            red.i += dirI[index];
            red.j += dirJ[index];
            if(map[red.i][red.j] == target) {
                return red;
            }
            if(map[red.i][red.j] == wall || (red.i == blue.i && red.j == blue.j)) {
                red.i -= dirI[index];
                red.j -= dirJ[index];
                return red;
            }
        }
    }

    public static BallIndex moveBlue(BallIndex red, BallIndex blue, int index) {
        while(true) {
            blue.i += dirI[index];
            blue.j += dirJ[index];
            if(map[blue.i][blue.j] == target) {
                return blue;
            }
            if(map[blue.i][blue.j] == wall || (red.i == blue.i && red.j == blue.j)) {
                blue.i -= dirI[index];
                blue.j -= dirJ[index];
                return blue;
            }
        }
    }
}

class BallIndex {
    int i;
    int j;

    BallIndex(int i, int j) {
        this.i = i;
        this.j = j;
    }
}

github
백준