백준 18428 감시 피하기 (C++)

18428번: 감시 피하기

완전 탐색을 이용한 문제이다. 먼저 맵을 입력받을 때 빈칸과 선생님의 위치를 따로 저장을 해준다. 그리고 재귀를 돌면서 빈칸에 장애물을 하나씩 추가해주면서 3개가 됬을 때 선생님의 위치 기준으로 학생이 보이는지 확인해주었다. 아이디어만 떠올리면 간단하게 풀 수 있는 문제이다. 처음에는 선생님의 위치 기준으로 학생이 보이는 바로 전 위치에 1씩 더해주어 겹치는 부분을 장애물로 막으면 된다고 생각하였는데 이렇게 할 경우 겹치는 부분이 아니라 다른 곳에 장애물이 있어도 YES가 되는 경우를 찾지 못해 실패를 했었다. 더 많은 문제를 풀어봐야 겠다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N;
char A[6][6];
int dy[4] = { -1,1,0,0 };
int dx[4] = { 0,0,-1,1 };
string result = "NO";
bool tf;
vector<pair<int, int>> T;
vector<pair<int, int>> X;

void checkResult(int y, int x, int d) {
    int ny = y + dy[d];
    int nx = x + dx[d];

    if (ny < 0 || nx < 0 || ny >= N || nx >= N) return;
    if (A[ny][nx] == 'O') return;
    if (A[ny][nx] == 'S') {
        tf = false;
        return;
    }

    checkResult(ny, nx, d);
}

void selectO(int n) {
    if (n == 3) {
        tf = true;

        for (int i = 0; i < T.size(); i++) {
            int y = T[i].first;
            int x = T[i].second;

            for (int j = 0; j < 4; j++) {
                checkResult(y, x, j);
            }
        }

        if (tf) result = "YES";

        return;
    }

    for (int i = 0; i < X.size(); i++) {
        int y = X[i].first;
        int x = X[i].second;

        if (A[y][x] == 'O') continue;

        A[y][x] = 'O';
        selectO(n + 1);
        A[y][x] = 'X';
    }
}

void solution() {
    selectO(0);
    cout << result;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> N;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> A[i][j];

            if (A[i][j] == 'T')
                T.push_back({ i,j });
            else if (A[i][j] == 'X')
                X.push_back({ i,j });
        }
    }

    solution();

    return 0;
}