백준 감시 피하기 코드 및 해설 (파이썬)

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

18428번: 감시 피하기

 

백준 연구소 문제와 유사하게 풀이했습니다.

 

school엔 입력으로 받아들인 학교의 상태, teachers에는 모든 선생님들의 위치 좌표, blank에는 빈 곳의 위치 좌표를 저장합니다. 

teacher_detect 함수에선 한 명의 선생님이 감시할 수 있는 범위를 확인합니다. 입력으로 주어진 선생님의 위치 좌표에 대해, 그 좌표의 상하좌우를 순서대로 살펴봅니다. 현재 방향으로 이동하면서, 좌표가 0~N 사이일 때, 거기에 학생이 있다면 학생을 감시할 수 있으므로 True를 반환합니다. 거기에 장애물이 있다면, 더 이상 그 방향으로 감시할 수 없으므로 break를 걸고 다른 방향을 살펴봅니다. 마지막으로 빈 곳이라면 계속 그 방향으로 나아갈 수 있으므로 큐에 현재 좌표를 추가합니다. 모든 방향을 살펴봤으나 True를 반환하지 않은 경우 어떤 학생도 감시하지 못한 것이므로 False를 반환합니다.

teachers_detect에는 입력으로 주어진 모든 선생님들의 감시 범위를 확인합니다. 선생님 한 명씩에 대해 위에서 정의한 teacher_detect를 실행합니다. 걸린 학생이 한 명이라도 있어 True를 반환하면 'detected'를, 그렇지 않으면 'undetected'를 반환합니다.

마지막으로 입력으로 주어진 모든 빈 곳에 대해 랜덤으로 3개의 조합을 선택하고 이에 따라 장애물을 설치한 상태를 new_school로 저장합니다. 이를 입력으로 teachers_detect를 실행합니다. 이때 teachers_detect가 'undetected'를 반환하면 아무 학생도 걸리지 않은 것입니다. 따라서 이땐 success_flag를 True로 바꿔줍니다. 모든 combination에 대해 적어도 한 명의 학생이 걸렸으면 success_flag는 그대로 False입니다. 

success_flag가 True면 'YES'를, 아니면 'NO'를 출력합니다. 

 

import sys
from itertools import combinations
from collections import deque
import copy

N = int(sys.stdin.readline())
school = [] # 초기 학교 상태 (선생님, 학생, 빈 곳만 있는 상태)
teachers = []  # 선생님들의 위치
blank = []  # 빈 곳의 좌표
for i in range(N):
    row = sys.stdin.readline().split()
    for j, r in enumerate(row):
        if r == 'T':
            teachers.append((i, j))
        elif r == 'X':
            blank.append((i, j))
    school.append(row)

# 상하좌우
UDLR = [(-1, 0), (1, 0), (0, 1), (0, -1)]

# 선생님들이 감시할 수 있는 범위 계산
def teacher_detect(school, teacher, N):
    # 각 상하좌우 방향에 대해 
    for udlr in UDLR:
        q = deque([teacher])
        while q:
            cur = q.popleft()
            a, b = cur
            x, y = udlr # 현재 방향으로 쭉 이동 
            # index error가 나지 않는지 
            if (a + x) in range(N) and (b + y) in range(N):
                pos = school[a + x][b + y]
                if pos == 'S': # 학생이 있으면 걸림 
                    return True
                elif pos == 'O': # 장애물 있으면 이 방향으로 볼 수 있는 범위는 끝 
                    break
                elif pos == 'X': # 빈 곳이면 계속 이 방향으로 이동 
                    q.append((a + x, b + y))
    return False


# 주어진 장애물 위치에 따라 학생들이 감시를 피할 수 있는지 여부 확인
def teachers_detect(new_school, teachers, N):
    # 각 선생님에 대해 
    for teacher in teachers:
        # 걸린 학생이 한 명이라도 있는 경우 
        if teacher_detect(new_school, teacher, N):
            return 'detected'
    # 모든 학생이 걸리지 않은 경우 
    return 'undetected'


# 모든 빈 곳 중 3개 선택
combs = list(combinations(blank, 3))

success_flag = False
for comb in combs:
    new_school = copy.deepcopy(school)  # deepcopy
    # 현재 combination으로 장애물 세우기
    for c in comb:
        a, b = c
        new_school[a][b] = 'O'
    # 현재 combination으로 모든 학생이 걸리지 않은 경우 success
    if teachers_detect(new_school, teachers, N) == 'undetected':
        success_flag = True
        break

# success면 YES, 아니면 NO 출력 
if success_flag:
    print('YES')
else:
    print('NO')