백준 알고리즘 18428: 감시 피하기(Python)

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

18428번: 감시 피하기

---

문제 해결을 위한 과정

이 문제는 BFS로 해결하기보다는 문제의 조건을 따라서 해결하면 더 쉬웠던 문제입니다. 처음에 그래프입력을 받으면서 x인 곳을 blank라는 리스트에 따로 추가하고 T인 곳을 teacher이라는 리스트에 따로 추가를 해줍니다. 선생님들은 상, 하 , 좌, 우 4곳으로 볼 수 있고 방해물이 없다면 그래프의 끝까지 조회할 수 있으므로 방향 리스트인 dx, dy를 만들고 bfs함수를 정의합니다. 각 방향을 끝까지 조회하면서 빈칸인 경우 T로 방문처리를 해주거나, 방해물이 있는경우 그 뒤쪽은 볼수 없는 경우를 처리해주고, 학생을 찾은 경우 바로 bfs함수에서 False를 return해주면 쉽게 해결할 수 있습니다. 학생을 찾지 못한 경우는 True를 return해주면 되겠습니다.

---

소스코드

from collections import deque
from itertools import combinations
import copy
 
n = int(input())
graph = []
teacher = []
blank = []
 
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
 
for i in range(n):
  graph.append(list(input().split()))
  for j in range(n):
    if graph[i][j] == 'T':
      teacher.append((i, j))
    elif graph[i][j] == "X":
      blank.append((i, j))
 
def bfs(): # 학생 찾으면 False 반환
  q = deque(teacher)
  test_graph = copy.deepcopy(graph)
  while q:
    x, y = q.popleft()
    for i in range(4):
      temp_x, temp_y = x, y
      while True:
        nx = temp_x + dx[i]
        ny = temp_y + dy[i]
        if 0 <= nx < n and 0 <= ny < n:
          if test_graph[nx][ny] == 'X':
            test_graph[nx][ny] = 'T'
          elif test_graph[nx][ny] == 'S':
            return False
          elif test_graph[nx][ny] == 'O':
            break
          temp_x, temp_y = nx, ny
        else:
          break
  return True
 
check = False
for data in list(combinations(blank, 3)):
  for x, y in data:
    graph[x][y] = 'O'
  if bfs():
    check = True
    break
  for x, y in data:
    graph[x][y] = 'X'
    
if check:
  print("YES")
else:
  print("NO")