[백준] 18428. 감시 피하기 풀이 (Python, JavaScript)

18428번: 감시 피하기

접근한 방법

완전탐색, 백트래킹 문제입니다. 장애물 3개를 놓을 수 있는 모든 경우의 수를 탐색합니다. 각 경우에서 선생님(T)으로부터 4방향을 모두 검사하여 학생(S)이 한명이라도 발견되는 경우 즉시 탐색을 멈춥니다. 발견되지 않으면 횟수를 카운트합니다.

카운트한 횟수와 선생님의 수가 일치할 경우 모든 감시를 피한 것으로 처리하고 그렇지 않은 경우는 피하지 못한것이 됩니다.

 

Python

import sys
input = sys.stdin.readline

n = int(input())
arr = [list(input().split()) for _ in range(n)]
direction = ((-1, 0), (1, 0), (0, -1), (0, 1))
t = 0
result = "NO"
for i in arr:
    t += i.count("T")

def setting(o):
    global result
    def finded(r, c):
        for [p, q] in direction:
            dr, dc = r + p, c + q
            while 1:
            	# 장애물이 있거나 맵 범위를 벗어난 경우
                if dr < 0 or dc < 0 or dr >= n or dc >= n or arr[dr][dc] == "O":
                    break
                # 학생이 발견된 경우
                if arr[dr][dc] == "S":
                    return 1
                dr, dc = dr + p, dc + q
        return 0
    # 장애물을 모두 놓았으면 선생의 감시 방향 체크
    if o == 3:
        checked = 0
        for i in range(n):
            for j in range(n):
                if arr[i][j] == "T" and not finded(i, j):
                        checked += 1
        # 감시를 피한 횟수와 선생의 수가 일치한 경우
        if checked == t:
            result = "YES"
        return
    # 장애물을 놓을 모든 경우의 수 진입
    for i in range(n):
        for j in range(n):
            if arr[i][j] == "X":
                arr[i][j] = "O"
                setting(o + 1)
                arr[i][j] = "X"
setting(0)
print(result)

JavaScript

function solution(n, arr) {
  const direction = [
    [-1, 0],
    [1, 0],
    [0, -1],
    [0, 1],
  ];
  let [t, result] = [0, "NO"];
  for (const i of arr) t += i.reduce((a, c) => a + (c === "T"), 0);
  const setting = (o) => {
    const finded = (r, c) => {
      for (const [p, q] of direction) {
        let [dr, dc] = [r + p, c + q];
        while (1) {
          if (dr < 0 || dc < 0 || dr >= n || dc >= n || arr[dr][dc] === "O")
            break;
          if (arr[dr][dc] === "S") return 1;
          [dr, dc] = [dr + p, dc + q];
        }
      }
    };
    if (o === 3) {
      let checked = 0;
      for (let i = 0; i < n; i += 1) {
        for (let j = 0; j < n; j += 1) {
          if (arr[i][j] === "T" && !finded(i, j)) checked += 1;
        }
      }
      if (checked === t) result = "YES";
      return;
    }
    for (let i = 0; i < n; i += 1) {
      for (let j = 0; j < n; j += 1) {
        if (arr[i][j] === "X") {
          arr[i][j] = "O";
          setting(o + 1);
          arr[i][j] = "X";
        }
      }
    }
  };

  setting(0);
  return result;
}

console.log(
  solution(5, [
    ["X", "S", "X", "X", "T"],
    ["T", "X", "S", "X", "X"],
    ["X", "X", "X", "X", "X"],
    ["X", "T", "X", "X", "X"],
    ["X", "X", "T", "X", "X"],
  ])
);