[백준] 18428. 감시 피하기 (파이썬)

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

18428번: 감시 피하기

 

import sys
n = int(sys.stdin.readline())
arr = [['X']*(n+1)]
blank = []
teachers = []
for i in range(1, n+1):
    arr.append([0] + list(map(str, sys.stdin.readline().split())))
    for j in range(1, n+1):
        if arr[i][j] == 'X': blank.append([i,j])
        if arr[i][j] == 'T': teachers.append([i,j])

def teacher_view():
    dx = [-1, 0, 1, 0]
    dy = [0, 1, 0, -1]
    for t in teachers:
        for i in range(4):
            x, y = t[0], t[1]
            # 학생을 만나거나 벽에 부딪힐 때까지
            while True:
                nx = x + dx[i]
                ny = y + dy[i]
                if nx < 1 or nx > n or ny < 1 or ny > n:
                    break
                if arr[nx][ny] == 'S':
                    return False
                if arr[nx][ny] == 'O':
                    break
                x, y = nx, ny
    return True

def solution():
    l = len(blank)
    for i in range(l):
        for j in range(i):
            for k in range(j):
                arr[blank[i][0]][blank[i][1]] = 'O'
                arr[blank[j][0]][blank[j][1]] = 'O'
                arr[blank[k][0]][blank[k][1]] = 'O'

                # 선생님 시야 파악
                if teacher_view():
                    return True

                arr[blank[i][0]][blank[i][1]] = 'X'
                arr[blank[j][0]][blank[j][1]] = 'X'
                arr[blank[k][0]][blank[k][1]] = 'X'
    return False


if solution():
    print("YES")
else:
    print("NO")

 

전에 풀었던 '연구소' 문제랑 거의 비슷한 문제여서 생각보다 빨리 풀 수 있었다.

1. 빈칸의 좌표 정보와 선생님의 좌표 정보를 저장한다.

2. 3개의 장애물을 설치할 수 있는 경우의 수마다 (combintaion 함수를 쓸 수도 있는데 3개까지는 3중반복문으로 돌려봄)

3. 3개의 장애물을 설치한다.('O'로 변경)

4. 선생님의 시야에 학생이 있는지 파악한다.

    각 선생님의 좌표마다 상하좌우로 움직이면서 벽이나 장애물에 부딪히기 전에 학생이 있으면 False, 전부 돌려봐도 학생을 만나지 못한다면 True를 반환

5. 선생님의 시야를 파악하는데 하나라도 True가 나오면 선생님의 감시를 피할 수 있는 경우가 있다는 의미이므로 바로 return True할 수 있도록 2-6까지도 함수로 만들어주었다.

6. 만약 모든 경우의 수에 대해서 선생님의 시야를 파악했지만 단 하나의 경우도 True가 나오지 않았다면 False를 반환한다.

7. 최종 결과 반환값이 True라면 "YES" 출력, False라면 "NO"를 출력

 

이 문제는 단 하나의 경우라도 찾으면 모든 실행을 중단하고 결과를 반환할 수 있도록 짜서 불필요한 계산을 줄이려고 했다. 전에 '연구소'문제를 풀 때에는 3개의 벽을 세우고, 바이러스를 퍼트린 뒤, 안전 영역을 계산하는 과정에서 DFS와 안전 영역 계산 등에서 헤맸어서 그 때 여러번 반복적으로 풀면서 확실히 풀이를 기억해두었는데, 이 문제가 상당히 유사해서 빨리 풀 수 있었던 것 같다. 한 문제 한 문제 확실히 풀고 넘어가야겠다는 생각이 든다.