BOJ 18428 감시 피하기

https://www.acmicpc.net/problem/18428
시간 2초, 메모리 256MB

input :

• N (3 ≤ N ≤ 6)
• N개의 줄에 걸쳐서 복도의 정보 (학생 : S, 선생님 : T, 아무것도 존재하지 않는다면 X)

output :

• 모든 학생들을 감시로부터 피하도록 할 수 있다면 "YES", 그렇지 않다면 "NO"를 출력

조건 :

• 선생님들은 자신의 위치에서 상, 하, 좌, 우 4가지 방향으로 감시, 아무리 멀리 있더라도 장애물로 막히기 전까지의 학생들은 모두 볼 수 있다

• 복도에 장애물이 위치한 경우, 선생님은 장애물 뒤편에 숨어 있는 학생들은 볼 수 없다.

• 복도의 빈 칸 중에서 장애물을 설치할 위치를 골라, 정확히 3개의 장애물을 설치

---

문제의 제약 조건이 크지 않기 때문에 모든 경우의 수를 따져보는 것이 가능하다.

빈 공간들에 대한 좌표를 저장한 후에 이 3개의 공간에 벽을 세우고 선생으로부터 피할 수 있는지 확인해야 한다.

import sys

def check():
    for fir in range(len(vacant) - 2):
        for sec in range(fir + 1, len(vacant) - 1):
            for thi in range(sec + 1, len(vacant)):
                data[vacant[fir][0]][vacant[fir][1]] = 'O'
                data[vacant[sec][0]][vacant[sec][1]] = 'O'
                data[vacant[thi][0]][vacant[thi][1]] = 'O'

                if search():
                    return True

                data[vacant[fir][0]][vacant[fir][1]] = 'X'
                data[vacant[sec][0]][vacant[sec][1]] = 'X'
                data[vacant[thi][0]][vacant[thi][1]] = 'X'
    return False

def search():
    dx, dy = [0, 0, 1, -1], [1, -1, 0, 0]
    for idx in range(len(teacher)):

        for i in range(4):
            nx, ny = teacher[idx][0], teacher[idx][1]

            while nx >= 0 and nx < n and ny >= 0 and ny < n:
                if data[nx][ny] == 'S':
                    return False

                if data[nx][ny] == 'O':
                    break

                nx += dx[i]
                ny += dy[i]
    return True


n = int(sys.stdin.readline())
data, vacant, teacher = [], [], []

for i in range(n):
    temp = list(sys.stdin.readline().split())
    data.append(temp)

    for j in range(n):
        if temp[j] == 'T':
            teacher.append((i, j))
        elif temp[j] == 'X':
            vacant.append((i, j))

print("YES" if check() else "NO")