18428. 감시 피하기

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

18428번: 감시 피하기

 

1. 재귀를 이용한 dfs로 선생님과, 학생이 없는 곳에 장애물을 놓을수 있는 모든 경우를 구한다

2. 모든 경우에 대하여 선생님의 4방향 시선 경로에 학생이 있는지 판단한다

3. 한 번이라도 숨을수 있는 경우가 있으면 YES

 

#include <iostream>
#include <algorithm>
#include <vector>
#define endl '\n'
using namespace std;

int n;
char map[7][7];
vector<pair<int,int>> tl; // teacher's location
int dr[4] = {-1, 0, 1, 0};
int dc[4] = {0, 1, 0, -1};
bool ans = false;

// 숨을수 있으면 true
bool CanHide()
{
    for(int t = 0; t < tl.size(); t++)
    {
        int tr = tl[t].first;
        int tc = tl[t].second;

        // 4방향 탐색
        for(int i = 0; i < 4; i++)
        {
            int _tr = tr + dr[i];
            int _tc = tc + dc[i];

            while(_tr >= 0 && _tr < n && _tc >= 0 && _tc < n)
            {
                // 시선경로에 벽이 있으면 더이상 탐색 불가능
                if(map[_tr][_tc] == 'O') break;
                // 학생을 찾음
                if(map[_tr][_tc] == 'S')
                {
                    return false;
                }

                _tr += dr[i];
                _tc += dc[i];
            }
        }
    }
    return true;
}

void MakeWalls(int depth)
{
    if(ans) return;

    if(depth == 3)
    {
        if(CanHide())
        {
            ans = true;
        }

        return;
    }

    for(int i = 0; i < n; i++)
    {
        for(int j = 0; j < n; j++)
        {
            if(map[i][j] == 'T' || map[i][j] == 'S' || map[i][j] == 'O') continue;

            map[i][j] = 'O';
            MakeWalls(depth+1);
            map[i][j] = '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')
                tl.push_back({i,j});
        }
    }

    MakeWalls(0);

    if(ans)
        cout << "YES";
    else
        cout << "NO";
}