백준 13460 구슬 탈출2

오랜만에 글을 올리게 되었다.

자바 교육을 받게 되어서 이제 부터는 자바로 풀게 되었다.

 

조금 힘들게 문제를 풀었다.

저번에 한 번 풀다가 도저히 못 풀것 같아서 다른 분들 코드를 참조했었다.

그러다가 흐지부지 넘어갔었다가 다시 풀게 되었다.

그 때 코드를 조금 봤던 덕분에 어떤식으로 풀어야 할지 대강 감이 오긴 했으나 역시 이번에도 힘겹게 풀었다.

7번? 정도 틀린 후에 질문 게시판에서 여러 테스트 케이스를 넣어 보고 겨우 통과했다.

 

BFS를 이용한 시뮬레이션 문제라고 생각하는데 그 조건들이 꽤나 까다로웠던 것 같다.

그래서 여러가지 경우의 수를 잘 생각하고 풀어야 하는 문제인 것 같다.

 

먼저, BFS를 이용해도 dr, dc를 이용해서 한 칸 정도씩 이동하는 것은 해보았지만 이 문제처럼 해당 방향으로 끝까지

이동하는 문제를 풀어 본적은 없었다. 그래서 좋은 경험이 된 것 같다.

또한, 한 개의 구슬만 움직여서 탈출시키는 것이 아니라 두 개의 구슬을 움직여야 했기 때문에 동시성이라는 면도

좋은 문제 풀이 경험이 되었다.

마지막으로 항상 다음 번에 응용해야지 하면서도 한 번도 응용한 적이 없는 4차원 배열을 이용한 visit를 다시 한 번

사용하게 되었다. 

이 3가지 특징이 이번 문제의 핵심이었던 것 같다.

 

이를 해결하기 위해서 필요한 조건들이 매우 까다로웠던 것 같다.

 

먼저, 빨간 공과 파란 공을 동시에 신경 써줘야 한다는 점이다.

빨간 공은 막혀서 그대로 있고, 파란 공만 이동되는 경우가 있는데, 이로 인해서 답이 바뀌는 경우가 있다.

그래서 visit를 사용할 때 빨간 공의 위치 뿐만 아니라 파란 공의 위치도 신경 써줘야 한다.

이를 생각하지 못하고 빨간 공에 대해서만 2차원 배열로 visit를 해주었더니 계속 틀렸다.

이에 대한 테스트 케이스는 해당 문제의 질문 게시판에 있다.

 

다음은 하지 말아야 할 실수 였다. 빨간 공과 파란 공을 queue에 넣을 때 10번의 이동을 하지 않고, empty가 되면

종료 했어야 했는데, 이를 간과했다.

 

그리고 중요하게 처리해야 할 부분이 빨간 공과 파란 공이 겹치는 부분이다. 이를 어떻게 해결해야 할까 고민했었는데,

케이스에  따라서 빨간 공이 앞일수도 있고, 파란 공이 앞일 수도 있기 때문이었다.

도저히 방법이 생각나지 않았었고, 다른 분들의 코드를 참조하여, 이동한 거리를 체크하면 됨을 알게 되었다.

 

또 중요한 점은 기존의 BFS는 한 칸씩 이동하면서 다 visit를 체크해줬었다. 하지만 해당 문제는 어짜피 멈출 때까지 

계속 이동하므로 공이 멈춘 곳에만 visit를 표시하면 되었지만, 이를 다 체크하려다 보니 생각이 가로막혀 있었다.

 

중요한 부분이 많았는데, 또 한가지 있다면 빨간 공이 골인한 경우와 파란 공이 골인한 경우를 잘 구분해야 한다는 것이다.

빨간 공만 통과하는 경우만 처리를 하고 파란 공이 통과를 하는 경우는 continue도 하지 않고 무시를 하면 된다고 생각했다. 하지만 내가 짠 코드에서 continue를 하지 않을 경우 파란 공이 골인 위치에서 멈추고 visit를 체크하는 문제점이 발생했다. 그래서 이를 처리해 주어야 했다. 깊게 생각하지 않아서 생긴 문제였다.

 

마지막으로 이동 횟수를 먼저 증가시키고 BFS를 처리한 후 이동 거리가 10을 넘어가면 종료를 시키려고 했는데, 

