[백준] 18428 감시 피하기

18428번: 감시 피하기

 

www.acmicpc.net

풀이

순열을 구현해서 3개의 장애물을 설치하고 감시를 피할 수 있는지 확인해주면 된다. c++에서는 DFS를 통해 순열을 구현했고, Python3에서는 combinations() 함수를 사용해서 구현했다.

코드

#include <iostream>
#include <vector>
using namespace std;

int n, answer;
const int dx[] = { -1, 0, 1, 0 }, dy[] = { 0, -1, 0, 1 };
vector<pair<int, int>> cand, teachers;
char board[6][6];

// 감시 피할 수 있는지 체크하는 함수
int check() {
    for (pair<int, int> t : teachers) {
        for (int i = 0; i < 4; i++) {
            int nx = t.first;
            int ny = t.second;
            while (true) {
                nx += dx[i];
                ny += dy[i];
                if (nx <0 || nx > n - 1 || ny < 0 || ny > n - 1 || board[ny][nx] == 'O') break;
                if (board[ny][nx] == 'S') return 0;
            }
        }
    }
    return 1;
}

// DFS 사용해서 장애물 설치
void dfs(int idx, int cnt) {
    if (cnt == 3) {
        answer += check();
        return;
    }

    for (int i = idx + 1; i < cand.size(); i++) {
        int x = cand[i].first;
        int y = cand[i].second;
        board[y][x] = 'O';
        dfs(i, cnt + 1);
        board[y][x] = '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 >> board[i][j];
            if (board[i][j] == 'X') cand.push_back({ j, i });
            else if (board[i][j] == 'T') teachers.push_back({ j, i });
        }
    dfs(-1, 0);
    if (answer == 0) cout << "NO\n";
    else cout << "YES\n";
    return 0;
}

Python3

import sys
from itertools import combinations

n = int(sys.stdin.readline().rstrip())
board = []  # 복도 저장 리스트
cand = []  # 빈 공간 저장할 리스트
teachers = []  # 선생님들 위치를 저장할 리스트

for i in range(n):
    board.append(list(sys.stdin.readline().rstrip().split()))
    for j in range(n):
        if board[i][j] == 'X':
            cand.append((j, i))
        elif board[i][j] == 'T':
            teachers.append((j, i))

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


# 빈 공간 3개를 선택해 장애물을 설치
def set_obstacles():
    for obs in combinations(cand, 3):
        for x, y in obs:
            board[y][x] = 'O'

        global answer
        answer += check()
        if answer > 0: break

        for x, y in obs:
            board[y][x] = 'X'


# 감시를 피할 수 있는지 체크하는 함수
def check():
    for t in teachers:
        for i in range(4):
            nx = t[0]
            ny = t[1]
            while True:
                nx += dx[i]
                ny += dy[i]
                if (nx < 0 or nx > n - 1 or ny < 0 or ny > n - 1 or board[ny][nx] == 'O'):
                    break
                if board[ny][nx] == 'S':
                    return 0
    return 1


set_obstacles()

if answer == 0:
    print('NO')
else:
    print('YES')