백준 18428번 - 감시 피하기

감시 피하기 문제 바로 가기

풀이 날짜: 2026-01-09

baekjoon 알고리즘 문제 풀이

풀이 코드


import sys
from itertools import combinations

input = sys.stdin.readline

n = int(input())
graph = []
teacher = []
space = []

for i in range(n):
    graph.append(list(input().split()))
    for j in range(n):
        if graph[i][j] == 'T':
            teacher.append((i,j))
        if graph[i][j] == 'X':
            space.append((i,j))

def watch(x,y,direction):
    if direction == 0:
        while y>=0:
            if graph[x][y] == 'S':
                return True
            if graph[x][y] == 'O':
                return False
            y-=1

    if direction == 1:
        while y<n:
            if graph[x][y] == 'S':
                return True
            if graph[x][y] == 'O':
                return False
            y+=1

    if direction == 2:
        while x>=0:
            if graph[x][y] == 'S':
                return True
            if graph[x][y] == 'O':
                return False
            x-=1

    if direction == 3:
        while x<n:
            if graph[x][y] == 'S':
                return True
            if graph[x][y] == 'O':
                return False
            x+=1
    return False

def process():
    for x,y in teacher:
        for i in range(4):
            if watch(x,y,i):
                return True
    return False

find = False

for data in combinations(space,3):
    for x,y in data:
        graph[x][y] = 'O'

    if not process():
        find = True
        break

    for x,y in data:
        graph[x][y] = 'X'

if find:
    print('YES')
else:
    print('NO')

문제 핵심 요약:

이 문제는 교실에서 선생님(T)의 감시를 피해 모든 학생(S)을 보호할 수 있는지 판단하는 문제다.
장애물(O)을 정확히 3개만 설치할 수 있는데, 선생님은 상하좌우 네 방향으로 직선 감시를 하고, 중간에 장애물이 있으면 그 방향의 시야는 차단된다.
따라서 이 문제는 “어디에 장애물 3개를 놓아야 모든 선생님의 시야에서 학생이 사라지는가”를 확인해야 한다.

내가 선택한 풀이 방식

먼저 장애물을 놓을 수 있는 빈 칸(X)의 좌표를 모두 수집한 뒤, 이 중에서 3개를 고르는 모든 조합을 생성했다.
각 조합마다 실제로 장애물을 설치한 후, 그 상태에서 선생님의 감시가 학생에게 닿는지 시뮬레이션 했다.

감시 로직(watch) 구현

선생님의 감시는 상, 하, 좌, 우 네 방향으로 직선으로 진행되기 때문에, watch(x, y, direction) 함수에서 방향별로 한 칸씩 이동하며 검사하도록 구현했다. 이동 중 학생(S)을 만나면 즉시 True를 반환해 “학생이 들켰다”는 사실을 알리고, 장애물(O)을 만나면 그 방향의 감시는 더 이상 진행할 수 없으므로 False를 반환하도록 했다. 끝까지 이동했는데 학생을 만나지 못한 경우에도 False를 반환한다. 이 함수는 “이 방향으로 학생이 보이는가?” 라는 질문에 답하는 역할만 수행하도록 설계했다.

장애물 조합 탐색과 백트래킹

각 조합에 대해 먼저 해당 위치에 장애물을 설치한 뒤, process() 함수를 호출해 감시 결과를 확인한다. 만약 process()가 False를 반환한다면, 이는 학생이 한 명도 들키지 않는 성공적인 배치이므로 즉시 정답을 찾았다고 판단하고 탐색을 종료한다. 실패한 경우에는 설치했던 장애물을 다시 빈 칸(X)으로 되돌려 다음 조합을 검사한다. 이 과정은 전형적인 백트래킹 구조이다.

구현 과정에서 겪은 어려움

find, True / False 의미가 헷갈렸던 이유

이 문제에서 가장 헷갈렸던 부분은 True와 False의 의미가 직관과 반대로 사용된다는 점이었다. process()에서 True는 “학생이 들켰다(실패)”를 의미하고, False는 “아무도 안 들켰다(성공)”를 의미한다. 반면 find 변수에서 True는 “정답이 되는 배치를 찾았다”라는 긍정적인 의미를 가진다. 이 두 의미가 섞이면서 코드 해석이 어려웠지만, 각 값을 문장으로 풀어 읽는 방식으로 이해하니 구조가 명확해졌다.

왜 if not process()

rocess()는 학생이 들켰을 때 True를 반환하므로, 우리가 원하는 성공 조건은 process()가 False일 때이다. 따라서 코드에서는 if not process():라는 형태로 조건을 검사한다. 이는 “현재 장애물 배치에서 학생이 단 한 명도 들키지 않았다면”이라는 의미이며, 이 조건이 만족되는 순간 문제의 답은 YES가 된다.

Vienna sausage