Q20. 감시 피하기

18428번: 감시 피하기 (acmicpc.net)

18428번: 감시 피하기

 

전형적인 grid 탐색 문제

N 제약조건이 작은 것을 보아 전형적인 combinations를 이용한 backtracking 문제

 

문제 푸는 방법은 이렇다.

1. 모든 X의 위치중에 3개의 O를 놓는 모든 상황을 다 고려한다.

2. 각 경우마다 T의 위치에서 상하좌우로 끝까지 탐색해서 S를 만나는지 검사한다.

 

아이디어는 매우 단순하다. 다만 좀 까다로운게 combinations인데, python 내장 라이브러리 itertools의 combinations함수를 쓰면 매우 편하게 구현 가능하다. 푸는데 30분 안걸린거같다.

 

from itertools import combinations

#input
N = int(input())
grid = []
X_positions = []
T_positions = []
for r in range(N):
    grid.append(input().split())

#padding
for r in range(N):
    grid[r] = ['O'] + grid[r] + ['O']
grid.insert(0,['O'] * (N+2))
grid.append(['O'] * (N+2))

#find t and x positions
for i in range(N+2):
    for j in range(N+2):
        if grid[i][j] == 'T':
            T_positions.append((i,j))
        if grid[i][j] == 'X':
            X_positions.append((i,j))

#check teacher view
#return true if teacher sees any student
def tcheck(grid,r,c):
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    for i in range(4):
        newr = r 
        newc = c 

        while grid[newr][newc] != 'O':
            newr += dx[i]
            newc += dy[i]

            if grid[newr][newc] == 'S':
                return True
    
    return False

#check every teacher view
#return true if all students can hide from teachers
def etcheck(grid,tpos):
    for r,c in tpos:
        if tcheck(grid,r,c):
            return False
    return True

#set 3 obstacles and etcheck
#return true if in any circumstances if all students can hide from teachers
def set_3obs(grid,xpos,tpos):
    for opos in combinations(xpos,3):
        for r,c in opos:
            grid[r][c] = 'O'

        if etcheck(grid,tpos):
            return True

        for r,c in opos:
            grid[r][c] = 'X'

if set_3obs(grid,X_positions,T_positions):
    print("YES")
else:
    print("NO")