[18428] 감시 피하기

감시 피하기

사용한 알고리즘 : 브루트 포스 + 백트래킹
gamsi()의 반환값으로 전부 감시를 피할 수 없는지, 있는지 판단한다.

#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
using namespace std;
int n, res = 0;
char map[7][7];
int dx[4] = {0, 1, 0, -1};
int dy[4] = {-1, 0, 1, 0};
vector<pair<int, int> > teacher;
vector<pair<int ,int> > obstacle;

int gamsi()
{
    for(pair<int ,int> t : teacher)
    {
        for(int dir = 0; dir < 4; dir++)
        {
            int nx = t.first;
            int ny = t.second;
            while (1)
            {
                nx += dx[dir];
                ny += dy[dir];
                if(nx < 0 || nx >= n || ny < 0 || ny >= n || map[nx][ny] == 'O') break ;
                if(map[nx][ny] == 'S')
                {
                    return 0; // 감시 피할 수 없음 
                }
            }
        }
    }
    return 1; // 감시 피함
}

void make_obstacle(int cur, int cnt)
{
    if(cnt == 3)
    {
        res += gamsi();  // ⭐️
        return ;
    }

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

        map[x][y] = 'O';
        make_obstacle(i+1, cnt+1);
        map[x][y] = 'X';
    }

}

int main()
{
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j<n; j++)
        {
            cin >> map[i][j];
            if(map[i][j] == 'T')
                teacher.push_back({i,j});
            else if(map[i][j] == 'X')
                obstacle.push_back({i,j});
        }
    }
    make_obstacle(0,0);

    if(res == 0)  // ⭐️
        cout << "NO";
    else
        cout << "YES";
    return 0;
}

📌 python 코드
알고리즘 : 브루트 포스 + 조합

from collections import deque
from itertools import combinations
import copy
dx = [-1, 0, 1, 0]
dy = [0, 1, 0 ,-1]

n = int(input())
board = [list(input().split()) for _ in range(n)]
teacher =[]
empty = []

def bfs():
    test = copy.deepcopy(board)
    q = deque(teacher)
    
    while q:
        curX, curY = q.popleft()
        for dir in range(4):
            tmp_x, tmp_y = curX, curY
            while True:  # 한 방향으로 쭉
                nx = tmp_x + dx[dir]
                ny = tmp_y + dy[dir]
                if 0 <= nx < n and 0 <= ny < n:
                    if test[nx][ny] == 'X':
                        test[nx][ny] == 'T'
                    elif test[nx][ny] == 'O':
                        break
                    elif test[nx][ny] == 'S':  # 학생을 찾았다
                        return False
                    tmp_x, tmp_y = nx, ny
                else:  # test를 벗어남, 방향을 바꾸자
                    break
    return True  # 학생을 못찾았다 (모든 학생들을 감시로부터 피하도록 할 수 있다)

for i in range(n):
    for j in range(n):
        if board[i][j] == 'T':
            teacher.append([i,j])
        elif board[i][j] == 'X':
            empty.append([i,j])

check = False
for wall in list(combinations(empty, 3)):
    for x, y in wall:
        board[x][y] = 'O'
    if bfs() == True:
        check = True
        break
    for x, y in wall:
        board[x][y] = 'X'

if check:
    print("YES")
else:
    print("NO")