[Algorithm]Baekjoon 18428번 :: 감시 피하기

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

18428번: 감시 피하기

struct Node
{
    int y;
    int x;
};
 
int dir[4][2] = { {-1,0}, {1,0}, {0,-1}, {0,1} };
char arr[7][7];
vector<int> v;
int n;
vector<Node> teachersInfo;
bool isBreak = false;
 
 
bool Check() // 모든 선생에 대해서 한번이라도 학생발견하면 return false;하고 전부종료
{
    for (int i = 0; i < teachersInfo.size(); ++i)
    {
        for (int j = 0; j < 4; ++j)
        {
            int curDirY = dir[j][0];
            int curDirX = dir[j][1];
 
            int curY = teachersInfo[i].y;
            int curX = teachersInfo[i].x;
 
            while (1)
            {
                curY += curDirY;
                curX += curDirX;
 
                if (curY < 0 || curY >= n) break;
                if (curX < 0 || curX >= n) break;
                if (arr[curY][curX] == 'O') break;
                if (arr[curY][curX] == 'T') break;
                if (arr[curY][curX] == 'S') return false;
            }
        }
    }
 
    return true;
}
 
 
void DFS(int index) // 수 뽑기
{
    if (isBreak) return;
 
    if (v.size() == 3) // 수 다 뽑음.
    {
        if (Check())
        {
            isBreak = true;
        }
 
        return;
    }
 
    for (int i = index + 1; i < n * n; ++i)
    {
        if (arr[i / n][i % n] != 'X') continue;
 
        arr[i / n][i % n] = 'O';
        v.push_back(i);
 
        DFS(i);
 
        arr[i / n][i % n] = 'X';
        v.pop_back();
    }
}
 
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> n;
 
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            cin >> arr[i][j];
 
            if (arr[i][j] == 'T')
            {
                teachersInfo.push_back({ i,j });
            }
        }
    }
 
    for (int i = 0; i < n * n; ++i)
    {
        if (arr[i / n][i % n] != 'X') continue;
 
        arr[i / n][i % n] = 'O';
        v.push_back(i);
        
        DFS(i);
 
        arr[i / n][i % n] = 'X';
        v.pop_back();
    }
 
    if (isBreak) cout << "YES";
    else cout << "NO";
 
    return 0;
}

백트래킹을 이용해 장애물을 설치할 경우의 수를 모두 구한 다음, 각각의 경우의 수마다 선생님을 기준으로 탐색을 해서 학생을 한번이라도 발견한다면 바로 false를 리턴한다.

n값이 굉장히 작기때문에 어떤방법이든 탐색만 제대로 하면 ANS를 받을 수 있다.