[문제 풀이] 백준 14502

해결 과정

3개 세우고 최대 개수를 찾으라길래 완전탐색 말고 다른 방법이 있나 생각해봤더니 없었음. 

결국 완전탐색 및 그래프 + BFS 문제였다. 1시간 이내로 걸림.

 

다만, 2차원 배열의 복사를 알아야 했다.

 

나의 풀이

from collections import deque
from copy import deepcopy
from itertools import combinations

def bfs(laboratory, tuple, virus): # ((0, 1), (2, 1), (2, 3))

    for i in range(3):
        laboratory[tuple[i][0]][tuple[i][1]] = 1

    queue = deque(virus) # [(0, 1), (2, 1), (2, 3)]

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

    newVirusCount = 0

    while queue:
        cur = queue.pop()
        for i in range(4):
            x = cur[0] + dx[i]
            y = cur[1] + dy[i]
            if x >= 0 and y >= 0 and x < N and y < M and laboratory[x][y] == 0:
                laboratory[x][y] = 2
                queue.append((x, y))
                newVirusCount += 1

    return newVirusCount

def solution():
    n, m = map(int, input().split())
    global N, M
    N = n
    M = m

    laboratory = [list(map(int, input().split())) for _ in range(N)]

    blank = []
    blankCount = 0
    virus = []
    for i in range(N):
        for j in range(M):
            if laboratory[i][j] == 0:
                blank.append((i, j))
                blankCount += 1
            elif laboratory[i][j] == 2:
                virus.append((i, j))

    candidates = []
    for c in list(combinations(blank, 3)):
        candidates.append(blankCount -  bfs(deepcopy(laboratory), c, virus) - 3)
        
    return max(candidates)

print(solution())

 

다른 풀이

 

 

IDEA

 

2차원 리스트의 copy

from copy import deepcopy
# 2차원 리스트
laboratory = [list(map(int, input().split())) for _ in range(N)]

copyLab = deepcopy(laboratory)

그런데, deepcopy의 시간 복잡도가 느리다는 글을 보고, 백준 다른 사람들 풀이도 보고 다음과 같이 바꿨더니 현저하게 시간이 줄었다.

from copy import deepcopy
# 2차원 리스트
laboratory = [list(map(int, input().split())) for _ in range(N)]

copyLab = [row[:] for row in laboratory]