while문을 시작할 때 10이 되면 10번 째 이동이 되므로  해당 로직을 진행하면 안 되는  거였다. 이 것도 찾지 못해서

질문 게시판의 답변을 통해 알게 되었다.

 

이처럼 여러 조건의 까다로운 문제였던 것 같다. 그래도 그 만큼 실력 향상에 많은 도움이 될 수 있는 문제라고 생각하고

꼭 다시 풀어 보아야 겠다고 생각했다.

 

아래는 코드이다.

 

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 Main13460 {
    static int[] dr = { -1, 0, 1, 0 };
    static int[] dc = { 0, 1, 0, -1 };
    static boolean[][][][] visit;
    static char[][] map;
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
 
        map = new char[n][m];
        Queue<Integer> red = new LinkedList<Integer>();
        Queue<Integer> blue = new LinkedList<Integer>();
 
        int srr = 0, src = 0, brr = 0, brc = 0;
        for (int i = 0; i < n; i++) {
            map[i] = br.readLine().toCharArray();
            for (int j = 0; j < m; j++) {
                if (map[i][j] == 'R') {
                    red.offer(i);
                    red.offer(j);
                    red.offer(0);
                    srr = i;
                    src = j;
                }
                if (map[i][j] == 'B') {
                    blue.offer(i);
                    blue.offer(j);
                    brr = i;
                    brc = j;
                }
            }
        }
 
        // 파란 공만 움직여서 답이 달라지는 경우가 있으므로 4차원 배열로 써야 한다. 개 빡침
        visit = new boolean[n][m][n][m];
        visit[srr][src][brr][brc] = true;
 
        int ans = -1;
 
        while (true) {
 
            // 더 이상 갈 수가 없으면 empty 처리를 해줘야 한다. 개 빡침
            boolean flag = false;
            if (red.isEmpty())
                break;
            int rr = red.poll();
            int rc = red.poll();
            int dis = red.poll();
            int bbr = blue.poll();
            int bbc = blue.poll();
            for (int i = 0; i < 4; i++) {
                int[] rarr = move(rr, rc, i);
                int[] barr = move(bbr, bbc, i);
 
                if (rarr[0] == barr[0] && rarr[1] == barr[1]) {
                    if (map[rarr[0]][rarr[1]] == 'O') {
                        continue;
                    }
                    if (rarr[2] > barr[2]) {
                        rarr[0] = rarr[0] + dr[(i + 2) % 4];
                        rarr[1] = rarr[1] + dc[(i + 2) % 4];
                    } else {
                        barr[0] = barr[0] + dr[(i + 2) % 4];
                        barr[1] = barr[1] + dc[(i + 2) % 4];
                    }
                }
                if (rarr[3] == 1 && barr[3] == 0) {
                    if (ans == -1 || dis + 1 < ans)
                        ans = dis + 1;
                    flag = true;
                    break;
                }
                // 파란 공만 들어간 경우에는 visit로 처리하지 않고 다음으로 넘어가야 한다. 개 빡침
                if (rarr[3] == 0 && barr[3] == 1)
                    continue;
                if (!visit[rarr[0]][rarr[1]][barr[0]][barr[1]]) {
//                    System.out.println(rarr[0] + " " + rarr[1] + " " + barr[0] + " " + barr[1] + " " + i);
                    red.offer(rarr[0]);
                    red.offer(rarr[1]);
                    red.offer(dis + 1);
                    blue.offer(barr[0]);
                    blue.offer(barr[1]);
                    visit[rarr[0]][rarr[1]][barr[0]][barr[1]] = true;
                }
            }
            // 다음에 들어가면 10이 넘어가니까 끝내야 한다 개 빡침
            if (flag || dis > 9) {
                break;
            }
 
        }
        System.out.println(ans);
    }
 
    static int[] move(int rr, int rc, int dir) {
        int[] ret = new int[4];
        while (true) {
            rr = rr + dr[dir];
            rc = rc + dc[dir];
            if (map[rr][rc] == '#') {
                rr = rr + dr[(dir + 2) % 4];
                rc = rc + dc[(dir + 2) % 4];
                break;
            }
            if (map[rr][rc] == 'O') {
                ret[3]++;
                break;
            }
            ret[2]++;
        }
        ret[0] = rr;
        ret[1] = rc;
 
        return ret;
    }
 
}