[백준] 18428번: 감시 피하기

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

18428번: 감시 피하기

구현 + 브루트포스 + 그래프 탐색 문제였다. 

 N 값이 3 ~ 6 으로 작아서 브루트포스로 장애물을 설치할 3군데를 정해서 풀어도 되는 문제였다. 

선생님이 움직이지 않아서 상하좌우 방향으로 세로줄 전체와 가로줄 전체만 확인해주면 되었다. 

from itertools import combinations
import sys
input = sys.stdin.readline

n = int(input())
teacher = []
blank = [] # 장애물 설치 가능 빈칸
board = [list(input().split()) for _ in range(n)]
result = False
for i in range(n):
    for j in range(n):
        if board[i][j] == 'T':
            teacher.append([i, j])
        if board[i][j] == 'X':
            blank.append([i, j])

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

def check_range(i, j):
    if 0 <= i < n and 0 <= j < n:
        return True
    else:
        return False

def seek_student():
    for tx, ty in teacher:
        for i in range(4):
            nx = tx + dx[i]
            ny = ty + dy[i]

            while True:

                if not check_range(nx, ny):
                    break
                if board[nx][ny] == 'S':
                    return False
                elif board[nx][ny] == 'O':
                    break

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



for test_case in combinations(blank, 3):
    for x, y in test_case:
        board[x][y] = 'O'

    temp_result = seek_student()

    if temp_result: # True
        result = True
        break

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

if result:
    print("YES")
else:
    print("NO")