18428: 감시 피하기

문제 링크

18428: 감시 피하기

구현 방식

• 3개의 장애물을 설치하는 경우를 모두 고려하여 brute force로 풀어주었다
• 3개의 장애물을 설치하는 부분을 backtracking을 이용해서 구현해주었다
  • if o_cnt == 3이면, check() 호출하여 감시 피할 수 있는 지의 여부 검사
  • else, backtracking 방식으로 재귀 호출

코드

#include <iostream>
#include <vector>
#include <queue>
#include <limits.h>
using namespace std;

#define INF INT_MAX
#define MAX 6

int dx[4] = {0, 0, -1, 1};
int dy[4] = {-1, 1, 0, 0};

int N;
char board[MAX][MAX];
bool answer = false;
vector<pair<int, int> > teachers;

bool check(){
    queue<pair<int, int> > q;
    for (int i=0; i<teachers.size(); i++){
        q.push(make_pair(teachers[i].first, teachers[i].second));
    }
    
    while (!q.empty()){
        int x = q.front().first;
        int y = q.front().second;
        q.pop();

        for (int i=0; i<4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            while (0 <= nx && nx < N && 0 <= ny && ny < N){
                if (board[nx][ny] == 'S'){
                    return false;
                }
                else if (board[nx][ny] == 'T' || board[nx][ny] == 'O'){
                    break;
                }
                nx += dx[i];
                ny += dy[i];
            }
        }
    }
    return true;
}

void backtracking(int o_cnt){
    if (o_cnt == 3){
        if (check()){
            answer = true;
            return;
        }
    }
    else{
        for (int i=0; i<N; i++){
            for (int j=0; j<N; j++){
                if (board[i][j] == 'X'){
                    board[i][j] = 'O';
                    backtracking(o_cnt+1);
                    board[i][j] = 'X';
                }
            }
        }
    }
}

int main() {
    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(make_pair(i, j));
            }
        }
    }

    backtracking(0);
    if (answer) {
        cout << "YES\n";
    }
    else{
        cout << "NO\n";
    }

    return 0;
}

import sys
from collections import deque

dx = (0, 0, -1, 1)
dy = (-1, 1, 0, 0)

def backtracking(o_cnt):
    global answer

    if o_cnt == 3:
        if check():
            answer = True; return
    else:
        for i in range(N):
            for j in range(N):
                if board[i][j] == 'X':
                    board[i][j] = 'O'
                    backtracking(o_cnt+1)
                    board[i][j] = 'X'

def check():
    q = deque(teachers)
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]; ny = y + dy[i]
            while 0 <= nx < N and 0 <= ny < N:
                if board[nx][ny] == 'S': return False
                elif board[nx][ny] == 'T' or board[nx][ny] == 'O': break
                nx += dx[i]; ny += dy[i]
    return True

N = int(sys.stdin.readline()[:-1])
board = [list(sys.stdin.readline()[:-1].split()) for n in range(N)]

teachers = []
for i in range(N):
    for j in range(N):
        if board[i][j] == 'T':
            teachers.append((i, j))

answer = False
backtracking(0)
if answer: print("YES")
else: print("NO")