[boj 14502] [Python] 연구소

문제 링크

PyPy3과 Python3의 신기한 차이

이전에 한 번 풀었을 때 정말 어려웠는데 이번엔 방향을 금방 잡고 풀었다.

과정

1. 입력 받음
2. 벽을 세울 수 있는 빈칸을 찾음
3. 빈칸 중에서 combinations 이용해서 3개 뽑음 - 경우의 수 많다
   1. 각각 경우의 수에 대해 벽 세움 (새 list)
   2. 바이러스 위치 찾아서 바이러스 위치에 대해 bfs 수행
      1. bfs에서는 바이러스 위치를 기준으로, 상하좌우 벽을 만날 때 까지 모두 2(바이러스)로 채움.
   3. 안전 영역 크기 셈.
4. 안전 영역 크기 중 최댓값 리턴.

코드

# 14502 연구소
# bfs/dfs

from itertools import combinations
from collections import deque
from sys import stdin 

input = 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()))


# spread_virus
def spread_virus(graph, i, j):
    q = deque()
    q.append((i, j))

    n = len(graph)
    m = len(graph[0])

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

    while q:
        x, y = q.popleft()
        for d in range(4):
            xx = dx[d] + x
            yy = dy[d] + y
            if 0 <= xx and xx < n and 0 <= yy and yy < m:
                if graph[xx][yy] == 0:
                    graph[xx][yy] = 2
                    q.append((xx, yy))


# 벽을 세울 수 있는 빈칸만 구함 
blanks = []
for i in range(n):
    for j in range(m):
        if graph[i][j] == 0:
            blanks.append((i, j))

# 빈칸 3개 뽑아서 벽 세움
new_graph = [[0 for _ in range(m)] for _ in range(n)]
counts = [-1]
# 각 case에 대해 벽 세우고 바이러스 퍼트리기
for com in combinations(blanks, 3):
    for i in range(n):
        for j in range(m):
            new_graph[i][j] = graph[i][j]
    for wall in com:
        new_graph[wall[0]][wall[1]] = 1
    # 바이러스 퍼트리기 - bfs
    # 바이러스를 우선 카운트
    viruses = []
    for i in range(n):
        for j in range(m):
            if new_graph[i][j] == 2:
                viruses.append((i, j))
    for virus in viruses:
        spread_virus(new_graph, virus[0], virus[1])

    # 안전 영역 크기 구하기
    count = 0
    for i in range(n):
        for j in range(m):
            if new_graph[i][j] == 0:
                count += 1
    counts.append(count)

print(max(counts))

추가

그래프 최대 크기가 8개니까, 벽을 세울 수 있는 경우의 수의 최대는 64C3 = 41664

이정도만 해도 느린데 그래프 크기가 크면 이런 무식한 방법으로 풀지 못할 것 같다...

기억할 것

• from itertools import combinations