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

문제

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

18428번: 감시 피하기

 

코드

import collections
import sys

input = sys.stdin.readline
n = int(input())
graph = [list(input().split()) for _ in range(n)]
dx,dy = [-1,1,0,0], [0,0,-1,1]
queue = collections.deque()
check = False

def bfs():
    visited = [[False]*n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if graph[i][j] == 'T':
                queue.append((i,j))

    while queue:
        x,y = queue.popleft()
        for i in range(4):
            temp_x, temp_y = x,y
            while True:
                nx = temp_x + dx[i]
                ny = temp_y + dy[i]
                if 0 <= nx < n and 0 <= ny < n:
                    if graph[nx][ny] == 'X' and visited[nx][ny] == False:
                        visited[nx][ny] = True
                    elif graph[nx][ny] == 'S':
                        return False
                    elif graph[nx][ny] == 'O':
                        break
                    temp_x, temp_y = nx,ny
                else:
                    break
    return True

def recursive(index):
    global check
    if index == 3:
        if bfs():
            check = True
        return
        
    for i in range(n):
        for j in range(n):
            if graph[i][j] == 'X':
                graph[i][j] = 'O'
                recursive(index+1)
                graph[i][j] = 'X'

recursive(0)
if check:
    print("YES")
else:
    print("NO")

 

벽을 세워서 선생님이 모든 학생들을 찾지 못할때 YES를 출력하고 학생을 찾으면 NO를 출력하는 문제이다.

 

벽은 3개 세울수 있어서 완전탐색으로 모든경우에 벽을세워서 학생들을 가릴수 있는 경우가 있는지 확인했다.

 

재귀로 벽이 3개 세워졌을때 bfs를 실행하고 bfs에서는 선생님이 여러명 있을 수 있으니 for문을 돌아 모든 선생님('T')을 queue에 넣어준다.

 

선생님은 4방향을 확인할 수 있는데 거리에 상관없이 벽이 없다면 끝까지 볼 수 있다.

 

그러므로 while문을 이용해 벽이 없다면 쭉 탐색할 수 있게 만들었다. 학생을 발견했다면 False, bfs가 끝날때까지 발견하지 못하면 True를 반환하면 된다.