175.監視を避ける

1. Python

コンビネーション

from sys import stdin
from itertools import combinations
from copy import deepcopy

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]

n = int(input())
board = [list(map(str, stdin.readline().split())) for _ in range(n)]

emptys = []
teachers = []
students = []
for i in range(n):
    for j in range(n):
        if board[i][j] == 'X':
            emptys.append([i, j])
        elif board[i][j] == 'T':
            teachers.append([i, j])
        elif board[i][j] == 'S':
            students.append([i, j])


def DFS(board, x, y, idx):
    global n
    if x < 0 or x >= n or y < 0 or y >= n or board[x][y] == 'O':
        return
    else:
        board[x][y] = 'T' #선생님 상,하, 좌, 우로 세우기
        DFS(board, x + dx[idx], y + dy[idx], idx)


def check():
    copy_board = deepcopy(board) #장애물 세운 뒤의 board
    for [x, y] in teachers:
        for i in range(4):
            DFS(copy_board, x, y, i)
    for [x, y] in students: #선생님 다 세웠는데 학생이 있던 자리가 선생으로 바뀌면 NO
        if copy_board[x][y] != 'S':
            return False

    return True #안바뀌면 YES


for case in list(combinations(emptys, 3)):
    for [x, y] in case:
        board[x][y] = 'O'
    if check():
        print("YES")
        exit()
    for [x, y] in case:
        board[x][y] = 'X'

print("NO")

DFS

n = int(input())

data = []
teacher = []
result = "NO"

# 상하좌우
dx = [-1,1,0,0]
dy = [0,0,-1,1]

for i in range(n):
    data.append(list(map(str, input().split())))
    for j in range(n):
        if data[i][j] == 'T':
            teacher.append((i,j))

def check():
    global teacher, data
    for t in teacher:
        for i in range(4):
            x, y = t
            while 0<= x < n and 0<= y < n:
                if data[x][y] == 'O':
                    break
                elif data[x][y] == 'S':
                    return False
                x += dx[i]
                y += dy[i]
    return True

def dfs(count):
    global teacher, data, result
    if count > 3:
        return
        
    if count == 3:
        if check():
            result = "YES"
            return
        else:
            result = "NO"
            
    
    for i in range(n):
        for j in range(n):
            if data[i][j] == 'X':
                data[i][j] = 'O'
                dfs(count+1)
                if result == "YES":
                    return
                data[i][j] = 'X'

dfs(0)
print(result)

コンポジット

from itertools import combinations

n = int(input()) # 복도의 크기
board = [] # 복도 정보 (N x N)
teachers = [] # 모든 선생님 위치 정보
spaces = [] # 모든 빈 공간 위치 정보

for i in range(n):
    board.append(list(input().split()))
    for j in range(n):
        # 선생님이 존재하는 위치 저장
        if board[i][j] == 'T':
            teachers.append((i, j))
        # 장애물을 설치할 수 있는 (빈 공간) 위치 저장
        if board[i][j] == 'X':
            spaces.append((i, j))

# 특정 방향으로 감시를 진행 (학생 발견: True, 학생 미발견: False)
def watch(x, y, direction):
    # 왼쪽 방향으로 감시
    if direction == 0:
        while y >= 0:
            if board[x][y] == 'S': # 학생이 있는 경우
                return True
            if board[x][y] == 'O': # 장애물이 있는 경우
                return False
            y -= 1
    # 오른쪽 방향으로 감시
    if direction == 1:
        while y < n:
            if board[x][y] == 'S': # 학생이 있는 경우
                return True
            if board[x][y] == 'O': # 장애물이 있는 경우
                return False
            y += 1
    # 위쪽 방향으로 감시
    if direction == 2:
        while x >= 0:
            if board[x][y] == 'S': # 학생이 있는 경우
                return True
            if board[x][y] == 'O': # 장애물이 있는 경우
                return False
            x -= 1
    # 아래쪽 방향으로 감시
    if direction == 3:
        while x < n:
            if board[x][y] == 'S': # 학생이 있는 경우
                return True
            if board[x][y] == 'O': # 장애물이 있는 경우
                return False
            x += 1
    return False

# 장애물 설치 이후에, 한 명이라도 학생이 감지되는지 검사
def process():
    # 모든 선생의 위치를 하나씩 확인
    for x, y in teachers:
        # 4가지 방향으로 학생을 감지할 수 있는지 확인
        for i in range(4):
            if watch(x, y, i):
                return True
    return False

