[BOJ-13460][BFS/시뮬레이션] 구슬탈출 2 - Java

문제 바로가기

13460번: 구슬 탈출 2

드뎌 풀어씀다...

4개월전에 이래 풀고 저래 풀고 해도 안됐는데... 드뎌 풀고야 말아씀다...

빨간 공 파란 공 두개를 계속 체크해줘야 되고 이것저것 고려해야할 게 증말 많습니다...

4차원 배열로 풀면 간단하다는데 제 머리론 이해가 안됩니다 ^^;;

 

import java.util.*;

class Dir{
    int y, x, day;
    Dir(int y, int x, int day){
        this.y = y; this.x = x; this.day = day;
    }
}

public class Main {
    static char[][] map;
    static int[][] visited;
    static Dir red, blue;
    static int[] dy = {1, -1, 0, 0};
    static int[] dx = {0, 0, 1, -1};

    static int bfs() {
        Queue<Dir> q = new LinkedList<Dir>();
        visited[red.y][red.x] = 1;
        boolean flag = false;
        boolean blueIn = false;
        int ans = 0;
        q.offer(red);
        q.offer(blue);

        while (!q.isEmpty()) {
            Dir curR = q.poll();
            Dir curB = q.poll();


            forloop:
            for (int i = 0; i < 4; i++) {
                Dir nextR = new Dir(curR.y + dy[i], curR.x + dx[i], curR.day + 1);
                Dir nextB = new Dir(curB.y + dy[i], curB.x + dx[i], 0);

                if(nextR.day > 10) {
                    return -1;
                }

                if (map[nextR.y][nextR.x] == '#' && map[nextB.y][nextB.x] == '#') continue;

                while (map[nextR.y][nextR.x] != '#') {
                    if (map[nextR.y][nextR.x] == 'O') {
                        flag = true;
                        ans = nextR.day;

                        nextR.y += dy[i];
                        nextR.x += dx[i];
                        break;
                    }
                    nextR.y += dy[i];
                    nextR.x += dx[i];
                }
                nextR.y -= dy[i];
                nextR.x -= dx[i];        //끝까지 이동

                whileloop:
                while (map[nextB.y][nextB.x] != '#') {
                    if (map[nextB.y][nextB.x] == 'O') {
                        ans = -1;
                        if(map[nextR.y][nextR.x] == 'O'){
                            blueIn = true;
                        }
                        continue forloop;
                    }
                    nextB.y += dy[i];
                    nextB.x += dx[i];
                }
                nextB.y -= dy[i];
                nextB.x -= dx[i];

                if (flag == true) {
                    if(!blueIn) return ans;
                    else {
                        blueIn = false;
                        flag = false;
                    }
                }

                if (nextB.y == nextR.y && nextB.x == nextR.x) {    //겹쳤을 때 처리
                    switch (i) {
                        case 0:
                            if (curR.y < curB.y) nextR.y -= dy[i];
                            else nextB.y -= dy[i];
                            break;

                        case 1:
                            if (curR.y < curB.y) nextB.y -= dy[i];
                            else nextR.y -= dy[i];
                            break;
                        case 2:
                            if (curR.x < curB.x) nextR.x -= dx[i];
                            else nextB.x -= dx[i];
                            break;
                        case 3:
                            if (curR.x < curB.x) nextB.x -= dx[i];
                            else nextR.x -= dx[i];
                            break;
                    }
                }
                q.offer(nextR);
                q.offer(nextB);
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int M = sc.nextInt();
        map = new char[N][M];
        visited = new int[N][M];
        sc.nextLine();
        for (int i = 0; i < N; i++) {
            String temp = sc.nextLine();
            for (int j = 0; j < M; j++) {
                map[i][j] = temp.charAt(j);
                if (map[i][j] == 'R') red = new Dir(i, j, 0);
                if (map[i][j] == 'B') blue = new Dir(i, j, 0);
            }
        }

        System.out.println(bfs());
    }

}

진짜 지저분하네

flag는 빨간 공이 구멍에 들어갔을 때를 체크해주는 변수입니다. 이 때 무조건 게임에서 이긴게 아니라, 그 뒤에 파란 공이 들어가는지 안들어 가는지도 체크를 해줘야 합니다.

 

처음에 빨간 공이 움직일 수 없는 경우는 탐색하지 않았는데, 이 경우에 굉장히 큰 맹점이 생깁니다. 빨간 공이 움직이지 않더라도 이래저래 판을 기울여서 파란 공이 구멍에 들어가지 않도록 만들어 줄 수 있기 때문입니다.

 

근데 또 파란 공이 같이 들어갔다고 무조건 -1이 정답이 아님다.. 왜냐면 완전 탐색으로 다른 경우들도 다 봐줘야 하기 때문임다 ;;;

 

빨간 공, 파란 공의 다음 위치를 구해주고, 구멍에 들어갔는지 체크해주고... 이것 저것 하고나서 공의 위치가 겹쳐져 있으면 이동한 방향에 따라 공의 위치를 다시 재조정해주면서 BFS를 돌려줍니다...

 

반례를 스스로 만들어보는 연습을 많이 해야겠습니다...

 

머리가 더 좋아진다면 4차원 배열로 한 번 다시 풀어보겟습니다..

 

감사함다~~