[本題]DFS/BFS-監視を避ける

🔔 質問する

NxNサイズの廊下があります.廊下は1×1の大きさの格子に分かれており、特定の位置は先生、学生、障害物であってもよい.今、何人かの学生が授業中にこっそり廊下を抜け出して、廊下を抜け出した学生が先生に発見されないようにすることを目標にしています.
各先生は自分の位置で上、下、左、右の4つの方向に監視しています.しかし、廊下に障害物があると、先生は障害物の後ろに隠れている学生を見ることができません.また、先生は上、下、左、右の4つの方向に対して、どんなに遠くても障害物が詰まる前に学生が見ることができると仮定しています.
本問題では,位置値を表す場合(行,列)の形式で表す.先生が存在する格子はTで,学生が存在する格子はSで,障害物が存在する格子はOである.
学生たちは廊下の空きスペースから障害物を設置する場所を選び、3つの障害物を正しく設置しなければならない.その結果、3つの障害物が設置され、すべての学生が監視されないようにすることができるかどうかを計算した.NxNサイズの廊下で学生と先生の位置情報を取得する場合は、3つの障害物を正しく設定し、すべての学生が先生の監視を避けることができるかどうかを印刷するプログラムを作成してください.

入力

の最初の行には自然数Nがある.(3<=N<=6)

2 2行目にはN行目の廊下情報があります.行ごとにN個の要素があり、スペースで区切られています.もしあなたの位置に学生がいたら、S、もしあなたが先生がいたら、T、何も存在しなければ、Xはあなたにあげます.スペースの数は常に3より大きい.

しゅつりょく

の第1行では、3つの障害を正確に設定し、すべての学生が監視されることを回避できるかどうかを出力する.すべての生徒が監視されないようにすることができれば「YES」、そうでなければ「NO」を出力する.

🎯 解答方法

この問題は、3つの障害物を正しく設置したすべての状況を確認し、すべての学生が監視されないように印刷するかどうかを確認しなければならない.では、すべての場合に3つの障害物を正しく設定する数を考えてみましょう.廊下の大きさはNxNで、Nは最大6です.したがって、3つの障害物を正確にセットするすべての組合せの数は、最悪の場合36 C 3となる.これは10000個以下であるため、すべての組合せを考慮して、完全なナビゲーションを行うこともタイムアウトなしに問題を解決することができる.したがって、DFSまたはBFSを使用してすべての組合せを返す関数を記述したり、Pythonの組合せライブラリを使用してすべての組合せを検索したりすることができます.また、3つの障害物が正しくセットされている組み合わせごとに、先生方の位置座標を確認し、先生方の位置で上、下、左、右を確認し、学生1人が検出されたかどうかを確認します.個別のwatch()メソッドを実施すれば便利です.

💻 Pythonコード

from itertools import combinations

n = int(input()) # 복도의 크기
board = [] # 복도 정보
teachers = [] # 모든 선생님 위치 정보
space = [] # 모든 빈 공간 위치 정보

for i in range(n):
    board.append(list(map(int, input().split())))
    for j in range(n):
        # 선생님이 존재하는 위치 저장
        if board[i][j] == 'T':
            teachers.append((i, j))
        # 장애물을 설치할 수 있는 (빈 공간) 위치 저장
        if board[i][j] == 'X':
            space.append((i, j))

# 특정 방향으로 감시를 진행 (학생 발견: True, 학생 미발견: False)
def watch(x, y, direction):
    if direction == 0:
        while y >= 0:
            if board[x][y] == 'S':
                return True
            if board[x][y] == 'O':
                return False
            y -= 1

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

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

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

    return False

# 장애물 설치 이후에, 한 명이라도 학생이 감지되는지 검사
def process():
    for x, y in teachers:
        # 4가지 방향으로 학생을 감지할 수 있는지 확인
        for i in range(4):
            if watch(x, y, i):
                return True

    return False

find = False

# 빈 공간에서 3개를 뽑는 모든 조합을 확인
for data in combinations(space, 3):
    for x, y in data:
        board[x][y] = 'O'
    # 학생이 한 명도 감지되지 않는 경우
    if not process():
        find = True
        break
    # 설치된 장애물 다시 없애기
    for x, y in data:
        board[x][y] = 'X'

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