[실버1] 18428번 : 감시 피하기

🛠 문제

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

👩🏻‍💻 해결 방법

combination을 통해 장애물을 3개 설치하는 모든 경우의 수를 확인해주었다
check 함수 안에서 teacher 리스트의 모든 T 위치에서 상하좌우 dfs 함수를 호출해주고,
dfs 함수 안에서는 하나의 방향에서(?) graph 길이 끝까지 다 확인할 수 있도록 재귀적으로 호출해주는 것이 중요했다...

소스 코드

from itertools import combinations
from copy import deepcopy

n = int(input())
board = [list(map(str, input().split())) for _ in range(n)]

empty = []
teacher = []
student = []
for i in range(n):
  for j in range(n):
    if board[i][j] == 'X':
      empty.append([i, j])
    elif board[i][j] == 'T':
      teacher.append([i, j])
    elif board[i][j] == 'S':
      student.append([i, j])

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

def dfs(board, x, y, i):
  global n
  if x < 0 or x >= n or y < 0 or y >= n or board[x][y] == 'O':
    return
  else:
    board[x][y] = 'T'
    dfs(board, x+dx[i], y+dy[i], i)

def check():
  copy_board = deepcopy(board)
  for [x, y] in teacher:
    for i in range(4):
      dfs(copy_board, x, y, i)
  
  for [x, y] in student:
    if copy_board[x][y] != 'S':
      return False
  return True

for combi in list(combinations(empty, 3)):
  for [x, y] in combi:
    board[x][y] = 'O'
  
  if check():
    print("YES")
    exit()

  for [x, y] in combi:
    board[x][y] = 'X'

print("NO")

💡 다른 사람의 풀이

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:
    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')