[Gold V] 감시 피하기 - 18428

문제 링크

성능 요약

메모리: 32412 KB, 시간: 36 ms

분류

브루트포스 알고리즘, 백트래킹

문제 설명

NxN 크기의 복도가 있다. 복도는 1x1 크기의 칸으로 나누어지며, 특정한 위치에는 선생님, 학생, 혹은 장애물이 위치할 수 있다. 현재 몇 명의 학생들은 수업시간에 몰래 복도로 빠져나왔는데, 복도로 빠져나온 학생들은 선생님의 감시에 들키지 않는 것이 목표이다.

각 선생님들은 자신의 위치에서 상, 하, 좌, 우 4가지 방향으로 감시를 진행한다. 단, 복도에 장애물이 위치한 경우, 선생님은 장애물 뒤편에 숨어 있는 학생들은 볼 수 없다. 또한 선생님은 상, 하, 좌, 우 4가지 방향에 대하여, 아무리 멀리 있더라도 장애물로 막히기 전까지의 학생들은 모두 볼 수 있다고 가정하자.

다음과 같이 3x3 크기의 복도의 정보가 주어진 상황을 확인해보자. 본 문제에서 위치 값을 나타낼 때는 (행,열)의 형태로 표현한다. 선생님이 존재하는 칸은 T, 학생이 존재하는 칸은 S, 장애물이 존재하는 칸은 O로 표시하였다. 아래 그림과 같이 (3,1)의 위치에는 선생님이 존재하며 (1,1), (2,1), (3,3)의 위치에는 학생이 존재한다. 그리고 (1,2), (2,2), (3,2)의 위치에는 장애물이 존재한다.

이 때 (3,3)의 위치에 존재하는 학생은 장애물 뒤편에 숨어 있기 때문에 감시를 피할 수 있다. 하지만 (1,1)과 (2,1)의 위치에 존재하는 학생은 선생님에게 들키게 된다.

학생들은 복도의 빈 칸 중에서 장애물을 설치할 위치를 골라, 정확히 3개의 장애물을 설치해야 한다. 결과적으로 3개의 장애물을 설치하여 모든 학생들을 감시로부터 피하도록 할 수 있는지 계산하고자 한다. NxN 크기의 복도에서 학생 및 선생님의 위치 정보가 주어졌을 때, 장애물을 정확히 3개 설치하여 모든 학생들이 선생님들의 감시를 피하도록 할 수 있는지 출력하는 프로그램을 작성하시오.

예를 들어 N=5일 때, 다음과 같이 선생님 및 학생의 위치 정보가 주어졌다고 가정하자.

이 때 다음과 같이 3개의 장애물을 설치하면, 모든 학생들을 선생님의 감시로부터 피하도록 만들 수 있다.

입력

첫째 줄에 자연수 N이 주어진다. (3 ≤ N ≤ 6) 둘째 줄에 N개의 줄에 걸쳐서 복도의 정보가 주어진다. 각 행에서는 N개의 원소가 공백을 기준으로 구분되어 주어진다. 해당 위치에 학생이 있다면 S, 선생님이 있다면 T, 아무것도 존재하지 않는다면 X가 주어진다.

단, 전체 선생님의 수는 5이하의 자연수, 전체 학생의 수는 30이하의 자연수이며 항상 빈 칸의 개수는 3개 이상으로 주어진다.

출력

첫째 줄에 정확히 3개의 장애물을 설치하여 모든 학생들을 감시로부터 피하도록 할 수 있는지의 여부를 출력한다. 모든 학생들을 감시로부터 피하도록 할 수 있다면 "YES", 그렇지 않다면 "NO"를 출력한다.

---

문제 풀이

문제 분석

이 문제는 NxN 크기의 복도에서 선생님, 학생, 장애물이 주어진 상황에서, 빈 칸(X)에 정확히 3개의 장애물(O)을 설치하여 모든 학생(S)이 선생님(T)의 감시를 피할 수 있도록 하는 것이 가능한지 판별하는 문제입니다.

• 입력:
  • 첫째 줄에 복도의 크기 N (3 ≤ N ≤ 6)이 주어집니다.
  • 다음 N개의 줄에 걸쳐 N개의 문자가 공백으로 구분되어 복도의 정보가 주어집니다. 'S'는 학생, 'T'는 선생님, 'X'는 빈 칸을 의미합니다.
• 출력:
  • 모든 학생들이 감시를 피하도록 할 수 있다면 "YES"를, 그렇지 않다면 "NO"를 출력합니다.
• 감시 규칙:
  • 선생님은 자신의 위치에서 상, 하, 좌, 우 4가지 방향으로 감시합니다.
  • 장애물(O)이 있으면 그 뒤편에 있는 학생은 볼 수 없습니다.
  • 선생님은 장애물로 막히기 전까지 아무리 멀리 있어도 학생을 볼 수 있습니다.

접근 방법

