[백준] 18428번 감시 피하기 - 파이썬/백트래킹

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

N = int(input())

graph = [ list(input().split()) for _ in range(N) ]

def chech(graph):

    for i in range(N):
        for j in range(N):
            if graph[i][j]=='T':
                # > 방향
                for k in range(j,N):
                    if graph[i][k] == 'S':
                        return False
                    elif graph[i][k] == 'O':
                        break
                    else:
                        continue

                # < 방향
                for k in range(j,-1,-1):
                    if graph[i][k] == 'S':
                        return False
                    elif graph[i][k] == 'O':
                        break
                    else:
                        continue
                # ^ 방향
                for k in range(i,N):
                    if graph[k][j] == 'S':
                        return False
                    elif graph[k][j] == 'O':
                        break
                    else:
                        continue


                for k in range(i,-1,-1):
                    if graph[k][j] == 'S':
                        return False
                    elif graph[k][j] == 'O':
                        break
                    else:
                        continue


    return True

bt_list = []

for i in range(N):
    for j in range(N):
        if graph[i][j] not in ['T','S']:
            bt_list.append([i,j])

array = []

ans = False

def dfs(depth):
    global ans

    if depth == 3:
        graph_copy = [arr[:] for arr in graph]
        for i in array:
            graph_copy[i[0]][i[1]] = 'O'

        if chech(graph_copy):
            ans = True

        return

    for i in range(len(bt_list)):
        if i not in array:
            array.append(bt_list[i])
            dfs(depth+1)
            array.pop()

dfs(0)

if ans:
    print('YES')
else:
    print('NO')

graph에 대해 조건 통과 여부를 판단하는 check라는 함수를 작성했고

백트래킹으로 O 장애물 3개를 설치해가면서 문제 조건을 통과하는지 체크해준다.