백준 18428. 감시 피하기 (구현)

https://www.acmicpc.net/problem/18428

18428번: 감시 피하기

3개의 장애물을 설치하여 모든 학생들을 감시로부터 피할 수 있는지 여부를 출력하는 문제이다. 

나는 장애물을 놓을 수 있는 곳인 'x'중 3개를 뽑아서 그곳에 장애물을 설치하고, 이 때 학생들이 감시를 피할 수 있는지 여부를 판별했다. 그리고 이를 조합의 횟수만큼 반복했다. 

대충 계산을 해보았을 때, 34C3 (3<= n <= 6, t와 s 최솟값 1)* 5(1<= t <=5)정도 이므로 시간 초과는 나지 않는다.

 

1. 특징

1) 조합

2) 구현

 

2. 코드

#include <bits/stdc++.h>
using namespace std;

int n;
char board[7][7];
char tmp[7][7];
pair<int, int> xarr[50];
int mask[50];
vector<pair<int, int>> _vec;

bool Up(int x, int y)
{
    while(x > 0)
    {
        x--;
        if(tmp[x][y] == 'S')
            return true;
        if(tmp[x][y] == 'O')
            return false;
    }
    return false;
}

bool Down(int x, int y)
{
    while(x < n-1)
    {
        x++;
        if(tmp[x][y] == 'S')
            return true;
        if(tmp[x][y] == 'O')
            return false;
    }
    return false;
}

bool Right(int x, int y)
{
    while(y < n-1)
    {
        y++;
        if(tmp[x][y] == 'S')
            return true;
        if(tmp[x][y] == 'O')
            return false;
    }
    return false;
}

bool Left(int x, int y)
{
    while(y > 0)
    {
        y--;
        if(tmp[x][y] == 'S')
            return true;
        if(tmp[x][y] == 'O')
            return false;
    }
    return false;
}


int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    int xsize = 0;

    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            cin >> board[i][j];
            if(board[i][j] == 'X')
            {
                xarr[xsize].first = i;
                xarr[xsize].second = j;
                xsize++;
            }
            if(board[i][j] == 'T')
            {
                _vec.push_back(make_pair(i, j));
            }

        }
    }


    bool isComp = false;
    // xsize 에서 3자리 고르기
    for(int i = 3; i < xsize ; i++)
    {
        mask[i] = 1;
    }

    do
    {
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < n; j++)
            {
                tmp[i][j] = board[i][j];
            }
        }


        for(int i = 0; i < xsize; i++)
        {
            if(mask[i] == 0)
            {
                int x = xarr[i].first;
                int y = xarr[i].second;
                tmp[x][y] = 'O';
            }
        }

        isComp = false;
        for(int i = 0; i < _vec.size(); i++)
        {
            int x = _vec[i].first;
            int y = _vec[i].second;

            isComp = isComp || Up(x, y) || Down(x, y) || Right(x, y) || Left(x, y);
        }
        
        if(isComp == false)
        {
            
            cout << "YES";
            return 0;
        }


    }while(next_permutation(mask, mask + xsize));

    cout << "NO";

}