문제 푼 날짜 : 2021-12-02

문제

문제 링크 : https://www.acmicpc.net/problem/18428

접근 및 풀이

입력의 크기가 크지 않아서 백트래킹으로 구현해도 큰 문제가 없었다.
아래의 생각대로 코드를 구현하였다.

1. 입력을 받으면서 선생님이 계신 자리를 다 저장해둔다.
2. 'X'의 위치마다 'O'(벽)를 놓아본다.
3. 'O'가 3개 놓아졌으면 선생님이 계신 모든 자리에서 가로, 세로로 학생들을 마주칠 수 있는지 체크해준다.
4. 아무도 마주치지 않으면 그대로 "YES"를 출력하고 프로그램을 종료해준다.
5. 아니면 다시 2번 부터 반복해준다.
6. 모든 경우에서 "YES"가 나오지 않으면 "NO"를 출력해준다.

코드

// 백준 18428번 : 감시 피하기
#include <bits/stdc++.h>

using namespace std;

int N;
char arr[7][7];
vector<pair<int, int>> v;
int D[4][2] = { { -1, 0 }, { 0, 1 }, { 1, 0 }, { 0, -1 } };

bool isValid() {
    for (auto pos : v) {
        for (int i = 0; i < 4; i++) {
            int y = pos.first;
            int x = pos.second;
            while (y >= 0 && y < N && x >= 0 && x < N) {
                if (arr[y][x] == 'S') {
                    return false;
                }
                if (arr[y][x] == 'O') {
                    break;
                }
                y += D[i][0];
                x += D[i][1];
            }
        }
    }
    return true;
}

void dfs(int cnt) {
    if (cnt == 3) {
        if (isValid()) {
            cout << "YES";
            exit(0);
        }
        return;
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (arr[i][j] == 'X') {
                arr[i][j] = 'O';
                dfs(cnt + 1);
                arr[i][j] = 'X';
            }
        }
    }
}

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

    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') {
                v.push_back(make_pair(i, j));
            } 
        }
    }
    dfs(0);
    cout << "NO";
    return 0;
}

결과