[백준][시뮬레이션] 18428.감시 피하기

18428.감시 피하기

 

• 내 풀이
  • 선생님(T) 기준 4방향에 인접한 칸에 학생(S)이 있으면 무조건 걸림
  • → 즉시 “NO” 출력 후 종료
  • 장애물 설치 위치 수집
    • 빈칸(X) 좌표를 수집하여 번호와 함께 저장
    • 장애물 3개를 설치할 수 있는 모든 조합 생성
  • 감시 시뮬레이션
    • 조합마다 장애물 3개를 임시로 설치
    • 각 선생님이 4방향으로 감시를 시작함
    • 장애물이 있는 경우 시야 차단
    • 학생이 보이면 실패
  • 정답 판단
    • 학생이 단 한 명이라도 감시에 걸리면 해당 조합은 실패
    • 모든 조합을 확인했을 때 단 한 번이라도 감시를 피하면
    • → "YES" 출력 후 종료
    • 끝까지 감시를 피할 수 없다면
    • → "NO" 출력

from collections import defaultdict
from itertools import combinations
import copy

n = int(input())
graph = [list(input().split()) for _ in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
number = 0
dic = defaultdict(tuple)
in_dic = set()


# 선생님 주변에 학생이 바로 있는 경우는 예외 처리
def neighbor(x, y):
    for k in range(4):
        nx = x+dx[k]
        ny = y+dy[k]
        if nx < 0 or ny < 0 or nx >= n or ny >= n:
            break
        if graph[nx][ny] == 'S':
            return False
    return True


# 감시 시뮬레이션: 한 방향으로 감시할 때 학생이 보이는지
def watch(x, y, d, board):
    while True:
        nx = x + dx[d]
        ny = y + dy[d]

        if nx < 0 or ny < 0 or nx >= n or ny >= n:
            break
        if board[nx][ny] == 'O':  # 장애물이 있으면 시야 차단
            break
        if board[nx][ny] == 'S':  # 학생 발견
            return True
        x, y = nx, ny

    return False


# 학생 감시되는지 전체 확인
def detect(board):
    for i in range(n):
        for j in range(n):
            if board[i][j] == 'T':
                for d in range(4):
                    if watch(i, j, d, board):
                        return True
    return False


# 장애물 설치 가능한 위치 저장
for i in range(n):
    for j in range(n):
        if graph[i][j] == 'X':
            dic[number] = (i, j)
            number += 1
        elif graph[i][j] == 'T':
            if not neighbor(i, j):
                print("NO")
                exit()


for combi in combinations(dic.keys(), 3):
    visited = copy.deepcopy(graph)
    for c in combi:
        i, j = dic[c]
        visited[i][j] = 'O'

    if not detect(visited):  # 감시 피함
        print("YES")
        exit()

print("NO")

 

 

• 다른 사람 풀이
  • 백트래킹
  • 하나씩 설치해보면서 3개가 될때 감시 가능한지 확인

n = int(input())
graph = []
teacher = 0
for _ in range(n):
  data = list(input().strip().split(' '))
  teacher += data.count('T')
  graph.append(data)

# 상,하,좌,우 움직이는 배열
dx = [1,-1, 0, 0]
dy = [0, 0, 1, -1]

# 직선 방향 확인 함수
def check_S(x,y):
  for i in range(4):
    nx = x + dx[i]
    ny = y + dy[i]
    # 직선 방향으로 확인
    while 0<= nx < n and 0<= ny < n and graph[nx][ny] !='O':
      if graph[nx][ny] == 'S':
        # 감시가능하다
        return True            
      else:        
        # T 나 X으면 계속 탐색
        nx += dx[i]
        ny += dy[i]
  # 감시 불가능하다
  return False

def solution(count):
  global answer
  if count == 3:
    cnt = 0
    for i in range(n):
      for j in range(n):
        if graph[i][j] == 'T':
          if not check_S(i,j):          
            cnt+=1
    # 모든 선생이 감시가 불가능할 때
    if cnt == teacher:
      answer = True
    return

  for i in range(n):
    for j in range(n):
      if graph[i][j] == 'X':
        graph[i][j] = 'O'
        count +=1
        solution(count)
        graph[i][j] = 'X'
        count -=1

answer = False
solution(0)
if answer:
  print('YES')
else:
  print('NO')