감시 피하기

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

뭔가 dfs문제같긴 했는데 나는 그냥 itertools의 조합을 이용하여 풀었다. 처음에 논리는 제대로 구현했으나 return false를 모든 k를 검사 한 후에 놔뒀어야 하는데 하나만 검사하고 리턴하도록 해서 못풀고 있었다. 아직 실력이 부족한 것 같다.

from itertools import combinations
import copy

n = int(input())
maps = []
istrue = 0
for i in range(n):
    maps.append(input().split())
    
spaces = []#빈 공간 좌표
for a in range(n):
    for b in range(n):
        if maps[a][b] == 'X':
            spaces.append((a, b))

def issafe(maps):
    teacher, student, obstacle = [], [], []
    for x in range(n):
        for y in range(n):
            if maps[x][y] == 'T':
                teacher.append((x, y))
            if maps[x][y] == 'S':
                student.append((x, y))
            if maps[x][y] == 'O':
                obstacle.append((x, y))
    for t in teacher:
        for i in range(n):
            if (i, t[1]) in student: #선생의 위아래 체크
                right = 0
                if i > t[0]:#학생이 선생보다 아래쪽에 있을 때
                    for k in range(t[0], i+1):
                        if (k, t[1]) in obstacle:
                            right = 1
                    if right == 0:
                        return False
                else: #학생이 위쪽에 있을 때
                    for k in range(i, t[0]+1):
                        if (k, t[1]) in obstacle:
                            right = 1
                    if right == 0:
                        return False

            if (t[0], i) in student: #선생의 좌우 체크
                right = 0
                if i > t[1]:#학생이 선생보다 오른쪽에 있을 때
                    for k in range(t[1], i+1):
                        if (t[0], k) in obstacle:
                            right = 1
                    if right == 0:
                        return False
                else: #학생이 왼쪽에 있을 때
                    for k in range(i, t[1]+1):
                        if (t[0], k) in obstacle:
                            right = 1 
                    if right == 0:
                        return False
    return True
            

for s in list(combinations(spaces, 3)):
    temp = copy.deepcopy(maps)
    for space in s:
        temp[space[0]][space[1]] = 'O'
    if issafe(temp):
        istrue = 1
        print('YES')
        break
            
if not istrue:
    print('NO')