[코테 스터디] DFS/BFS, 감시 피하기

Q20. 감시 피하기

🐣문제

NxN 크기의 복도가 있다. 복도는 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 선생님, 학생, 혹은 장애물이 위치할 수 있다.


각 선생님들은 자신의 위치에서 상하좌우 4가지 방향으로 감시를 진행한다. 단, 복도에 장애물이 위치한 경우 선생님은 장애물 뒤에 위치한 학생들은 볼 수 없다. 또한 선생님은 상하좌우 4가지 방향에 대하여 아무리 멀리 있더라도 장애물로 막히기 전까지의 학생들은 모두 볼 수 있다고 가정한다. 학생들은 복도의 빈 칸 중에서 정확히 3개의 장애물을 설치해야 한다.


NxN 크기의 복도에서 학생 및 선생님의 위치 정보가 주어졌을 때, 장애물을 정확히 3개 설치하여 모든 학생들이 선생님의 감시를 피하도록 할 수 있는지 출력하는 프로그램을 작성하시오.


백준 링크 | https://www.acmicpc.net/problem/18428

🐥풀이

3개의 벽을 세우는 모든 경우에서 감시 피하기 성공 여부를 판단한다. 한 경우에서라도 성공하면 선생님의 감시를 피할 수 있다.

벽을 3개씩 세워가면서 선생님의 감시를 피할 수 있는지를 판단한다.
각 선생님의 위치에 대하여 상하좌우 방향으로 뻗어나가며 감시를 진행한다.
학생이 한명이라도 발견되면 감시를 피하는 데 실패한 것이고, 장애물이 먼저 발견되거나 해당 방향으로 학생이 없으면 감시를 피하는 데 성공한 것이다.

🐓코드

n = int(input())
teacher = []
board = [[0]*n for _ in range(n)]
for i in range(n):
  line = list(input().split())
  for j in range(n):
    if line[j]=='S':  # 학생
      board[i][j] = 1
    elif line[j]=='T':  # 선생님
      board[i][j] = 2
      teacher.append([i,j])

dist = [[-1,0], [1,0], [0,1], [0,-1]]

# 감시 피하기 성공 여부
def checking():
  for t in teacher:
    x, y = t  # 선생님 좌표
    for d in dist:
      dx, dy = x, y
      while 0<=dx<n and 0<=dy<n:
        dx, dy = dx+d[0], dy+d[1]
        if dx<0 or dx>=n or dy<0 or dy>=n:
          break
        if board[dx][dy]==1:  # 학생 걸림
          return False
        if board[dx][dy]==3:  # 벽 때문에 안보이니까 탐색 중지
          break
  return True # 걸린 학생 없으면 True


def building():
  for i1 in range(n):
    for j1 in range(n):
      if board[i1][j1]!=0:
        continue
      board[i1][j1] = 3 # 벽1 세우기

      for i2 in range(n):
        for j2 in range(n):
          if board[i2][j2]!=0:
            continue
          board[i2][j2] = 3 # 벽2 세우기

          for i3 in range(n):
            for j3 in range(n):
              if board[i3][j3]!=0:
                continue
              board[i3][j3] = 3 # 벽3 세우기

              # 감시 피하기 체킹
              if checking():
                return "YES"

              board[i3][j3] = 0 # 벽3 치우기
          board[i2][j2] = 0 # 벽2 치우기
      board[i1][j1] = 0 # 벽1 치우기
  
  return "NO"

print(building())

⭐2022.04.25

스스로 생각해서 풀어낸 문제! 뿌듯하다 :)