[백준] 감시 피하기

문제

https://www.acmicpc.net/problem/18428

 

 

 

 

풀이

 

문제 요약

1. NxN 크기의 복도에서 선생님(T), 학생(S), 장애물(O), 빈칸(X)이 주어진다.
2. 선생님은 상, 하, 좌, 우 방향으로 감시를 하며, 장애물이 있으면 그 뒤는 볼 수 없다.
3. 학생들이 선생님의 감시를 피할 수 있도록 정확히 3개의 장애물을 배치할 수 있는지 확인해야 한다.
4. 가능한 모든 장애물 배치 경우의 수를 확인하고, 학생이 들키지 않는 경우가 존재하는지 판단해야 한다.

 

import java.util.*;

class Combination { // nCr 조합 구하는 로직
    private int n;  // 전체 요소 개수
    private int r;  // 뽑을 요소 개수
    private int[] now; // 현재 조합
    private ArrayList<ArrayList<Position>> result; // 모든 조합

    public ArrayList<ArrayList<Position>> getResult() {
        return result;
    }

    public Combination(int n, int r) {
        this.n = n;
        this.r = r;
        this.now = new int[r];
        this.result = new ArrayList<ArrayList<Position>>();
    }

    public void combination(ArrayList<Position> arr, int depth, int index, int target) {
        if (depth == r) {
            ArrayList<Position> temp = new ArrayList<>();
            for (int j : now) {
                temp.add(arr.get(j));
            }
            result.add(temp);
            return;
        }
        if (target == n) return;    // 더 이상 선택할 요소가 없을 때
        now[index] = target;
        combination(arr, depth + 1, index + 1, target + 1); // 현재 요소를 포함하는 경우
        combination(arr, depth, index, target + 1);     // 포함하지 않는 경우
    }
}

class Position {
    private int x;
    private int y;

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

    public int getX() {
        return this.x;
    }

    public int getY() {
        return this.y;
    }
}

public class Main {

    public static int n; // 복도의 크기
    public static char[][] board = new char[6][6]; // 복도 정보 (N x N)
    public static ArrayList<Position> teachers = new ArrayList<>(); // 모든 선생님 위치 정보
    public static ArrayList<Position> spaces = new ArrayList<>(); // 모든 빈 공간 위치 정보

    // 특정 방향으로 감시를 진행 (학생 발견: true, 학생 미발견: false)
    public static boolean watch(int x, int y, int direction) {
        // 왼쪽 방향으로 감시
        if (direction == 0) {
            while (y >= 0) {
                if (board[x][y] == 'S') { // 학생이 있는 경우
                    return true;
                }
                if (board[x][y] == 'O') { // 장애물이 있는 경우
                    return false;
                }
                y -= 1;
            }
        }
        // 오른쪽 방향으로 감시
        if (direction == 1) {
            while (y < n) {
                if (board[x][y] == 'S') { // 학생이 있는 경우
                    return true;
                }
                if (board[x][y] == 'O') { // 장애물이 있는 경우
                    return false;
                }
                y += 1;
            }
        }
        // 위쪽 방향으로 감시
        if (direction == 2) {
            while (x >= 0) {
                if (board[x][y] == 'S') { // 학생이 있는 경우
                    return true;
                }
                if (board[x][y] == 'O') { // 장애물이 있는 경우
                    return false;
                }
                x -= 1;
            }
        }
        // 아래쪽 방향으로 감시
        if (direction == 3) {
            while (x < n) {
                if (board[x][y] == 'S') { // 학생이 있는 경우
                    return true;
                }
                if (board[x][y] == 'O') { // 장애물이 있는 경우
                    return false;
                }
                x += 1;
            }
        }
        return false;
    }

    // 장애물 설치 이후에, 한 명이라도 학생이 감지되는지 검사
    public static boolean process() {
        // 모든 선생의 위치를 하나씩 확인
        for (int i = 0; i < teachers.size(); i++) {
            int x = teachers.get(i).getX();
            int y = teachers.get(i).getY();
            // 4가지 방향으로 학생을 감지할 수 있는지 확인
            for (int j = 0; j < 4; j++) {
                if (watch(x, y, j)) {
                    return true;
                }
            }
        }
        return false;
    }

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

        n = sc.nextInt();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                board[i][j] = sc.next().charAt(0);
                // 선생님이 존재하는 위치 저장
                if (board[i][j] == 'T') {
                    teachers.add(new Position(i, j));
                }
                // 장애물을 설치할 수 있는 (빈 공간) 위치 저장
                if (board[i][j] == 'X') {
                    spaces.add(new Position(i, j));
                }
            }
        }

        // 빈 공간에서 3개를 뽑는 모든 조합을 확인
        Combination comb = new Combination(spaces.size(), 3);
        comb.combination(spaces, 0, 0, 0);
        ArrayList<ArrayList<Position>> spaceList = comb.getResult();

        // 학생이 한 명도 감지되지 않도록 설치할 수 있는지 여부
        boolean found = false;
        for (ArrayList<Position> positions : spaceList) {
            // 장애물들을 설치해보기
            for (Position pos : positions) {
                board[pos.getX()][pos.getY()] = 'O';
            }
            // 학생이 한 명도 감지되지 않는다면 성공
            if (!process()) {
                found = true;
                break;
            }
            // 장애물 제거 (백트래킹)
            for (Position pos : positions) {
                board[pos.getX()][pos.getY()] = 'X';
            }
        }
        System.out.println(found ? "YES" : "NO");
    }
}

 

 

 

 

동작 과정

 

1. 입력받기: 복도 크기 N과 선생님, 학생, 빈 칸 정보를 입력받아 저장.
2. 장애물을 설치할 수 있는 위치 찾기: 빈 칸(X)들의 좌표를 저장.
3. 모든 장애물 조합 생성: 빈 칸 중에서 3개를 선택하는 모든 경우의 수를 생성.
4. 각 조합에 대해 다음을 수행
   1. 장애물 설치
   2. 감시 실행
   3. 모든 학생이 감시를 피하면 "YES" 출력 후 종료
   4. 설치한 장애물 제거
5. 모든 경우의 수를 다 검사한 후, 감시를 피할 수 없으면 "NO" 출력