백준 18428번 감시 피하기[골드 5][C++]

1. 개요

 안녕하세요. 이 문제의 유형은 브루트포스, 백트래킹입니다. 모든 경우의 수를 도입해 보고 정답을 구할 수 있는지 확인해 보시면 됩니다. 이 문제에서 경우의 수는 N * N 크기의 복도 빈칸 세 곳을 결정하는 개수를 의미하겠죠. N은 6 이하까지 가능하니깐 최악의 경우는 36C3이 됩니다. 또 세 곳만 결정하면 되니깐 삼중 for loop로 풀이하셔도 무방합니다. 하지만 벽을 세울 곳이 5가지나 그 이상이라면 백트래킹이 더 간편하겠죠. 

 

2. 문제 풀이

2 - 1. 벽 위치 결정하기

 위 설명과 같이 삼중 for loop나 백트래킹을 사용해서 빈 칸 세 곳을 벽으로 결정하시면 됩니다. 최악의 경우 시간복잡도는 O(36C3) = O(28,560)가 됩니다. 

 

2 - 2. 학생 감지하기

 선생님들이 놓인 위치에서 상하좌우 방향으로 장애물이 있는 곳 전까지 학생들을 감시합니다. 즉 선생님들의 위치에서 배열의 범위에서 벗어나거나 장애물이 만나기 전까지 상하좌우 방향으로 이동하면서 학생이 있는지 검사하면 됩니다. bfs에서 사용하는 dx, dy 등의 배열을 가지고 구현할 수 있습니다.

 

3. 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> pi; typedef pair<ll, ll> pl;
typedef tuple<int, int, int> ti; typedef tuple<ll, ll, ll> tl; typedef vector<int> vi; typedef vector<ll> vl;
typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<ti> vti; typedef vector<tl> vtl;
typedef vector<string> vs; typedef vector<bool> vb; typedef queue<int> qi; typedef queue<ll> ql;
typedef queue<pi> qpi; typedef queue<pl> qpl; typedef queue<ti> qti; typedef queue<tl> qtl;
#define fastio(x, y) cin.tie((x))->sync_with_stdio((y))
#define X first
#define Y second
#define pb push_back
#define sz(x) (int((x).size()))
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
const char nl = '\n';

const int dx[]{1, 0, -1, 0};
const int dy[]{0, 1, 0, -1};

int n;
vector<vector<char>> board;

vpi teacher, wall;
vb isused;

bool detect() {
    for(auto [tx, ty] : teacher) {
        for(int dir = 0; dir < 4; dir++) {
            int nx = tx + dx[dir];
            int ny = ty + dy[dir];
            while(0 <= nx && nx < n && 0 <= ny && ny < n && board[nx][ny] != 'O') {
                if(board[nx][ny] == 'S') {
                    return 1;
                }
                nx += dx[dir];
                ny += dy[dir];
            }
        }
    }
    return 0;
}

bool solve(int idx, int k) {
    if(k == 3) {
        return !detect();
    }
    
    bool ret{};
    for(int i = idx; i < sz(wall); i++) {
        if(!isused[i]) {
            isused[i] = 1;
            board[wall[i].X][wall[i].Y] = 'O';
            ret |= solve(i, k + 1);
            board[wall[i].X][wall[i].Y] = 'X';
            isused[i] = 0;
        }
    }       
    return ret;
}

int main() {
    fastio(nullptr, false);

    cin >> n;
    vector<vector<char>>(n, vector<char>(n)).swap(board);
    
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            cin >> board[i][j];
            if(board[i][j] == 'X') {
                wall.pb({i, j});
            }
            if(board[i][j] == 'T') {
                teacher.pb({i, j});
            }
        }
    }

    vb(sz(wall)).swap(isused);
    cout << (solve(0, 0) ? "YES" : "NO");
}

 

4. 제출 결과