[백준] 14502. 연구소 풀이 (Python, JavaScript)

14502번: 연구소

접근한 방법

dfs를 이용한 조합과 bfs를 이용한 탐색을 이용한 문제입니다.

먼저 벽을 세울 3개의 자리를 순차적으로 구성해봐야 하므로 dfs를 이용해서 3개가 카운트될 때까지 빈칸을 찾아 진입합니다. 3개가 구성되면 bfs를 이용해 바이러스를 퍼트립니다.

 

bfs를 여러번 동작해야 하므로 탐색을 시작할 때 미리 구성된 큐와 연구소 배열을 복사합니다. python에서는 큐는 deque의 copy, 어레이는 copy 라이브러리의 deepcopy를 이용하고 js에서는 어레이만 JSON 메서드를 사용합니다. 큐는 js에 없으므로 front 변수를 두어 큐처럼 활용합니다.

 

상하좌우를 탐색하여 0인 자리는 2로 만들고 큐에 다시 탐색 위치를 넣어줍니다. 탐색이 끝나면 바이러스가 진입할 수 있는 자리가 모두 2로 채워질 것이고 남아있는 0의 자리의 개수를 세어 최댓값을 구해주면 됩니다.

 

Python

import sys
sys.stdin = open("input.txt", "r") # 제거
input = sys.stdin.readline

n, m = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]
print(arr)
from collections import deque
from copy import deepcopy
deq, result = deque(), 0
for i in range(n):
    for j in range(m):
        if arr[i][j] == 2:
            deq.append((i, j))
def bfs():
    q, array = deq.copy(), deepcopy(arr)
    while q:
        r, c = q.popleft()
        for d in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            dr, dc = r + d[0], c + d[1]
            if dr < 0 or dc < 0 or dr >= n or dc >= m:
                continue
            if not array[dr][dc]:
                array[dr][dc] = 2
                q.append((dr, dc))
    res = 0
    for i in range(n):
        for j in range(m):
            if not array[i][j]:
                res += 1
    return res
def dfs(cnt):
    global result
    if cnt == 3:
        result = max(result, bfs())
        return
    for i in range(n):
        for j in range(m):
            if not arr[i][j]:
                arr[i][j] = 1
                dfs(cnt + 1)
                arr[i][j] = 0
dfs(0)
print(result)

JavaScript

function solution(n, m, array) {
  const deq = [];
  for (let i = 0; i < n; i += 1) {
    for (let j = 0; j < m; j += 1) {
      if (array[i][j] === 2) deq.push([i, j]);
    }
  }
  const bfs = () => {
    const q = deq.slice();
    let front = 0;
    const arr = JSON.parse(JSON.stringify(array));
    while (q[front]) {
      const [r, c] = q[front++];
      for (const d of [
        [-1, 0],
        [1, 0],
        [0, -1],
        [0, 1],
      ]) {
        const [dr, dc] = [r + d[0], c + d[1]];
        if (dr < 0 || dc < 0 || dr >= n || dc >= m) continue;
        if (!arr[dr][dc]) {
          arr[dr][dc] = 2;
          q.push([dr, dc]);
        }
      }
    }
    let res = 0;
    for (let i = 0; i < n; i += 1) {
      for (let j = 0; j < m; j += 1) {
        if (!arr[i][j]) res += 1;
      }
    }
    return res;
  };
  let result = 0;
  const dfs = (cnt) => {
    if (cnt == 3) return (result = Math.max(result, bfs()));
    for (let i = 0; i < n; i += 1) {
      for (let j = 0; j < m; j += 1) {
        if (!array[i][j]) {
          array[i][j] = 1;
          dfs(cnt + 1);
          array[i][j] = 0;
        }
      }
    }
  };
  dfs(0);
  return result;
}

  solution(7, 7, [
    [2, 0, 0, 0, 1, 1, 0],
    [0, 0, 1, 0, 1, 2, 0],
    [0, 1, 1, 0, 1, 0, 0],
    [0, 1, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 1, 1],
    [0, 1, 0, 0, 0, 0, 0],
    [0, 1, 0, 0, 0, 0, 0],
  ])