20.감시 피하기

📍 문제 설명

💡 접근

치킨 배달문제와 유사한 조합뽑기 문제

장애물을 세운뒤 감지를 하고 장애물을 없애는 작업도 필요하다.

 

1.모든 빈칸에 대해서 장애물을 3개 뽑고 세우기
2.장애물을 3개 뽑았다면 해당 위치의 좌표에 장애물을 세운다.
3.모든 선생님의 위치에서 상하좌우를 쭉 확인하여 학생를 감지한다.

4.한번이라도 감지가 되면 NO

👩‍💻 코드

import java.util.*;

public class Main {
    static ArrayList<Position> teachers = new ArrayList<>();
    static ArrayList<Position> spaces = new ArrayList<>();
    static int[] combi;
    static int n,spaceLen;
    static char[][] map;
    static boolean found;
    public static void main(String[] args) {
        Scanner kb = new Scanner(System.in);

        n = kb.nextInt();

        //선생님 T 학생 S 장애물 O
        map = new char[n][n];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                map[i][j] = kb.next().charAt(0);
                //선생님의 위치 저장(이 위치에서 출발)
                if(map[i][j] == 'T') teachers.add(new Position(i, j));
                if(map[i][j] == 'X') spaces.add(new Position(i, j));
            }
        }

        //빈칸의 총 갯수 중에 3개를 뽑아야한다
        spaceLen = spaces.size();
        combi = new int[3];
        //장애물 3개 세우기위한 함수
        solution(0,0);
        if(found) System.out.println("YES");
        else System.out.println("NO");
    }

    private static void solution(int L, int s) {
        //장애물 세울 수 있는 횟수를 다 뽑으면
        if(L == 3) {
            //선생님의 학생 감지 여부
            found = false;
            //장애물 설치하기
            for(int i : combi) {
                int x = spaces.get(i).x;
                int y = spaces.get(i).y;
                map[x][y] = 'O';
            }

            //장애물 설치 후 각 선생님의 위치에서 상하좌우 쭉 확인
            //참이 아닌 경우가 학생이 한 명도 감지되지 않는 경우임
            if(!process()) {
                found = true;
                return;
            }

            //장애물 다시 없애기
            for(int i : combi) {
                int x = spaces.get(i).x;
                int y = spaces.get(i).y;
                map[x][y] = 'X';
            }

        }
        else {
            //3개 뽑기
            for(int i = s; i < spaceLen; i++) {
                combi[L] = i;
                solution(L+1,i+1);
            }
        }
    }

    // 장애물 설치 이후에, 한 명이라도 학생이 감지되는지 검사
    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++) {
                //한번이라도 감지되면 true를 리턴
                if (watch(x, y, j)) {
                    return true;
                }
            }
        }
        return false;
    }

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

    static 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;
        }

        @Override
        public String toString() {
            return "Position{" +
                    "x=" + x +
                    ", y=" + y +
                    '}';
        }
    }
}