[python] 백준 - 18428. 감시 피하기

🤔문제 해결

• S1 | 완전탐색

N의 범위가 매우 작으므로 완전탐색을 하는 문제이다.

벽을 세울 수 있는 빈 공간을 리스트로 구하고,

콤비네이션(3)을 한다. ( 벽을 3개 세워야 하므로 )

 

벽을 세우면 감시를 시작한다.

선생님리스트도 만들어서 상하좌우 감시를 한다.

감시를 하던 도중 끝까지 가거나 벽을 만나면 해당 방향의 감시는 멈추고

학생을 만나면 감시에 성공하므로

그 벽은 다시 철거하고 다른 벽을 세운다.

선생님이 모든 방향에 대해서 감시에 실패할 때까지 반복한다.

 

💻소스 코드

from itertools import combinations as cb


def watch():
    for teacher in teacher_list:
        x, y = teacher
        # 상
        nx, ny = x, y
        while nx > 0:
            nx -= 1
            if hallway[nx][ny] == 'S':
                return False

            if hallway[nx][ny] == 'O':
                break
        # 하
        nx, ny = x, y
        while nx < N - 1:
            nx += 1
            if hallway[nx][ny] == 'S':
                return False
            if hallway[nx][ny] == 'O':
                break
        # 좌
        nx, ny = x, y
        while ny > 0:
            ny -= 1
            if hallway[nx][ny] == 'S':
                return False
            if hallway[nx][ny] == 'O':
                break
        # 우
        nx, ny = x, y
        while ny < N - 1:
            ny += 1
            if hallway[nx][ny] == 'S':
                return False
            if hallway[nx][ny] == 'O':
                break
    return True


if __name__ == '__main__':
    N = int(input())
    hallway = [input().split() for _ in range(N)]

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

    # 벽 3개 뽑기
    for walls in cb(empty_list, 3):

        # 벽 세우기
        for wall in walls:
            x, y = wall
            hallway[x][y] = 'O'
        # 감시하기
        if watch():
            print('YES')
            break
        # 벽 허물기
        for wall in walls:
            x, y = wall
            hallway[x][y] = 'X'
    else:
        print('NO')
 

 

📕문제 확인

출처: BACKJOON ONLINE JUDGE

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

18428번: 감시 피하기