[BOJ]18428 감시 피하기

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

18428번: 감시 피하기

풀이

수업 시간에 도망친다는 얘기는 오랜만이라, 유쾌하게 풀어보았다. 모든 경우의 수를 다 확인해봐야하는 브루트포스 문제이기 때문에, 전체 빈칸 중에서 3가지만 뽑는 조합을 이용하면 되겠다고 생각했다. itertools에서 combination 모듈을 임포트한 후 만약 빈칸이면 빈칸 리스트 blank에, 선생님이면 teacher리스트에 넣어주었다. 다음 모든 경우의 수를 possibility 리스트에 넣어준 후, 하나씩 순차적으로 탐색하면서 먼저 각 경우의 수마다 새로운 매트릭스가 필요하므로 새로운 매트릭스 new_mtr은 passage 매트릭스를 deepcopy한 것이라고 생각하면 된다. new_mtr에서 pos의 요소인 p의 x좌표, y좌표(p[0], p[1])을 "O"로 바꿔주고, teacher 리스트에서 하나씩 가져와서 4방향으로 벽을 만나거나 학생을 만나거나, 장애물을 만날때까지 계속 dx, dy를 더해주었다. 만약 선생님이 학생을 발견한다면 그 경우의 수는 이미 더 이상 탐색할 필요가 없으므로 break해주고, 끝까지 탐색을 완료했는데도 spotted이 거짓이면, 학생 아무도 걸리지 않은 것이므로 possibility 탐색을 종료하고 flag = True로 마무리하면 된다.

import sys
from itertools import combinations
input = lambda: sys.stdin.readline().rstrip()
n = int(input())
passage = [list(input().split())for _ in range(n)]
blank = []
teacher = []
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
for i in range(n):
    for j in range(n):
        if passage[i][j] == 'X':
            blank.append([i, j])
        elif passage[i][j] == 'T':
            teacher.append([i, j])
possibility = list(combinations(blank, 3))
flag = False
for pos in possibility:
    #print(pos)
    new_mtr = [[passage[i][j]for j in range(n)]for i in range(n)]
    spotted = False
    for p in pos:
        new_mtr[p[0]][p[1]] = 'O'
    # for k in range(n):
    #     for h in range(n):
    #         print(new_mtr[k][h], end = ' ')
    #     print()
    for t in teacher:
        for i in range(4):
            nx, ny = t
            while True:
                nx += dx[i]
                ny += dy[i]
                #print(nx, ny)
                if nx < 0 or ny < 0 or nx >= n or ny >= n:
                    break
                if new_mtr[nx][ny] == 'O':
                    break
                if new_mtr[nx][ny] == 'S':
                    spotted = True
                    break
            if spotted:
                break
        if spotted:
            break
    if not spotted:
        flag = True
        break
if flag:
    print('YES')
else:
    print('NO')