PS/백준

14502번 - 연구소

ForteQook 2022. 7. 16. 18:05

문제

 

먼저 문제를 어떻게 접근할지 생각해보자. 문제가 요구하는 것은, 빈칸에 3개의 벽을 세웠을 때 바이러스가 퍼지는 경우 중 최상의 상태 (빈칸이 가장 많이 남은 상태) 를 찾아 빈칸의 개수를 출력하는 것이다. 문제의 요구사항을 다음과 같이 나눠볼 수 있다.

  1. 빈칸에 3개의 벽을 세우는 모든 경우의 수
  2. 과정 1 이후에, 바이러스가 퍼졌을 때의 상태
  3. 과정 2 이후에, 남아있는 빈칸의 개수
  4. 결과 : 남아있는 빈칸의 최대 개수

 과정 1은, 크게는 두가지 경우로 나눠 접근 가능하다. 첫 번째는 DFS나 BFS를 직접 구현해서, 깊이 3 까지 도달했을 때 그 이후 과정들을 시행해주는 것이다. 두 번째는 itertools의 permutations 를 이용해서 벽을 세울 수 있는 모든 경우의 수를 구한 다음, 각 경우에 대해 나머지 과정들을 시행해주는 것이다.

 과정 2는 역시 DFS나 BFS로 구현할 수 있다. 과정 1처럼 깊이 3까지만 탐색한다는 식의 제한사항이 없기 때문에, permutations를 이용하는 것보다는 간단히 DFS나 BFS를 사용하는 편이 좋아보인다.

 과정 3은 말 그래도 남아있는 빈칸의 개수를 세는 것이다.

 과정 4에서, 과정 3을 통해 가져온 결과들의 최대값을 구해 출력하면 될 것이다.

과정 1

 가장 먼저 DFS로 구현해보자. 재귀 함수를 탈출하는 조건은 벽을 3개 까지 세웠을 때, 즉 깊이 3까지 탐색한 경우가 될 것이며, 각 단계에서는 0인 요소를 찾아 1로 바꿔주는 것이다. 이를 정리해보면 다음과 같다.

  1. 깊이 3이면, 남아있는 빈칸의 개수를 세고 결과값을 갱신한 뒤 탈출.
  2. 각 단계에서 그래프 요소를 순회하며 0을 찾아 1로 바꿔줌.
  3. 깊이를 한 단계 올리고, 재귀 함수 호출.

 이를 코드로 정리하면 다음과 같을 것이다.

def dfs_solution(cnt):
  global result
  # 울타리가 세개 설치되면
  if cnt == 3:
    # 그래프 상에서 바이러스가 발견되면, 바이러스를 퍼뜨림.
    # 현재 그래프에 빈 칸이 얼마나 남아있는지 구한 뒤, 결과값 갱신.

  # 울타리 설치
  for row in range(n):
    for col in range(m):
      # 빈 칸이 발견되면
      if graph[row][col] == 0:
        # 벽을 세우고
        # 깊이를 한 단계 올린 뒤 재귀 호출.
        # 재귀 함수가 깊이 정보만 받고 참조 하는 그래프는 전역적으로 선언되어 있기 때문에, 벽을 다시 허물고 깊이 정보를 현재 깊이 상태로 되돌림.

 물론 이렇게 하지 않고 조금 더 간단하면서 빠른 방법이 있다. 깊이 3까지만 탐색한다는 제한 사항이 명백하게 주어져있기 때문에, combinations로 빈 칸 좌표 세개의 조합을 구해주는 방법이다.

# 0인 요소의 위치를 넣어줄 리스트
zerosLoc = []
for row in range(n):
  for col in range(m):
  	# 요소가 0인 위치를 리스트에 삽입
    if graph[row][col] == 0:
      zerosLoc.append((row,col))

# 0의 개수, 즉 결과값을 담아줄 리스트
cntList = []
for zeroCombs in combinations(zerosLoc,3):
  _graph = copy.deepcopy(graph)
  # 각 조합에 대해 0인 요소를 1로 바꿔줌.
  for zeroComb in zeroCombs:
    row, col = zeroComb
    _graph[row][col] = 1
  # 벽이 세워진 그래프에 바이러스를 퍼뜨린 후, 남아있는 0의 개수를 가져와 리스트에 담아줌.
  cntList.append(zeroCounter(_graph))

과정 2

 바이러스를 퍼뜨리는 과정이다. 과정 1은 뚜렷하게 조합으로 경우의 수를 구할 수 있었지만, 해당 과정은 0인 인접요소들을 2로 바꿔준다는 조건만 있으므로 BFS나 DFS로 간단히 구현하는게 좋아보인다.

# 바이러스 퍼뜨리기

def dfs_virus(row,col):
  for i in range(4):
    nRow = row + dRow[i]
    nCol = col + dCol[i]
    if nRow >= 0 and nRow < n and nCol >= 0 and nCol < m:
      if _graph[nRow][nCol] == 0:
        _graph[nRow][nCol] = 2
        dfs_virus(nRow,nCol)

def bfs_virus(row,col):
  q = deque([(row,col)])
  while q:
    now = q.popleft()
    row,col = now
    for i in range(4):
      nRow = row + dRow[i]
      nCol = col + dCol[i]
      if nRow >= 0 and nRow < n and nCol >= 0 and nCol < m:
        if _graph[nRow][nCol] == 0:
          _graph[nRow][nCol] = 2
          q.append((nRow,nCol))

과정 3

 그냥 0의 개수를 세어주기만 하면 된다.

def get_score():
  score = 0
  for row in range(n):
    for col in range(m):
      if _graph[row][col] == 0:
        score += 1
  return score

코드

