[백준] 18428 - 감시 피하기 (구현, 조합)

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

18428번: 감시 피하기

from itertools import combinations
 
dd = ((-1, 0), (0, 1), (1, 0), (0, -1))
n = int(input())
graph = [[' '] for _ in range(n + 1)]
empty = list()
teachers = list()
for i in range(1, n + 1):
    graph[i] += input().split()
    for j in range(1, n + 1):
        if graph[i][j] == 'X':
            empty.append((i, j))
        elif graph[i][j] == 'T':
            teachers.append((i, j))
 
for obj in combinations(empty, 3):
    for y, x in obj:
        graph[y][x] = 'O'
 
    flag = False
    for teacher in teachers:
        for i in range(4):
            y, x = teacher
            while 1 <= y <= n and 1 <= x <= n and graph[y][x] != 'O':
                if graph[y][x] == 'S':
                    flag = True
                    break
                y += dd[i][0]
                x += dd[i][1]
            if flag:
                break
        if flag:
            break
 
    if not flag:
        print('YES')
        exit()
 
    for y, x in obj:
        graph[y][x] = 'X'
 
print('NO')

문제 분류에는 백트래킹으로 되어 있으나, 파이썬의 경우 combinations를 사용하면 구현처럼 풀 수 있다.

PS를 하면 할 수록 파이썬이 코딩 테스트에 정말 좋은 언어라는걸 새삼 느낀다. 귀찮은 것이 정말 줄어든다.