[백준 python] 18428번 감시 피하기

[백준 python] 18428번 감시 피하기

레벨: 실버 1

언어: python

---

문제풀러가기

18428번: 감시 피하기

📑풀이 과정

이 문제는 14502번 연구소 문제와 비슷하다고 생각하여 그러한 방식으로 풀이를 접근했다.

이 문제를 풀기 위해서는 크게 2가지가 필요하다.

1. 장애물을 설치하는 함수
2. 선생의 상하좌우 일직선으로 학생이 있는지 확인하는 함수

1번 함수(solution(count))

solution 함수는 벽을 설치할 수 있는 모든 경우를 찾는 함수이다.
1번의 함수는 재귀방식을 사용하여 X가 되어 있는 곳을 찾고 'O'로 바꿔준다. 그리고 count를 1증가 시킨 후 다시 함수를 호출한다.
이렇게 했을때 count 3 즉 벽이 3개가 설치 되었을 때 check_S(감시하는 함수)를 실행하여 준다.
그리고 check_S(감시하는 함수)가 끝나면 함수를 종료하고 'O'로 바꾼 곳을 다시 'X'로 변경한다.

위 과정을 장애물을 설치할 수 있는 모든 경우에 실행시켜준다.

2번 함수(check_S)

2번 함수는 선생(T)의 위치에서 상,하,좌,우 일직선으로 학생이 있는지 확인하는 함수이다.
학생이 있어 감시가 가능하면 True
상하좌우 직선상에 학생이 없다면 False를 리턴한다.

for 문으로 상하좌우 움직일 위치를 nx, ny에 좌표값 계산한다.
x,y 가 (0,0) 이면 for문에서 우: (1,0), 좌: (-1,0), 상: (0,1), 하(0,-1)로 움직인다.

그리고 while문을 사용하여 좌표계를 벗어나거나 장애물이 없을 때는
같은 방향으로 계속 이동하게 한다.
이동을 하다가 학생('S')를 만나게 되면 True를 리턴한다.
모든 방향을 확인하고 학생을 만나지 않았다면 False를 리턴한다.

학생을 감시할 수 없는 선생의 수를 count하여 모든 선생이 감시를 할 수 없을 때를 찾는다.

📋풀이 코드

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

---