문제에서 N의 크기가 최대 6으로 매우 작습니다 (N=6일 때 복도 크기 36칸). 따라서 모든 빈 칸 중에서 3개의 장애물을 설치하는 모든 경우의 수를 확인하는 **브루트포스 알고리즘(완전 탐색)**으로 해결할 수 있습니다. 각 경우마다 모든 학생이 선생님의 감시를 피할 수 있는지 확인하는 방식으로 접근합니다.

세부적인 접근 단계는 다음과 같습니다.

1. 복도 정보를 입력받고, 선생님의 위치를 저장합니다.
2. 장애물을 설치할 수 있는 모든 빈 칸(X)을 후보로 선정합니다.
3. 선정된 후보 칸들 중에서 3개를 선택하는 모든 조합을 시도합니다. itertools.combinations 라이브러리를 사용하면 효율적으로 조합을 생성할 수 있습니다.
4. 각 조합(3개의 장애물 위치)에 대해, 모든 학생들이 선생님의 감시를 피할 수 있는지 확인하는 함수를 실행합니다.
5. 만약 어떤 조합에서 모든 학생들이 감시를 피할 수 있다면, "YES"를 출력하고 프로그램을 종료합니다.
6. 모든 조합을 시도했는데도 조건을 만족하는 경우가 없다면, "NO"를 출력합니다.

코드에서는 get_can_blocks 함수를 통해 감시 경로에 있는 빈 칸들만을 후보로 삼아 조합의 수를 줄이는 최적화를 시도했습니다. 이는 모든 빈 칸을 후보로 삼는 것보다 효율적일 수 있습니다.

구현 설명

1. 초기 설정 및 선생님 위치 저장

• 프로그램 시작 시, N을 입력받고 NxN 크기의 복도(board)를 2차원 리스트 형태로 저장합니다.
• 복도를 순회하며 선생님의 위치를 찾아 teachers 리스트에 (행, 열) 튜플 형태로 저장합니다. 이 정보는 이후 감시 시뮬레이션에 사용됩니다.

2. 장애물 설치 후보 칸 탐색 (get_can_blocks 함수)

• 이 함수는 장애물을 설치할 만한 유효한 빈 칸(X)의 후보를 찾습니다.
• teachers 리스트에 있는 각 선생님에 대해 상하좌우 4방향으로 감시를 시뮬레이션합니다.
• 선생님 시야 내에서 X (빈 칸)을 만나면, 해당 칸은 잠재적인 장애물 설치 위치가 될 수 있으므로 new_blocks 임시 집합에 추가합니다.
• 만약 S (학생)을 만나면, 해당 학생이 선생님에게 들킨다는 뜻이므로, 지금까지 new_blocks에 모아둔 칸들은 이 학생을 가릴 수 있는 유효한 후보가 됩니다. 따라서 이 칸들을 최종 blocks 집합에 추가하고 현재 방향 탐색을 중단합니다.
• O (장애물)을 만나면, 시야가 막히므로 현재 방향 탐색을 중단합니다.
• 맵 경계를 벗어나면 탐색을 중단합니다.
• 이 과정을 통해 모든 선생님의 시야 내에 있는 학생을 가릴 수 있는 빈 칸들만이 can_blocks 리스트에 담겨 반환됩니다. 이는 모든 빈 칸을 후보로 삼는 것보다 경우의 수를 줄여주는 최적화입니다.

3. 학생 감시 여부 확인 (check 함수)

• 이 함수는 인자로 주어진 3개의 blocks (장애물 설치 위치)가 있을 때, 모든 학생이 선생님의 감시를 피할 수 있는지 확인합니다.
• teachers 리스트의 모든 선생님에 대해 반복합니다.
• 각 선생님에 대해 상하좌우 4방향으로 시뮬레이션하며 감시를 진행합니다.
• 탐색 경로에서 다음 규칙을 따릅니다.
  • 맵 경계를 벗어나면 현재 방향의 감시를 중단합니다.
  • S (학생)을 만나면, 해당 학생이 들킨 것이므로 즉시 False를 반환합니다 (모든 학생이 감시를 피할 수 없음).
  • 현재 칸이 blocks에 포함된 장애물 위치이거나 원래 board에 O (장애물)이 있다면, 시야가 막히므로 현재 방향의 감시를 중단합니다.
• 모든 선생님이 모든 방향으로 감시를 마쳤는데도 False가 반환되지 않았다면, 모든 학생이 감시를 피할 수 있었다는 의미이므로 True를 반환합니다.

4. 조합 생성 및 결과 출력

• get_can_blocks() 함수를 호출하여 장애물 설치 후보 can_blocks 리스트를 얻습니다.
• itertools.combinations(can_blocks, l)를 사용하여 can_blocks에서 l개(최대 3개, 후보가 3개 미만이면 그 개수만큼)의 장애물 위치를 선택하는 모든 조합을 생성합니다.
• 각 조합(a)에 대해 check(*a) 함수를 호출하여 모든 학생이 감시를 피할 수 있는지 확인합니다.
• check() 함수가 True를 반환하는 조합을 하나라도 찾으면, "YES"를 출력하고 즉시 프로그램을 종료합니다.
• 모든 가능한 조합을 시도했지만 check() 함수가 True를 반환하는 경우가 없었다면, "NO"를 출력합니다.

