[python] 백준 18428번: 감시 피하기

내가 생각한 분류

DFS

 

아이디어

1. 장애물을 놓을 수 있는 공간을 리스트로 저장해놓는다.

2. combination 을 활용해, 장애물을 놓을 수 있는 위치의 조합별로 확인한다.

3. (2) 에서 정한 장애물의 위치대로 전체 지도에 장애물을 배치한다.

4. check 함수를 통해 각 경우별로 "선생님"에게 잡히는 "학생"이 없는지를 확인한다.

5. 선생님의 위치마다 동서남북 4방향으로 "T"를 채워넣는다. (장애물이 없는경우)

6. 다 채웠으면 (DFS가 끝나면) 각 학생의 위치의 board 가 "T"인지 "S" 인지를 확인해 "S"가 아닌 경우 1명이라도 선생님에게 잡힌 경우니 이 장애물 배치는 False 다.

7. 모든 장애물 배치에 대해 "모든 학생이 감시를 피하는 경우" 가 없다면 "NO"를 출력하고, 있다면 "YES" 를 출력한다.

 

코드

from sys import stdin
from itertools import combinations
from copy import deepcopy

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

n = int(input())
board = [list(map(str, stdin.readline().split())) for _ in range(n)]

emptys = []
teachers = []
students = []
for i in range(n):
    for j in range(n):
        if board[i][j] == 'X':
            emptys.append([i, j])
        elif board[i][j] == 'T':
            teachers.append([i, j])
        elif board[i][j] == 'S':
            students.append([i, j])


def DFS(board, x, y, idx):
    global n
    if x < 0 or x >= n or y < 0 or y >= n or board[x][y] == 'O':
        return
    else:
        board[x][y] = 'T'
        DFS(board, x + dx[idx], y + dy[idx], idx)


def check():
    copy_board = deepcopy(board)
    for [x, y] in teachers:
        for i in range(4):
            DFS(copy_board, x, y, i)
    for [x, y] in students:
        if copy_board[x][y] != 'S':
            return False

    return True


for case in list(combinations(emptys, 3)):
    for [x, y] in case:
        board[x][y] = 'O'
    if check():
        print("YES")
        exit()
    for [x, y] in case:
        board[x][y] = 'X'

print("NO")