Baekjoon13460Java

1. 예시) 1번과 3번을 가진 CCTV를 가진 사무실이 있으면 4가지 x 4가지의 방향 가지수로 16가지라는 경우의 수가 나온다. 이런 경우 2번과 5번은 방향의 가지수가 있으며 각각의 CCTV는 방향이 다르기 때문에 순서가 중요하여 순열로 구해야 한다.
2. 순열이란 n개의 값중에서 r개의 숫자를 순서대로 뽑는 경우를 말한다.
3. 각각의 CCTV는 각각의 다른 방향이 있으며 각각의 cctv의 위치와 몇번 cctv인지 판단할 필드값을 가지는 클래스를 하나 만들어준다.
4. 순열을 담아줄 배열을 하나 만들어주어 output을 cctv개수만큼 담을 배열을 선언해준다.
5. 순열 함수를 만들어 주어, 각각의 경우의 수에 대한 copymap을 구해준다. 여기서 copymap을 해주는 이유는 방향에따른 맵을 그려주었을 때, 다시 다른 경우의 수에 대한 맵을 처음부터 그려주기 위하여 copyMap을 선언한다.
6. 그 후 cctvList에 있는 cctv를 하나씩 조회하여 방향을 구해준 후, 각각의 총 4가지에 대한 방향을 for문으로 돌려주어 담아준다음에 depth와 순열에 있는 크기가 비슷해졌을 경우 사각지대를 구해준다.

 

 

package src.week4.Baekjoon13460;

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 Baekjoon13460 {
    static int N,M;
    static boolean [][][][]visited;
    static char [][]board;
    static int holeX,holeY;
    static Marble red,blue;
    static int dx[] = {0, 0, -1, 1}; // 왼 오 아래 위
    static int dy[] = {-1, 1, 0, 0};
    static class Marble{
        int rx;
        int ry;
        int bx;
        int by;
        int cnt;
        Marble(int rx, int ry, int bx, int by, int cnt){
            this.rx = rx;
            this.ry = ry;
            this.bx = bx;
            this.by = by;
            this.cnt = cnt;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        board = new char[N][M];
        visited = new boolean[N][M][N][M];

        for(int i=0; i<N; i++){
            String str = br.readLine();
            for(int j=0; j<M; j++){
                board[i][j] = str.charAt(j);

                if(board[i][j]=='R'){
                    red = new Marble(i, j, 0,0,0);
                } else if(board[i][j] == 'B'){
                    blue = new Marble(0, 0, i, j, 0);
                } else if(board[i][j] =='O'){
                    holeX = i;
                    holeY = j;
                }
            }
        }

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

    static int bfs(){
        Queue<Marble> q = new LinkedList<>();
        q.add(new Marble(red.rx, red.ry, blue.bx, blue.by, 1));
        visited[red.rx][red.ry][blue.rx][blue.ry] = true;

        while(!q.isEmpty()){
            Marble marble = q.poll();
            int curRx = marble.rx;
            int curRy = marble.ry;
            int curBx = marble.bx;
            int curBy = marble.by;
            int curCnt = marble.cnt;

            if(curCnt > 10) {
                return -1;
            }

            for(int i=0; i<4; i++){
                int newRx = curRx;
                int newRy = curRy;
                int newBx = curBx;
                int newBy = curBy;

                boolean isRedHole = false;
                boolean isBlueHole = false;

                while (board[newRx + dx[i]][newRy + dy[i]] != '#' && newRx + dx[i] < N && newRx + dx[i] >= 0 && newRy + dy[i] < M && newRy + dy[i] >= 0){
                    newRx += dx[i];
                    newRy += dy[i];
                    if(holeX == newRx && holeY == newRy){
                        isRedHole = true;
                        break;
                    }
                }

                while(board[newBx + dx[i]][newBy + dy[i]] != '#' && newBx + dx[i] < N && newRx + dx[i] >= 0 && newRy + dy[i] < M && newRy + dy[i] >= 0){
                    newBx += dx[i];
                    newBy += dy[i];
                    if(holeX == newBx && holeY == newBy){
                        isBlueHole = true;
                        break;
                    }
                }

                if(isBlueHole){
                    continue;
                }

                if(isRedHole && !isBlueHole){
                    return curCnt;
                }

                if(newRx == newBx && newRy == newBy){
                    if(i==0){
                        if(curRy < curBy) newBy -= dy[i];
                        else newRy -= dy[i];
                    } else if(i==1){
                        if(curRy > curBy) newBy -= dy[i];
                        else newRy -= dy[i];
                    } else if(i==2){
                        if(curRx < curBx) newBx -= dx[i];
                        else newRx -= dx[i];
                    } else{
                        if(curRx > curBx) newBx -= dx[i];
                        else newRx -= dx[i];
                    }
                }

                if(!visited[newRx][newRy][newBx][newBy]){
                    q.add(new Marble(newRx, newRy, newBx, newBy, curCnt + 1));
                    visited[newRx][newRy][newBx][newBy] = true;
                }
            }
        }
        return -1;
    }
}