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')