1. Python
조합, DFS
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';
}
For the sake of someone who studies computer science