[백준 18428] - 감시 피하기(JAVA)

출처 - https://www.acmicpc.net/problem/18428

18428번: 감시 피하기

---

[문제풀이 전] 

이코테  DFS&BFS 20번 문제이기도 합니다. 연구소 문제를 먼저 풀어봐서인지 쉽게 해결했습니다. 똑같이 3개의 장애물을 모든 경우에 세우고 감시의 여부를 구해야하는데 여기서 신경써야 할 점인게 선생님끼리 감시가 겹쳤을 때 처리만 잘 해준다면 될 것 같습니다.

 

---

[문제풀이] 

N제한이 작아 모든 배열에 기둥을 3개씩 설치하는 경우는 36 C 3 으로 10,000 이하로 모든 경우를 해도 시간 초과가 없을 것입니다. 학생의 좌표를 따로 리스트에 만들어 넣어줍니다. 이유는 감시가 이루어진 뒤 해당 좌표가 감시 지역이 됐는지 안됐는지 boolean 으로 체크 하기 때문입니다. 벽을 세개를 설치를 하는 조합식을 만들고 3개가 됐을 때 BFS를 탐색합니다. BFS 탐색할때 해당 좌표가 선생님이면 장애물을 만나기전까지 좌표를 감시 지역으로 만듭니다. [주의] 탐색 조건에 감시 지역이면 감시를 안한다 라고 조건을 넣으면 선생님 끼리 감시가 겹쳤을때 장애물이 없음에도 다음 지역을 탐색 할 수 없습니다. 감시가 끝나고 학생 좌표가 감시대상이면 "YES"를 출력하고 모든 경우의 감시가 끝나고 학생 좌표가 감시 대상이 아니면 "NO"를 출력합니다.

 

 

• 입력된 값을 map 이라는 2차원 배열을 선언한다. 
• 학생의 좌표값을 ArrayList 에 담는다
• dfs (재귀) 탐색으로 장애물을 설치할 수 있는 모든 경우를 만든다.
• 장애물이 3개가 된 경우 bfs 탐색을 시작한다.
• bfs 탐색을 할 때 선생님은 상 하 좌 우 모든 방향을 감시를 할 수 있게 처리한다.
• 선생님의 감시 범위가 구해지면 List에 담은 학생 좌표가 감시 범위인지 체크한다.
• 감시 범위에 학생이 있으면 "YES" 없다면 "NO"

 

---

[소스코드] 

import java.io.*;
import java.util.*;

public class Q20 {
    static class Node{
        int x;
        int y;

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

    static ArrayList<Node> student = new ArrayList<>();
    static int n;
    static char[][] map;
    static final int[] dx = {0, 0, 1, -1};
    static final int[] dy = {1, -1, 0, 0};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        map = new char[n][n];


        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                map[i][j] = st.nextToken().charAt(0);
                if(map[i][j] == 'S'){
                    student.add(new Node(i, j));
                }
            }
        }
        dfs(0);

        System.out.println("NO");

    }

    static void dfs(int wall) {
        if (wall == 3) {
            bfs();
            return;
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (map[i][j] == 'X') {
                    map[i][j] = 'O';
                    dfs(wall + 1);
                    map[i][j] = 'X';
                }
            }
        }
    }

    private static void bfs() {

        Queue<Node> q = new LinkedList<>();
        char[][] copyMap = new char[n][n];
        boolean[][] check = new boolean[n][n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                copyMap[i][j] = map[i][j];
            }
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (copyMap[i][j] == 'T') {
                    q.add(new Node(i, j));
                    check[i][j] = true;
                }
            }
        }

        while (!q.isEmpty()) {
            Node now = q.poll();
            int x = now.x;
            int y = now.y;

            for (int k = 0; k < 4; k++) {
                int nx = x + dx[k];
                int ny = y + dy[k];

                while(0 <= nx && nx < n && 0 <= ny && ny < n) {
                    if (copyMap[nx][ny] != 'O') {
                        check[nx][ny] = true;
                        nx += dx[k];
                        ny += dy[k];
                    }else{
                        break;
                    }
                }
            }
        }
        if(catchStudent(check)){
            System.out.println("YES");
            System.exit(0);
        }
    }

    private static boolean catchStudent(boolean[][] check) {

        for (Node node : student) {
            if (check[node.x][node.y] == true) {
                return false;
            }
        }
        return true;
    }
}