[백준 14502, 17141, 17142][파이썬] 연구소 1, 2, 3

14502 연구소

https://www.acmicpc.net/problem/14502

14502번: 연구소

 

풀이

3개의 벽을 세울 수 있는 모든 경우의 수에 대해(브루트포스) 각각 바이러스가 퍼져나가게 한 후(bfs) 지도 전체에 대해 탐색하여 0인 곳이 몇 개인지 확인하여 그중 최댓값을 출력한다.

 

- 인풋을 다 받은 후 지도에서 바이러스가 존재하는 곳(2)의 좌표를 virus 리스트에 저장한다. 

- solve 함수에서는 3개의 파라미터를 받는데 map, wall, a이다. 바이러스가 퍼져나가게 하면 원래 상태로 복구가 어렵기 때문에 map에는 input으로 받은 map이 아닌 이걸 deepcopy한 복사본을 넣어준다. 

- deepcopy()를 사용하면 시간이 오래 걸리기 때문에 slicing 방식으로 깊은 복사를 해주었다.

- wall은 현재 세운 벽의 개수, a는 벽을 몇번째 열에 세우고 있었는지를 알려주는데 a는 필수는 아니다.

- wall의 값이 3이 됐을 때 너비 우선 탐색 방식으로 바이러스가 퍼져나가도록 한다. 

- 바이러스가 다 퍼져나가면 지도를 처음부터 탐색하여 안전 영역인 0인 곳이 몇 개있는기 세어준다.

- 그 값이 ans 보다 크다면 ans 값을 갱신해주고 마지막에 ans를 출력한다.

import sys
from collections import deque

input = sys.stdin.readline


N, M = map(int, input().split())
map = [list(map(int, input().split())) for _ in range(N)]
ans = 0
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

virus = []
for i in range(N):
  for j in range(M):
    if map[i][j] == 2:
      virus.append((i, j))

def solve(map, wall, a):
  global ans
  
  if wall == 3:
    q = deque(virus)
      
    while q:
      x, y = q.popleft()
      for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]
        if 0 <= nx < N and 0 <= ny < M and map[nx][ny] == 0:
          map[nx][ny] = 2
          q.append((nx, ny))

    temp = 0
    for n in range(N):
      for m in range(M):
        if map[n][m] == 0:
          temp += 1
    ans = max(ans, temp)
    return

  for i in range(a, N):
    for j in range(M):
      if map[i][j] == 0:
        map_copy = [m[:] for m in map]
        map_copy[i][j] = 1
        solve(map_copy, wall+1, i)

solve(map, 0, 0)
print(ans)

 

---

17141 연구소 2

https://www.acmicpc.net/problem/17141

17141번: 연구소 2

위에서 본 연구소 문제와 비슷하지만 이번엔 벽이 아니라 바이러스를 놓아 바이러스가 전체에 퍼지기까지 몇 초의 시간이 걸리는지를 구하는 문제이다.

 

풀이

M개의 바이러스를 놓을 수 있는 모든 경우의 수에 대해(브루트포스) 각각 바이러스가 퍼져나가게 한 후(bfs) 지도 전체에 대해 탐색하여 바이러스가 모두 퍼졌다면 그때까지 걸린 시간 중 최솟값을 출력한다.

 

- 위의 연구소 문제와 전체적인 틀은 비슷하다.

- ans 값은 충분히 큰 값(INF)으로 정해줬다. 만약 ans 값이 탐색이 끝난 후에도 그대로라면 -1을 출력한다.

- 연구소 1에서 벽을 세웠던 방식대로 이번엔 바이러스를 놓아준다. 바이러스를 놓은 곳은 지도에서 3이라고 표시한다. 

- 바이러스 위치를 미리 다 찾아놓았던 연구소 1 풀이와 달리 이번에는 바이러스를 놓을 때 virus 리스트에 바이러스 좌표를 넣어준다. 그리고 탐색이 끝나면 다시 리스트에서 이 좌표를 지워준다.

- 바이러스를 M개만큼 놓으면 바이러스를 퍼뜨린다. 바이러스가 퍼진 곳도 지도에서 3으로 바꿔준다.

- 바이러스가 다 퍼진 후에 지도 전체를 확인하여 0이거나 2인 곳이 있는지 확인한다. 만약 있다면 ans 값을 그대로 두고 없다면 ans 값을 cnt, 바이러스가 퍼지는데 걸린 시간과 비교하여 둘 중 더 작은 값으로 바꿔준다.

import sys
from collections import deque

input = sys.stdin.readline


