BFS&DFS_심화20) 감시 피하기 _ python

문제링크

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

18428번: 감시 피하기

코드

# 감시 피하기
from itertools import combinations
from collections import deque
import copy

n = int(input())
maps = []
for i in range(n):
    maps.append(list(input().split()))
# 선생님, 학생, 빈칸 좌표 저장
tch = []
empty = []
for x in range(n):
    for y in range(n):
        if maps[x][y] == 'T': tch.append((x, y))
        elif maps[x][y] == 'X': empty.append((x, y))

def bfs(map):
    dx = [1, -1, 0, 0]
    dy = [0, 0, 1, -1]
    for t in tch:
        for k in range(4):
            nx, ny = t
            while 0 <= nx < n and 0 <= ny < n:
                if map[nx][ny] == 'O':
                    break
                if map[nx][ny] == 'S':
                    return False
                nx += dx[k]
                ny += dy[k]
    return True

def solution():
    for i in combinations(empty, 3) :
        new_maps = copy.deepcopy(maps)
        for x, y in i:
            new_maps[x][y] = 'O'
        if bfs(new_maps):
            return 'YES'
    return 'NO'
print(solution())