[acmicpc] 18428. 감시 피하기(python)

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

N=int(input())
arr=[]
student=[]
dirs=[(0,1),(1,0),(0,-1),(-1,0)]

def search(move):
    arr2=copy.deepcopy(arr)
    for r,c in move:
        arr2[r][c]='O' # 장애물 세우기
    for row, col in student:
        for i in range(4):
            nr,nc=row,col
            while True:
                nr, nc = nr + dirs[i][0], nc + dirs[i][1]
                if 0>nr or nr>=N or 0>nc or nc>=N: break
                if arr2[nr][nc]=='O': break
                if arr2[nr][nc]=='T':
                    return False
    return True

for row in range(N):
    arr.append(input().split())
    for col in range(N):
        if arr[row][col]=='S':
            student.append((row,col))
            
moves=set()
for row in range(N):
    for col in range(N):
        if arr[row][col]=='X':
            moves.add((row, col))
moves=list(combinations(moves,3)) # 조합으로 모든 경우의 수 탐색

for i in range(len(moves)):
    if search(moves[i]):
        print('YES')
        exit(0)
print('NO')

 

---

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

18428번: 감시 피하기