감시 피하기

p.351

 

방법 1

import sys
from itertools import combinations

input=sys.stdin.readline
n=int(input())
map=[]
temp_map=[[0]*n for _ in range(n)]

o=[] # 장애물을 놓을 수 있는 곳의 위치
t=[] # 선생님의 위치

for i in range(n):
  temp_o=list(input().split())
  map.append(temp_o)
  for j in range(n):
    if temp_o[j] == 'X':
      o.append((i,j))
    elif temp_o[j]=='T':
      t.append((i,j))
oc=list(combinations(o,3))

dx=[-1,1,0,0]
dy=[0,0,-1,1]

found=0
flag=0

def dfs(a,b,direction):
  global found
  if a<0 or b<0 or a>=n or b>=n:
    return
  else:
    if temp_map[a][b]=='S': # 학생이 있으면
      found+=1
      return
    elif temp_map[a][b]=='O': # 장애물이 있으면
      return
    elif temp_map[a][b]=='X': # 아무것도 없으면
      dfs(a+dx[direction],b+dy[direction],direction)
      


for obsta in oc:

  for i in range(n): # 맵 초기화
    for j in range(n):
      temp_map[i][j]=map[i][j]
  for i in range(3): # 장애물 설치
    temp_map[obsta[i][0]][obsta[i][1]]='O'

  for teacher in t: # 선생님별로
    t_a,t_b=teacher
    for d in range(4): # 4방향 탐색
      dfs(t_a+dx[d],t_b+dy[d],d)

  if found==0:
    # 학생이 걸리지 않은체로 끝남
    print("YES")
    flag=1
    break
  else:
    found=0
      
if flag==0:
  print("NO")

 

방법 2

from itertools import combinations

n=int(input()) # 복도의 크기
board=[] # 복도의 정보
teachers = [] # 모든 선생님의 위치 정보
spaces = [] # 모든 빈 공간 위치 정보

for i in range(n):
  board.append(list(input().split()))
  for j in range(n):
    # 선생님 위치 저장
    if board[i][j]=='T':
      teachers.append((i,j))
    # 장애물을 설치할 수 있는 빈 공간 저장
    if board[i][j]=='X':
      spaces.append((i,j))

# 특정 방향으로 감시를 진행(학생 발견 : True, 학생 미발견 : False)
def watch(x,y,direction):
  # 왼쪽 방향으로 감시
  if direction==0:
    while y>=0:
      if board[x][y]=='S':
        return True
      if board[x][y]=='O':
        return False
      y-=1
  # 오른쪽 방향으로 감시
  if direction==1:
    while y<n:
      if board[x][y]=='S':
        return True
      if board[x][y]=='O':
        return False
      y+=1
  # 위쪽 방향으로 감시
  if direction==2:
    while x>=0:
      if board[x][y]=='S':
        return True
      if board[x][y]=='O':
        return False
      x-=1
  # 아래쪽 방향으로 감시
  if direction==3:
    while x<n:
      if board[x][y]=='S':
        return True
      if board[x][y]=='O':
        return False
      x+=1
  return False

# 장애물 설치 이후에, 한명이라도 학생이 감지되는지 검사
def process():
  # 모든 선생님의 위치를 하나씩 확인
  for x,y in teachers:
    # 4가지 방향으로 학생을 감지할 수 있는지 확인
    for i in range(4):
      if watch(x,y,i):
        return True
  return False

# 학생이 한 명도 감지되지 않도록 설치할 수 있는지의 여부
find=False

# 빈 공간에서 3개를 뽑는 모든 조합을 확인
for data in combinations(spaces,3):
  # 장애물 설치해보기
  for x,y in data:
    board[x][y]='O'
  # 학생이 한 명도 감지되지 않는 경우
  if not process():
    find=True
    break
  # 설치된 장애물을 다시 없애기
  for x,y in data:
    board[x][y]='X'

if find:
  print("YES")
else:
  print("NO")