[백준] 18428 감시 피하기 python

이번 포스팅에서는 백준 18428 번 감시피하기 문제를 python으로 해결한 것에 대해 이야기하려고 합니다.

 

 

정답 코드

# 감시 피하기
# 복습 횟수:0, 00:30:00, 복습필요X
import sys
from itertools import combinations
si = sys.stdin.readline
# 완탐인듯 3 <= N <= 6
N = int(si())
graph = [list(map(str, si().rstrip().split())) for _ in range(N)]

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

for i in range(N):
    for j in range(N):
        if graph[i][j] == 'X':
            blank_list.append([i, j])
        
        if graph[i][j] == 'T':
            teacher_list.append([i, j])

answer = "NO"

candidate_combi_list = list(combinations(blank_list, 3))

for candidate_combi in candidate_combi_list:
    x1, y1 = candidate_combi[0]
    x2, y2 = candidate_combi[1]
    x3, y3 = candidate_combi[2]
    
    # 장애물 설치하기
    graph[x1][y1] = 'O'
    graph[x2][y2] = 'O'
    graph[x3][y3] = 'O'

    studentFound = False
    for x, y in teacher_list:
        for idx in range(4):
            nx, ny = x, y
            while True:
                nx, ny = nx + dx[idx], ny + dy[idx]
                if not (0 <= nx < N and 0 <= ny < N): break
                if graph[nx][ny] == 'O': break # 장애물을 만나 더이상 탐색할 수 없으므로

                if graph[nx][ny] == 'S':
                    studentFound = True

    if studentFound == False:
        answer = "YES"
        break

    # 장애물 초기화
    graph[x1][y1] = 'X'
    graph[x2][y2] = 'X'
    graph[x3][y3] = 'X'

print(answer)

 

풀이 과정

1. N의 범위가 매우 작으므로 완전 탐색으로 문제를 풀어야 겠다는 생각을 하였습니다.

문제 분석

 

2. 완전 탐색이 맞는지 체크해보기위해 필요한 계산의 횟수를 체크해보았습니다.

combination(6*6, 3) 으로 case 마다 되는지 안되는지 체크를 해도 충분할 것이라고 판단하였습니다.

 

3. combination으로 할당된 3 개의 위치에 장애물을 놓고 teacher을 꺼내서 4가지 방향을 탐색하였습니다.