⏱복잡도 분석

• 시간 복잡도:

  • N의 최대 크기는 6입니다.
  • get_can_blocks() 함수: 선생님의 수(최대 5) * 4방향 * N (복도 한 줄의 길이). 이 과정에서 set 연산이 포함됩니다. 대략 O(T * N) 정도의 시간이 소요됩니다. (T는 선생님 수)
  • check() 함수: 선생님의 수(최대 5) * 4방향 * N (복도 한 줄의 길이). 이 과정에서 set (blocks) 확인이 포함됩니다. 대략 O(T * N) 정도의 시간이 소요됩니다.
  • 메인 로직(combinations): 장애물 설치 후보 can_blocks의 최대 크기는 N*N (36)입니다. 이 중에서 3개를 선택하는 조합의 수는 C(N^2, 3) 입니다. C(36, 3) = (36 * 35 * 34) / (3 * 2 * 1) = 3570가지 입니다.
  • 따라서 전체 시간 복잡도는 대략 O(C(N^2, 3) * T * N)으로 나타낼 수 있습니다. 3570 * 5 * 6 = 107,100으로, 매우 작은 연산 횟수이므로 제한 시간(36ms) 내에 충분히 해결 가능합니다.

• 공간 복잡도:

  • board: NxN 크기의 2차원 리스트이므로 O(N^2) 공간을 사용합니다.
  • teachers: 선생님의 수(최대 5)만큼 저장하므로 O(T) 공간을 사용합니다.
  • can_blocks: 최대 N*N개의 좌표를 저장할 수 있으므로 O(N^2) 공간을 사용합니다.
  • blocks (check 함수 내부): 항상 3개의 좌표를 저장하므로 O(1) 공간을 사용합니다.
  • 종합적으로 O(N^2)의 공간 복잡도를 가집니다. N=6일 때 36칸이므로 공간 사용량도 매우 적습니다.

핵심 포인트

1. 제약 조건 활용한 브루트포스: N의 크기가 3에서 6으로 매우 작기 때문에, 모든 빈 칸에 3개의 장애물을 설치하는 모든 경우의 수를 완전 탐색하는 것이 가능합니다. itertools.combinations를 사용하여 조합을 효율적으로 생성합니다.
2. 명확한 감시 로직 구현: 선생님의 시야가 장애물에 의해 막히는 규칙을 check 함수 내에서 정확히 구현하는 것이 중요합니다. 각 선생님의 위치에서 4방향으로 탐색하며, 학생을 만나면 False, 장애물을 만나면 해당 방향 탐색 중단 로직을 포함합니다.
3. 최적화된 장애물 후보 선정 (get_can_blocks): 모든 빈 칸을 장애물 설치 후보로 고려하는 대신, 실제로 선생님의 감시 경로에 있고 학생을 가릴 수 있는 빈 칸들만 can_blocks로 선정함으로써 탐색해야 할 조합의 수를 줄이는 최적화를 시도했습니다. 이는 필수적이지는 않지만, 작은 N에서도 효율을 높일 수 있는 방법입니다.

풀이 코드

import sys
from itertools import combinations

input = sys.stdin.readline

n = int(input())

board = []
for i in range(n):
    board.append(list(input().split()))

teachers = []
for i in range(n):
    for j in range(n):
        if board[i][j] == "T":
            teachers.append((i,j))

directions = [(0,1),(0,-1),(1,0),(-1,0)]
def get_can_blocks():
    blocks = set()
    for x,y in teachers:
        for dx,dy in directions:
            new_blocks = set()
            sx,sy = x,y
            while True:
                sx,sy = sx+dx,sy+dy
                if 0<=sx<n and 0<=sy<n:
                    if board[sx][sy] == "X":
                        new_blocks.add((sx,sy))

                    elif board[sx][sy] == "S":
                        blocks = blocks.union(new_blocks)
                        break

                    elif board[sx][sy] == "O":
                        break

                else:
                    break
    
    return list(blocks)

def check(*blocks):
    blocks = set(blocks)
    for x,y in teachers:
        for dx,dy in directions:
            sx,sy = x,y
            while True:
                sx,sy = sx+dx,sy+dy
                if 0<=sx<n and 0<=sy<n:
                    if board[sx][sy] == "S":
                        return False
                    elif (sx,sy) in blocks or board[sx][sy] == "O":
                        break
                    
                else:
                    break
    return True                     

can_blocks = get_can_blocks()

l = min(3,len(can_blocks))

for a in combinations(can_blocks, l):
    if check(*a):
        print("YES")
        break

else:
    print("NO")