[백준 18428번] 감시 피하기

이번 문제는 브루트포스 문제 중에서 조합과 백트래킹을 사용해서 해결하는 문제이다.

N의 범위가 3 <= N <= 36 이고, 최소 1개는 선생님, 1개는 학생이므로 34개의 빈칸 중에서 3개의 장애물을 설치한 뒤에 감시를 피할 수 있는지 여부를 확인하면 되는 문제이다.

 

처음에 문제를 풀었을 때는 순열을 이용해서 장애물을 동일한 위치에 설치하는 경우도 모두 포함해서 풀었다. 조합을 이용해서 장애물을 설치할 위치를 구한다면 중복적인 위치를 탐색할 필요가 없어지기 때문에 효율적인 탐색이 가능하다.

 

2차원 배열에서 조합으로 선택하는 방법은 인덱스를 N*N으로 구하면 된다. 즉, 2차원 배열로 이루어진 것을 1차원 배열로 생각해서 하나씩 선택하는 것이다.

 

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

public class Solution_for_18428 {
    static int N;
    static char[][] map;
    static List<Teacher> teachers = new ArrayList<>();

    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());
        map = new char[N][N];

        for (int n = 0; n < N; n++) {
            st = new StringTokenizer(br.readLine());

            for (int m = 0; m < N; m++) {
                char c = st.nextToken().charAt(0);

                // 탐색을 시작할 선생님의 위치
                if (c == 'T') {
                    teachers.add(new Teacher(n, m));
                }

                map[n][m] = c;
            }
        }

        comb(0, 0);
        System.out.println("NO");
    }
    
    public static void comb(int idx, int cnt) {
        if (cnt == 3) {
            if (hidePossible()) {
                System.out.println("YES");
                System.exit(0);
            }
            return;
        }

        if (idx == N * N) return;

        int r = idx / N;
        int c = idx % N;

        if (map[r][c] == 'X') {
            map[r][c] = 'O';

            comb(idx + 1, cnt + 1);

            map[r][c] = 'X';
        }

        comb(idx + 1, cnt);
    }

    public static boolean hidePossible() {

        for (Teacher t : teachers) {
            int startRow = t.row;
            int startCol = t.col;

            // O가 나오거나 배열의 끝 부분에 도달하면 종료
            // 상
            for (int i = startRow; 0 <= i; i--) {
                if (map[i][startCol] == 'O') break;
                if (map[i][startCol] == 'S') return false;
            }
            // 하
            for (int i = startRow; i < N; i++) {
                if (map[i][startCol] == 'O') break;
                if (map[i][startCol] == 'S') return false;
            }
            // 좌
            for (int j = startCol; 0 <= j; j--) {
                if (map[startRow][j] == 'O') break;
                if (map[startRow][j] == 'S') return false;
            }
            // 우
            for (int j = startCol; j < N; j++) {
                if (map[startRow][j] == 'O') break;
                if (map[startRow][j] == 'S') return false;
            }
        }

        return true;
    }

    public static class Teacher {
        int row;
        int col;

        Teacher(int row, int col) {
            this.row = row;
            this.col = col;
        }
    }
}