[python] 백준 18428 감시 피하기

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

18428번: 감시 피하기

 

문제 해결

벽 3개를 세우는 경우의 수를 모두 해보는 수밖에 없다.

3개를 세우고 'T'(teacher)을 중심으로 동, 서, 남, 북 모든 좌표를 보면서 T와 'S'의 사이에 이미 O가 있으면 넘어가는 방면 없으면 바로 다음 경우의 수를 확인하면 된다.

만약 모든 T와 S 사이에 O로 블로킹(blocking)이 된다면 가능한 사건이므로 YES를 출력하고 코드를 끄면(exit) 된다.

 

CODE

def find_student():
    for teacher in teachers:
        x, y = teacher
        for i in range(x-1,-1,-1):
            if graph[i][y] == 'O':break
            elif graph[i][y] == 'S':
                return False
        for j in range(x+1,n):
            if graph[j][y] =='O':break
            elif graph[j][y] =='S':
                return False
        for i in range(y-1,-1,-1):
            if graph[x][i] == 'O':break
            elif graph[x][i] == 'S':
                return False
        for j in range(y+1,n):
            if graph[x][j] =='O': break
            elif graph[x][j] == 'S':
                return False
    return True

def solve(cnt):
    if cnt == 0:
        if find_student():
            print('YES')
            exit()
        return
    for i in range(n):
        for j in range(n):
            if graph[i][j] == 'X':
                graph[i][j] = 'O'
                solve(cnt-1)
                graph[i][j] = 'X'

if __name__=='__main__':
    n = int(input())
    graph = [list(input().rstrip().split()) for _ in range(n)]
    teachers = []
    for i in range(n):
        for j in range(n):
            if graph[i][j] == 'T':
                teachers.append((i,j))
    solve(3)
    print('NO')