[백준 18428] 감시피하기(Python)

1. 요약

학생들이 선생님의 감시를 피해 복도에 빠져나가려고 한다. 선생님은 장애물로 막히지 않는 한 상하좌우 방향으로 복도 끝까지 볼 수 있다. 학생들이 장애물을 3개 설치해서 선생님들의 감시를 피할 수 있는지 없는지 알아보는 문제이다.

2. 아이디어

입력 조건에서 복도의 크기가 작은 것을 알 수 있다. 따라서 주어진 위치에서 장애물 3개를 복도에 설치하는 경우의 수를 구한다.(이 때, 학생과 선생님이 없는 곳으로 두어야한다.) 이후, 각 경우에 대해, 선생님들이 학생들을 볼 수 있는지 없는지 검사한다.

3. 코드

import sys
from itertools import combinations

n = int(sys.stdin.readline().rstrip())
arr = [sys.stdin.readline().rstrip().split() for _ in range(n)]

available_obstacle_pos = [(i,j) for i in range(n) for j in range(n) if arr[i][j] == 'X']
obstacle_cases = tuple(combinations(available_obstacle_pos, 3))
teachers_pos = [(i,j) for i in range(n) for j in range(n) if arr[i][j] == 'T']

def isin(y, x):
    if -1<y<n and -1<x<n: return True
    return False

def solve():
    d = [(-1,0), (1,0), (0,1), (0,-1)]

    for case in obstacle_cases:
        copy_arr = [[arr[i][j] for j in range(n)] for i in range(n)]
        ok = True

        for y, x in case: copy_arr[y][x] = 'O'

        for teacher_pos in teachers_pos:
            y, x = teacher_pos[0], teacher_pos[1]

            for k in range(4):
                _y, _x = y, x

                while True:
                    ny = _y + d[k][0]
                    nx = _x + d[k][1]
                    if not isin(ny, nx): break
                    if copy_arr[ny][nx] == 'O': break
                    if copy_arr[ny][nx] == 'S':
                        ok = False
                        break

                    _y = ny
                    _x = nx
                
                if not ok: break
            
            if not ok: break
        
        if ok:
            print('YES')
            return
    
    print('NO')

solve()