[백준] 감시 피하기

접근 방법 : 브루트 포스, DFS or BFS, combinations

모든 경우를 조합으로 구한 뒤, 그래프 탐색을 이용하여 조건을 충족하는 지를 확인.
한 방향으로 계속 탐색해야 하는 상황이라 한 방향으로 탐색하는 로직을 잘 생각했어야 했음.

deepcopy해야 할 대상 유의하자!

# -*- coding: euc-kr -*-
import sys
from itertools import combinations
from copy import deepcopy
from collections import deque

N = int(sys.stdin.readline())

board= []
X_list = []
T_list = deque([])
X_com = []

for i in range(N):
    input_list = list(sys.stdin.readline().strip().split())
    board.append(input_list)
    for j in range(N):
        if input_list[j] == "X":
            X_list.append([i, j])
        elif input_list[j] == "T":
            T_list.append([i, j])

X_com = list(combinations(X_list, 3))

result = False

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


def bfs():
    while temp_T:
        x, y = temp_T.popleft()

        for i in range(4):
            temp_x, temp_y = x , y
            # 한 방향으로 계속 탐색하기 위한 로직.
            while True:
                nx = temp_x + dx[i]
                ny = temp_y + dy[i]
                if 0 <= nx < N and 0 <= ny < N:
                    if temp_board[nx][ny] == 'X':
                        temp_board[nx][ny] = 'T'
                    elif temp_board[nx][ny] == 'S':
                        return False
                    elif temp_board[nx][ny] == 'O':
                        break
                    temp_x, temp_y = nx, ny
                else:
                    break
    return True


for x in X_com:
    temp_board = deepcopy(board)
    temp_T = deepcopy(T_list)

    temp_board[x[0][0]][x[0][1]] = temp_board[x[1][0]][x[1][1]] = temp_board[x[2][0]][x[2][1]] = 'O'

    if bfs():
        result = True
        break

if result:
    print("YES")
else:
    print("NO")