DFS + DFS/BFS

import sys
from collections import deque

input = sys.stdin.readline

n,m = map(int, input().split())
graph = []
_graph = [[0]*m for _ in range(n)]

for _ in range(n):
  graph.append(list(map(int, input().split())))

# 서, 남, 동, 북
dRow = [-1,0,1,0]
dCol = [0,1,0,-1]

#
result = 0

# 바이러스 퍼뜨리기

def dfs_virus(row,col):
  for i in range(4):
    nRow = row + dRow[i]
    nCol = col + dCol[i]
    if nRow >= 0 and nRow < n and nCol >= 0 and nCol < m:
      if _graph[nRow][nCol] == 0:
        _graph[nRow][nCol] = 2
        dfs_virus(nRow,nCol)

# def bfs_virus(row,col):
#   q = deque([(row,col)])
#   while q:
#     now = q.popleft()
#     row,col = now
#     for i in range(4):
#       nRow = row + dRow[i]
#       nCol = col + dCol[i]
#       if nRow >= 0 and nRow < n and nCol >= 0 and nCol < m:
#         if _graph[nRow][nCol] == 0:
#           _graph[nRow][nCol] = 2
#           q.append((nRow,nCol))

def get_score():
  score = 0
  for row in range(n):
    for col in range(m):
      if _graph[row][col] == 0:
        score += 1
  return score

def dfs_solution(cnt):
  global result
  # 울타리가 세개 설치되면
  if cnt == 3:
    for row in range(n):
      for col in range(m):
        _graph[row][col] = graph[row][col]
    for row in range(n):
      for col in range(m):
        if _graph[row][col] == 2:
          dfs_virus(row,col)
    result = max(result, get_score())
    return
  # 울타리 설치
  for row in range(n):
    for col in range(m):
      if graph[row][col] == 0:
        graph[row][col] = 1
        cnt += 1
        dfs_solution(cnt)
        graph[row][col] = 0
        cnt -= 1

dfs_solution(0)
print(result)

Combinations + BFS

import sys
import copy
from collections import deque
from itertools import combinations

input = sys.stdin.readline

n,m = map(int, input().split())
graph = [[] for _ in range(n)]

for i in range(n):
  graph[i] = list(map(int, input().split()))

# 북, 동, 남, 서
moves = [(1,0),(0,1),(-1,0),(0,-1)]

# 바이러스 퍼뜨리기
def bfs(start, graph):
  q = deque([start])
  while q:
    now = q.popleft()
    for move in moves:
      next_loc = (now[0]+move[0], now[1]+move[1])
      if next_loc[0] >= 0 and next_loc[0] < n and next_loc[1] >= 0 and next_loc[1] < m:
        if graph[next_loc[0]][next_loc[1]] == 0:
          graph[next_loc[0]][next_loc[1]] = 2
          q.append(next_loc)
        
def zeroCounter(graph):
  for row in range(n):
    for col in range(m):
      if graph[row][col] == 2:
        bfs((row,col),graph)

  cnt = 0
  for row in range(n):
    for col in range(m):
      if graph[row][col] == 0:
        cnt += 1
  return cnt

# 0 인 위치 찾기
zerosLoc = []
for row in range(n):
  for col in range(m):
    if graph[row][col] == 0:
      zerosLoc.append((row,col))

cntList = []
for zeroCombs in combinations(zerosLoc,3):
  _graph = copy.deepcopy(graph)
  for zeroComb in zeroCombs:
    row, col = zeroComb
    _graph[row][col] = 1
  cntList.append(zeroCounter(_graph))

print(max(cntList))

 combinations를 쓰는 쪽이 메모리, 시간면에서 우세한 결과를 얻을 수 있었다.

  메모리 시간
DFS + DFS/BFS 146852 KB 4996 ms
Combinations + BFS 122884 KB 1456 ms

풀이 2

DFS로 벽을 3개 세운뒤에, 바이러스를 유출 시킨 뒤 answer를 갱신해주면 되는 간단한 문제이다. DFS와 BFS를 이용하여 풀이했고, 1700ms 정도가 나왔다.

from collections import deque

N,M = map(int,input().split())
board = []
for _ in range(N):
    board.append(list(map(int,input().split())))

dRow = [-1,0,1,0]
dCol = [0,-1,0,1]


def spread():
    global answer
    cpy_board = [[*elem] for elem in board]
    for row in range(N):
        for col in range(M):
            if cpy_board[row][col] == 2:
                q = deque()
                q.append((row,col))
                while q:
                    r,c = q.popleft()
                    for i in range(4):
                        nr,nc = r+dRow[i],c+dCol[i]
                        if 0 <= nr < N and 0 <= nc < M and cpy_board[nr][nc] == 0:
                            cpy_board[nr][nc] = 3
                            q.append((nr,nc))

    result = 0
    for row in range(N):
        result += cpy_board[row].count(0)

    answer = max(answer,result)
    return


def set_walls(cnt):
    if cnt == 3:
        spread()
        return

    for row in range(N):
        for col in range(M):
            if board[row][col] == 0:
                board[row][col] = 1
                set_walls(cnt+1)
                board[row][col] = 0


answer = 0
set_walls(0)
print(answer)

'PS > 백준' 카테고리의 다른 글

16234번 - 인구 이동  (0) 2022.07.21
18428번 - 감시 피하기  (0) 2022.07.20
14888번 - 연산자 끼워넣기  (0) 2022.07.20
18405번 - 경쟁적 전염  (0) 2022.07.19
18352번 - 특정 거리의 도시 찾기  (0) 2022.07.15

'PS/백준'의 다른글

  • 현재글14502번 - 연구소

관련글

댓글

티스토리툴바