18428-감시피하기

www.acmicpc.net/problem/18428

1. 장애물 3 개를 설치하는 모든 경우의 수 순열

2. 각 경우마다 학생이 들키지 않는지 검사

3. 중간에 한 명도 안 들킨 경우가 생겼다면 YES 출력하고 exit()

# 학생을 발견하면 발견표시 남기자
def see(y,x,dir):
    global n, triger

    ny = y + dy[dir]
    nx = x + dx[dir]

    if 0 <= ny < n and 0 <= nx < n:
        if temp[ny][nx] == 'S':
            triger = 'ON'
            return
        elif temp[ny][nx] == 'O':
            return
        elif temp[ny][nx] == "X":
            see(ny,nx,dir)
    else:
        return

from itertools import combinations

n = int(input())
arr = [list(input().split()) for _ in range(n)]

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

# 선생님들의 위치
t_locs = []
for i in range(n):
    for j in range(n):
        if arr[i][j] == 'T':
            t_locs.append((i,j))

# 장애물을 설치할 수 있는 경우의 수
x_locs = []
for i in range(n):
    for j in range(n):
        if arr[i][j] == 'X':
            x_locs.append((i,j))
o_cases = list(combinations(x_locs,3))

# 장애물 위치 정보 경우들로 반복문
# 장애물을 설치한 한 경우에서..! 모든 선생님의 상하좌우에서 True 라면 끝
poss = "NO"
for o_case in o_cases:
    temp = [arr[i][:] for i in range(len(arr))]

    # 장애물 설치
    for i in range(3):
        temp[o_case[i][0]][o_case[i][1]] = 'O'

    # 장애물 설치된 복도에서 모든 선생님들 감시를 해보자
    triger = 'OFF'
    for ty,tx in t_locs:
        for i in range(4):
            see(ty,tx,i)

    # 현재 케이스에서 단 한 번도 학생을 만난적이 없다면
    if triger == 'OFF':
        poss = 'YES'
        break

print(poss)