BOJ 14502 연구소

https://www.acmicpc.net/problem/14502
시간 2초, 메모리 512MB
input :

• N M (3 ≤ N, M ≤ 8)
• N개의 줄에 지도의 모양(0 - 빈 칸, 1 - 벽, 2 - 바이러스 위치)

output :

• 안전 영역의 최대 크기를 출력

처음에 itertools 가지고 풀다가 8 * 8 모양이 안 나오길래 아 시간 초과다 생각하고 어떻게 줄일 방법들을 찾다가. 도저히 못 찾겠어서 책이랑 여러 사람들 답을 검색해 보았다.

다들 for문으로 벽을 지정하는 방법을 쓰길래 아 저게 좀 빠른가보다 하고 문제를 풀었는데 왠걸 7 * 7 도 제대로 못 뱉더라... 일단 짜증나서 둘 다 만들긴 했는데
수가 큰 경우엔 itertools 해서 풀면 시간 초과 당연히 날 꺼고 작은 경우엔 이게 더 빠른 거 같다.
for 문으로 하는 거도 기억해 두자.

import sys
from itertools import combinations
from _collections import deque

n, m = map(int, sys.stdin.readline().split())
data = []
temp = [[0] * m for _ in range(n)]
virus = []
empty = []
for i in range(n):
    a = list(map(int, sys.stdin.readline().split()))
    for j in range(m):
        if a[j] == 2:
            virus.append((i, j))
        if a[j] == 0:
            empty.append((i, j))
    data.append(a)

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

ret = 0

def viruses():
    q = deque()
    for item in virus:
        q.append(item)

    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx >= n or nx < 0 or ny >= m or ny < 0:
                continue
            if temp[nx][ny] == 0:
                temp[nx][ny] = 2
                q.append((nx, ny))

def zeros():
    cnt = 0
    for i in range(n):
        for j in range(m):
            if temp[i][j] == 0:
                cnt += 1
    return cnt


for positions in combinations(empty, 3):
    for i in range(n):
        for j in range(m):
            temp[i][j] = data[i][j]

    for now_x, now_y in positions:
        temp[now_x][now_y] = 1

    viruses()
    ret = max(ret, zeros())

print(ret)

-----------------------------------------------------------

import sys

n, m = map(int, sys.stdin.readline().split())
data = []
temp = [[0] * m for _ in range(n)]

for _ in range(n):
    data.append(list(map(int, sys.stdin.readline().split())))

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

ret = 0

def virus(x, y):
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx >= n or nx < 0 or ny >= m or ny < 0:
            continue
        if temp[nx][ny] == 0:
            temp[nx][ny] = 2
            virus(nx, ny)

def zeros():
    cnt = 0
    for i in range(n):
        for j in range(m):
            if temp[i][j] == 0:
                cnt += 1
    return cnt

def wall(count):
    global ret
    if count == 3:
        for i in range(n):
            for j in range(m):
                temp[i][j] = data[i][j]
        for i in range(n):
            for j in range(m):
                if temp[i][j] == 2:
                    virus(i, j)
        ret = max(ret, zeros())
        return
    for i in range(n):
        for j in range(m):
            if data[i][j] == 0:
                data[i][j] = 1
                count += 1
                wall(count)
                data[i][j] = 0
                count -= 1

wall(0)
print(ret)

위의 경우가 combination을 이용한 것이고,
아래가 for문으로 고른 것이다.