[백준/Python] 14502번 - 연구소

문제

백준 14502번 - 연구소

풀이1 해결 과정

1. 벽을 세운다. (모든 곳에 벽을 세워본다)

• 0이면 1로 바꿔서 벽을 세운다.
• 3개의 벽을 다 세우면 bfs를 실행

2. 2인 곳을 찾아서 큐에 넣는다.

• bfs를 돌면서 0인 곳은 2로 바꾼다.

4. 0의 개수를 센다.
5. 모든 경우의 수를 다 해본 후 가장 최대값을 찾는다.

풀이2 해결 과정

1. 그래프에서 값이 2인 곳을 바이러스 존에 넣고, 0인 곳은 세이프 존에 넣는다.
2. 조합을 이용해서 세이프 존에서 3개를 뽑는다.

• 뽑은 3개를 1로 바꿔서 벽으로 바꾼다.
• 3개의 벽을 세운 그래프(tmp_graph)를 만들고 bfs를 돈다.

4. 바이러스 존을 큐에 넣고 하나씩 빼면서 상하좌우를 확인한다.

• 0이라면 2로 바꿔서 바이러스를 퍼트린다.
• 0의 갯수를 세고 최대값을 갱신한다.

5. 해당 경우의 수를 다 구했으면 아까 세운 3개의 벽을 0으로 바꾸고
   다시 다른 벽을 세워서 해당 과정을 반복한다.

풀이 1 (Python3 실패, PyPy3 성공)

import sys
from collections import deque
import copy

n,m = map(int,sys.stdin.readline().split())

graph = []
for i in range(n):
  graph.append(list(map(int,sys.stdin.readline().split())))


dx = [-1,1,0,0]
dy = [0,0,-1,1]
q = deque()
ans = 0

def bfs():
  global ans
  tmp = copy.deepcopy(graph)
  # 2인 곳에서 바이러스 퍼지기 시작
  for i in range(n):
    for j in range(m):
      if tmp[i][j] == 2:
        q.append([i,j])
  # 상하좌우가 0이라면 2로 바꾸기 = 바이러스 퍼지는 중
  while q:
    x,y = q.popleft()
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if 0 <= nx < n and 0 <= ny < m:
        if tmp[nx][ny] == 0:
          tmp[nx][ny] = 2
          q.append([nx,ny])
  # 0의 개수 세기
  cnt = 0
  for i in tmp:
    cnt += i.count(0)
  ans = max(cnt,ans)

# 백트래킹을 이용해서 벽을 세우는 경우의 수 구하기
def make_wall(x):
  if x == 3:
    bfs()
    return 
  for i in range(n):
    for j in range(m):
      if graph[i][j] == 0:
        graph[i][j] = 1
        make_wall(x+1)
        graph[i][j] = 0

make_wall(0)
print(ans)

풀이 2 (Python3 성공, PyPy3 성공)

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

n,m = map(int,sys.stdin.readline().split())

graph = []
virus_zone = []
safe_zone = []
for i in range(n):
  graph.append(list(map(int,sys.stdin.readline().split())))


dx = [-1,1,0,0]
dy = [0,0,-1,1]

ans = 0

# 벽을 3개 세울 때 중복되는 조합 없게 하기 위해 combination 사용
# ex) (1,1) (2,4) (3,5) 세우고 검사한 뒤 나중에 (2,4) (1,1) (3,5)를 방지하기 위해
for i in range(n):
  for j in range(m):
    if graph[i][j] == 2:
      virus_zone.append([i,j])
    if graph[i][j] == 0:
      safe_zone.append([i,j])


def bfs(tmp_graph):
  global ans
  q = deque(virus_zone)

  # 상하좌우가 0이라면 2로 바꾸기 = 바이러스 퍼지는 중
  while q:
    x,y = q.popleft()
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]
      if 0 <= nx < n and 0 <= ny < m:
        if tmp_graph[nx][ny] == 0:
          tmp_graph[nx][ny] = 2
          q.append([nx,ny])
  # 0의 개수 세기
  cnt = 0
  for i in tmp_graph:
    cnt += i.count(0)
  ans = max(cnt,ans)

# 조합을 이용해서 경우의 수 구하기
def make_wall():
  safe_zones_combi = combinations(safe_zone, 3)
  
  for walls in safe_zones_combi:
      a, b, c = walls[0], walls[1], walls[2]

      graph[a[0]][a[1]] = 1
      graph[b[0]][b[1]] = 1
      graph[c[0]][c[1]] = 1

      tmp_graph = [item[:] for item in graph]

      bfs(tmp_graph)

      graph[a[0]][a[1]] = 0
      graph[b[0]][b[1]] = 0
      graph[c[0]][c[1]] = 0

make_wall()
print(ans)