[이것이 코딩 테스트다 with Python] Chapter 13. DFS/BFS - 감시 피하기

< 감시 피하기 >

 

💬 문제 설명

NxN 크기의 복도가 있다. 복도는 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 선생님, 학생, 혹은 장애물이 위치할 수 있다. 현재 몇 명의 학생들은 수업시간에 몰래 복도로 빠져나왔는데, 복도로 빠져나온 학생들은 선생님의 감시에 들키지 않는 것이 목표이다.

....

 

입력	출력
5   X  S  X  X  T   T  X  S  X  X   X  X  X  X  X   X  T  X  X  X   X  X  T  X  X	YES
4   S  S  S  T   X  X  X  X   X  X  X  X   T  T  T  X	NO

💬 입력 조건

• 첫째 줄에 N ( 3 ≤ N ≤ 6 )
  
• 둘째 줄부터 N개의 원소들 ( S : 학생,  T : 선생님,  X : 빈칸)  
• 선생님 수 ( 1 ≤ T의 수 ≤ 5 ), 학생 수 ( 1 ≤ S의 수 ≤ 30 )

💬 출력 조건

• 모든 학생들이 감시를 피하는 경우 있으면 "YES" 없으면 "NO"

---

✍ 문제요약

N X N 크기의 복도가 있다. 특정한 위치에 선생님(T), 학생(S) 혹은 장애물이 위치할 수 있다. 선생님들이 본인의 위치에서 상, 하, 좌, 우로 감시했을 때 학생이 보이면 감시를 피하지 못한 것이고, 장애물에 가려서 보이지 않는 등등의 상황이면 감시를 피한 것이다. 무조건 3개의 장애물을 설치 해야할 때 감시를 피하는 경우가 한번이라도 있으면 "YES" 그렇지 않으면 "NO"를 출력하라.

💯 문제링크

백준18428 문제와 동일하다.

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

18428번: 감시 피하기

---

✅  문제 풀이

• 기둥 3개를 임의로 세워서 선생님의 눈을 피할 수 있는 Case를 찾아야한다.
• Combinations으로 기둥 3개를 세우는 모든 케이스를 완전탐색한다.
• 선생님의 수 최대 5, 학생 수 최대 30 선생님이 적으니 선생님 기준으로 학생을 확인한다.

import sys
from itertools import combinations
input = sys.stdin.readline

def isMeet():
    global meet
    for r, c in T:
        for dr, dc in ((-1, 0), (0, 1), (1, 0), (0, -1)): # 선생님 기준 4방향 확인
            for n in range(1, N):                         # 각 방향으로 n칸 씩 이동
                nr, nc = r + dr * n, c + dc * n
                if 0 <= nr < N and 0 <= nc < N:  # 그래프 범위 안에 있을 때만
                    if G[nr][nc] == "O":         # 장애물 만나면
                        break                    # 해당 방향 탐색 끝
                    elif G[nr][nc] == "S":       # 학생 만나면
                        return True              # 감시를 피하지 못헀음

    meet = False  # 만나지 않았다
    return False  # 감시를 피했다

N = int(input())
G, X, T = [], [], []
for R in range(N):
    tmp = list(map(str,input().split()))
    G.append(tmp)                               # 복도 그래프 만들기
    for C in range(N):
        if tmp[C] == "X" : X.append((R,C))      # 빈공간 위치 저장
        elif tmp[C] == "T" : T.append((R,C))    # 선생님 위치 저장

meet = True
for blocks in combinations(X,3):           # 빈공간 3곳에 임의로 장애물 설치
    for r, c in blocks : G[r][c] = "O"     # 장애물 세우고 확인
    if not isMeet() : break                # False가 반환 되면 감시를 피했으니 break
    for r, c in blocks : G[r][c] = "X"     # 장애물 회수

print("NO") if meet else print("YES")