[ 백준 18428 ] 감시 피하기 (c/c++)

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

 

 

[ 문제 요약 ]

선생님은 장애물의 뒷편을 감시하지 못하고, 학생과 선생님과 장애물의 위치가 주어질 때, 정확히 장애물 3개를 설치하여 모든 학생들이 감시로 피할 수 있는 지 여부를 출력한다.

 

 

[ 문제 풀이 ]

1. 주어지는 N의 최대 크기가 6이기 때문에 완전 탐색을 할 수 있다.

2. X가 주어지는 곳을 기록한 뒤, DFS를 이용하여 가능한 장애물의 배치를 모두 시도해 본다.

3. 선생님의 시선을 늘려가면서 만약 학생이 있다면 그 경우는 실패이다.

4. 모든 경우를 했을 때에도 성공한 적이 없으면 NO, 아니면 YES를 출력한다.

 

 

[ 소스 코드 ]

#include <bits/stdc++.h>
using namespace std;

int N;
char arr[10][10];
vector<pair<int, int>> teacher;
vector<pair<int, int>> none;

int d[][2] = { {-1,0},{1,0},{0,1},{0,-1} };

int Find(int x, int y) {
    for (int i=0; i<4; i++){
        int nx = x, ny = y;
        while (nx>=0 && ny>=0 && nx<N && ny<N){
            if (arr[nx][ny] == 'O') break;
            if (arr[nx][ny] == 'S') return 0;
            nx = nx + d[i][0];
            ny = ny + d[i][1];
        }
    }
    return 1;
}

void allSet(int cnt, int idx) {
    if (cnt == 3) {
        for (auto i : teacher) if (!Find(i.first, i.second)) return;
        cout << "YES";
		exit(0);
    }

    for (int i=idx; i<none.size(); i++){
        arr[none[i].first][none[i].second] = 'O';
        allSet(cnt + 1, i + 1);
        arr[none[i].first][none[i].second] = 'X';
    }
}

int main() {
    cin >> N;
    for (int i=0; i<N; i++){
        for (int j=0; j<N; j++){
            cin >> arr[i][j];
            if (arr[i][j] == 'T') teacher.push_back(make_pair(i, j));
            if (arr[i][j] == 'X') none.push_back(make_pair(i, j));
        }
    }
    allSet(0, 0);
    cout << "NO";
    
    return 0;
}

 

 

 

[ 주의할 점 ]

N의 최대값이 6이기 때문에 완전 탐색이 가능하다는 것을 늦게 알아차려 조금 걸렸다.