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

백준 18428 감시 피하기 Gold V - JAVA 📌

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

문제 설명

문제 풀이

---

접근 💡

2차원 배열에서 주어지는 정보는 선생님의 위치와 학생의 위치이다. 장애물을 빈 칸에 세 개를 놓았을 때 감시를 피할 수 있는 경우를 찾아야 한다.

 

장애물을 3개 놓는 경우는 조합으로 생각하면 된다. 빈칸의 좌표를 리스트로 받아서 그 리스트 안에서 조합을 뽑아 모든 경우의 수를 탐색할 수 있다.

이 때 빈칸의 최소 갯수는 3개이고 최대 갯수는 선생님의 최소 수는 1, 학생의 최소 수는 1 이다. N의 최댓값이 6이므로 6 * 6 = 36, 36 - 2 = 34,  34C3의 경우의 수가 생긴다. 이는 5,984의 경우의 수가 생기며 이는 완전탐색 하기에 충분한 경우의 수이다.

 

백트래킹을 통해 장애물의 위치를 계속 갱신해 주면 된다. 

코드 💡

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static class Point {
        int r;
        int c;

        public Point(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }

    static int N;
    static List<Point> traps, teachers;
    static boolean success;
    static char[][] map;
    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        map = new char[N][N];
        traps = new ArrayList<>();
        teachers = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                map[i][j] = st.nextToken().charAt(0);
                if (map[i][j] == 'X') {
                    traps.add(new Point(i, j));
                } else if (map[i][j] == 'T') {
                    teachers.add(new Point(i, j));
                }
            }
        }

        // 함정의 조합을 뽑는다.
        success = false;
        combination(0, 0);
        if (success) System.out.println("YES");
        else System.out.println("NO");

    }

    private static void combination(int idx, int depth) {
        if (depth == 3) {
            if (check()) {
                success = true;
            }
            return;
        }

        for (int i = idx; i < traps.size(); i++) {
            Point p = traps.get(i);
            map[p.r][p.c] = 'O';
            combination(i + 1, depth + 1);
            if (success) return;
            map[p.r][p.c] = 'X';
        }
    }

    private static boolean check() {
        for (Point teacher : teachers) {
            for (int dir = 0; dir < 4; dir++) {
                int nr = teacher.r;
                int nc = teacher.c;

                while (true) {
                    nr += dr[dir];
                    nc += dc[dir];

                    if (0 > nr || nr >= N || 0 > nc || nc >= N) break;
                    if (map[nr][nc] == 'O') break;
                    if (map[nr][nc] == 'S') return false;
                }
            }
        }

        return true;
    }
}