N, M = map(int, input().split())
map = [list(map(int, input().split())) for _ in range(N)]
ans = 9999
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
virus = []

def solve(map, v, a):
  global ans
  
  if v == M:
    q = deque(virus)
      
    while q:
      x, y, cnt = q.popleft()
      for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]
        if 0 <= nx < N and 0 <= ny < N and (map[nx][ny] == 0 or map[nx][ny] == 2):
          map[nx][ny] = 3
          q.append((nx, ny, cnt+1))

    for n in range(N):
      for m in range(N):
        if map[n][m] == 0 or map[n][m] == 2:
          return
    ans = min(ans, cnt)
    return

  for i in range(a, N):
    for j in range(N):
      if map[i][j] == 2:
        map_copy = [m[:] for m in map]
        map_copy[i][j] = 3
        virus.append((i, j, 0))
        solve(map_copy, v+1, i)
        virus.remove((i, j, 0))

solve(map, 0, 0)
if ans == 9999:
  print('-1')
else:
  print(ans)

 

---

17142 연구소 3

https://www.acmicpc.net/problem/17142

17142번: 연구소 3

연구소 2와 비슷하지만 이번엔 바이러스를 놓는 게 아니라 비활성화 바이러스 중에 어떤 바이러스를 활성화할지 고르는 거다. 그래서 지도에서 2인 부분도 바이러스가 퍼진 상태라고 본다.

 

풀이

활성화할 M개의 바이러스를 고르는 모든 경우의 수에 대해(combinations 사용) 각각 바이러스가 퍼져나가게 한 후(bfs) 지도 전체에 대해 탐색하여 바이러스가 모두 퍼졌다면 그때까지 걸린 시간 중 최솟값을 출력한다.

 

- 전체적인 방식은 연구소 2와 비슷하다.

- 시간 절약을 위해 하나하나 탐색하는 방식이 아닌 바이러스가 위치한 곳을 먼저 한번에 다 찾은 후에 combinations를 사용하여 바이러스 좌표 중에 M개를 고르도록 하였다.

- 비활성화 바이러스를 활성화 시켜 바이러스가 퍼지는 거나 그냥 활성화 바이러스가 계속 퍼지는 거나 결국 결과는 같기 때문에 크게 신경쓰지 않아도 된다. 

- deque에 temp를 추가해줬다. 이걸 추가한 이유는 예를 들어, 빈공간 없이 비활성화 바이러스만 있을 때 이건 이미 바이러스가 다 퍼진 상태이기 때문에 cnt 값이 0이 되어야 한다. 하지만 연구소 2의 코드대로라면 cnt 값은 계속 커진다. 그래서 이를 방지하기 위해 활성화 바이러스에서 비활성화 바이러스로 갈 때 temp 값만 1 더해주고 cnt 값은 그대로 두다가 이 비활성화 바이러스를 지나 다시 그냥 빈 공간에 도달하면 그제야 cnt 값과 temp 값을 같게 해줬다.

- 하지만 이 방식에서는 문제점이 하나 발생하는데 계산 과정에서 마지막에 pop한 게 cnt 값이 최댓값이라는 보장이 사라지기 때문에 제대로된 cnt 값을 구할 수 없다. 그래서 result라는 변수를 추가하여 cnt 값 중 최댓값을 저장하도록 하여 이걸 ans 값에 넣어주었다.

import sys
from collections import deque
from itertools import combinations

input = sys.stdin.readline


N, M = map(int, input().split())
map = [list(map(int, input().split())) for _ in range(N)]
ans = 999999
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
virus = []

for i in range(N):
  for j in range(N):
    if map[i][j] == 2:
      virus.append((i, j))

def solve(map, vs):
  global ans
  
  result = 0
  q = deque()
  for v in vs:
    a, b = v
    map[a][b] = 3
    q.append((a, b, 0, 0))
      
  while q:
    x, y, cnt, temp = q.popleft()
    result = max(result, cnt)
    for k in range(4):
      nx = x + dx[k]
      ny = y + dy[k]
      if 0 <= nx < N and 0 <= ny < N:
        if map[nx][ny] == 0:
          map[nx][ny] = 3
          q.append((nx, ny, temp+1, temp+1))
        if map[nx][ny] == 2:
          map[nx][ny] = 3
          q.append((nx, ny, cnt, temp+1))

  for n in range(N):
    for m in range(N):
      if map[n][m] == 0:
        return
  ans = min(ans, result)
  return

for c in combinations(virus, M):
  map_copy = [m[:] for m in map]
  solve(map_copy, c)

if ans == 999999:
  print('-1')
else:
  print(ans)