find = False # 학생이 한 명도 감지되지 않도록 설치할 수 있는지의 여부

# 빈 공간에서 3개를 뽑는 모든 조합을 확인
for data in combinations(spaces, 3):
    # 장애물들을 설치해보기
    for x, y in data:
        board[x][y] = 'O'
    # 학생이 한 명도 감지되지 않는 경우
    if not process():
        # 원하는 경우를 발견한 것임
        find = True
        break
    # 설치된 장애물을 다시 없애기
    for x, y in data:
        board[x][y] = 'X'

if find:
    print('YES')
else:
    print('NO')

2. C++

#include <bits/stdc++.h>

using namespace std;

int n; // 복도의 크기
char board[6][6]; // 복도 정보 (N x N)
vector<pair<int, int> > teachers; // 모든 선생님 위치 정보
vector<pair<int, int> > spaces; // 모든 빈 공간 위치 정보

// 특정 방향으로 감시를 진행 (학생 발견: true, 학생 미발견: false)
bool watch(int x, int y, int direction) {
    // 왼쪽 방향으로 감시
    if (direction == 0) {
        while (y >= 0) {
            if (board[x][y] == 'S') { // 학생이 있는 경우
                return true;
            }
            if (board[x][y] == 'O') { // 장애물이 있는 경우
                return false;
            }
            y -= 1;
        }
    }
    // 오른쪽 방향으로 감시
    if (direction == 1) {
        while (y < n) {
            if (board[x][y] == 'S') { // 학생이 있는 경우
                return true;
            }
            if (board[x][y] == 'O') { // 장애물이 있는 경우
                return false;
            }
            y += 1;
        }
    }
    // 위쪽 방향으로 감시
    if (direction == 2) {
        while (x >= 0) {
            if (board[x][y] == 'S') { // 학생이 있는 경우
                return true;
            }
            if (board[x][y] == 'O') { // 장애물이 있는 경우
                return false;
            }
            x -= 1;
        }
    }
    // 아래쪽 방향으로 감시
    if (direction == 3) {
        while (x < n) {
            if (board[x][y] == 'S') { // 학생이 있는 경우
                return true;
            }
            if (board[x][y] == 'O') { // 장애물이 있는 경우
                return false;
            }
            x += 1;
        }
    }
    return false;
}

// 장애물 설치 이후에, 한 명이라도 학생이 감지되는지 검사
bool process() {
    // 모든 선생의 위치를 하나씩 확인
    for (int i = 0; i < teachers.size(); i++) {
        int x = teachers[i].first;
        int y = teachers[i].second;
        // 4가지 방향으로 학생을 감지할 수 있는지 확인
        for (int i = 0; i < 4; i++) {
            if (watch(x, y, i)) {
                return true;
            }
        }
    }
    return false;
}

bool found; // 학생이 한 명도 감지되지 않도록 설치할 수 있는지의 여부

int main(void) {
    cin >> n;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> board[i][j];
            // 선생님이 존재하는 위치 저장
            if (board[i][j] == 'T') {
                teachers.push_back({i, j});
            }
            // 장애물을 설치할 수 있는 (빈 공간) 위치 저장
            if (board[i][j] == 'X') {
                spaces.push_back({i, j});
            }
        }
    }

    // 빈 공간에서 3개를 뽑는 모든 조합을 확인
    vector<bool> binary(spaces.size());
    fill(binary.end() - 3, binary.end(), true);
    do {
        // 장애물들을 설치해보기
        for (int i = 0; i < spaces.size(); i++) {
            if (binary[i]) {
                int x = spaces[i].first;
                int y = spaces[i].second;
                board[x][y] = 'O';
            }
        }
        // 학생이 한 명도 감지되지 않는 경우
        if (!process()) {
            // 원하는 경우를 발견한 것임
            found = true;
            break;
        }
        // 설치된 장애물을 다시 없애기
        for (int i = 0; i < spaces.size(); i++) {
            if (binary[i]) {
                int x = spaces[i].first;
                int y = spaces[i].second;
                board[x][y] = 'X';
            }
        }
    } while(next_permutation(binary.begin(), binary.end()));

    if (found) cout << "YES" << '\n';
    else cout << "NO" << '\n';
}