백준 14502

문제출처: https://www.acmicpc.net/problem/14502

[처음 맞췄을 때 코드]

import sys 
from collections import deque

dx = [0,0,-1,1]
dy = [-1,1,0,0]
def bfs(a): 
    d = [[0] * m for _ in range(n)]
    q = deque()

    # a 모방
    for i in range(n):
        for j in range(m):
            d[i][j] = a[i][j]
            if d[i][j] == 2:
                q.append((i, j))
        
    while q:
        x, y = q.popleft()
        for k in range(4):
            nx, ny = x + dx[k], y + dy[k]
            if 0 <= nx < n and 0 <= ny < m:
                if d[nx][ny] == 0:
                    d[nx][ny] = 2
                    q.append((nx, ny))

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


n, m = map(int, sys.stdin.readline().split())
a = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
ans = 0

for x1 in range(n):
    for y1 in range(m):
        if a[x1][y1] != 0:
            continue
        for x2 in range(n):
            for y2 in range(m):
                if a[x2][y2] != 0:
                    continue
                for x3 in range(n):
                    for y3 in range(m):
                        if a[x3][y3] != 0:
                            continue
                        if x1 == x2 and y1 == y2:
                            continue
                        if x2 == x3 and y2 == y3:
                            continue
                        if x1 == x3 and y1 == y3:
                            continue
                        
                        # 벽 세우기
                        a[x1][y1] = 1
                        a[x2][y2] = 1
                        a[x3][y3] = 1
                        
                        cur = bfs(a)
                        if ans < cur:
                            ans = cur
                        
                        # 벽 원래대로
                        a[x1][y1] = 0
                        a[x2][y2] = 0
                        a[x3][y3] = 0
print(ans)  

-> 실행시간: 1464ms

combination 사용하면 실행시간을 더 줄일 수 있을 것 같아서 시도해봄!

[수정 후]

import sys 
from itertools import combinations
from collections import deque

n, m = map(int, sys.stdin.readline().split())
check = []
empty = []
dx = [0,0,-1,1]
dy = [-1,1,0,0]
ans = 0

for i in range(n):
    tmp = list(map(int, sys.stdin.readline().split()))
    check.append(tmp)
    
    # 0이 들어간 자리 인덱스 뽑아내기(조합구하기 위해) 
    for j in range(m):
        if tmp[j] == 0:
            empty.append(i*m + j)

#combination사용
combi = list(combinations(empty, 3))

for a, b, c in combi:
    dq = deque()
    # 벽 세우기
    check[a//m][a%m] = 1
    check[b//m][b%m] = 1
    check[c//m][c%m] = 1
    
    d = [[0] * m for _ in range(n)]

    # check 모방
    for i in range(n):
        for j in range(m):
            d[i][j] = check[i][j]
            if d[i][j] == 2 :
                dq.append(i*m + j)
        
    while dq:
        idx = dq.popleft()
        x, y = idx // m, idx % m 
        for k in range(4):
            nx, ny = x + dx[k], y + dy[k]
            if 0 <= nx < n and 0 <= ny < m:
                if d[nx][ny] == 0:
                    d[nx][ny] = 2
                    dq.append(nx*m + ny)

    # d를 다 채운 후
    cnt = 0
    for i in range(n):
        for j in range(m):
            if d[i][j] == 0: 
                cnt += 1
    if cnt > ans :
        ans = cnt
        
    check[a//m][a%m] = 0
    check[b//m][b%m] = 0
    check[c//m][c%m] = 0
print(ans) 

-> 실행시간: 424ms