[백준] 14502번 : 연구소

 

 

 

 

 

 

 

접근법

- 전에 올렸던 "토마토"와 매우 유사한 문제라 개념을 확실히 쌓고자 풀어보았다.

 

- "토마토" 문제와 유사하게 전염이 되는 형식을 사용하였기에 dfs를 채택하였다. 그런데 특이점으로 "1"이라는 방벽 3개를 사용자가 임의로 설정해야한다는 점이 달랐다.

 

- 행과 열의 범위를 계산해보니 최대 8 * 8이어서 combination으로 1을 놓을 수 있는 조합을 모두 찾아낸 후 하나씩 적용해가면서 최댓값을 비교해야겠다는 생각을 했다.

 

- zero_count() 함수를 정의해서 행렬 내의 안전 구역(0인 곳)의 갯수를 반환하도록 하였고, shallow_copy() 함수를 정의하여 matrix를 visit에 복사하도록 했다. 이 때 [i, j]가 combi 즉, 사용자가 놓을 3개의 방벽 조합에 해당하는 인덱스면 1로 설정을 하고 그 외에는 matrix의 값을 복사하도록 했다.

 

- 이제 찾은 모든 조합의 list p를 for문으로 돌면서 deque(속도를 위해서 deque로 설정)를 만들고, 상하좌우의 값이 인덱스의 범위를 넘지 않고, 현재의 픽셀(visit[N][M] == 2)과 인접한 visit[n_row][n_col]의 값이 0이라면 visit[n_row][n_col]의 값을 2로 설정하고 해당 픽셀에서 전염을 시키기 위해 deque에 [n_row, n_col]을 넣는다.

 

- 모든 visit을 순회하고 난 뒤 zero_count() 함수를 사용하여 최댓값을 계속 업데이트를 하고 모든 for문이 종료되면 max_val을 출력한다.

 

 

 

 

 

 

풀이

from itertools import combinations
from collections import deque

row, col = map(int, input().split())

def zero_count(matrix) :
    count = 0
    for i in range(row) :
        for j in range(col) :
            if matrix[i][j] == 0 :
                count += 1
    return count

def shallow_copy(matrix, visit, combi) :
    for i in range(row) :
        for j in range(col) :
            if i * col + j in combi :
                visit[i][j] = 1
            else :
                visit[i][j] = matrix[i][j]


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

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

l = list()
visit = [[0 for _ in range(col)] for _ in range(row)]

for i in range(row) :
    for j in range(col) :
        if matrix[i][j] == 0 :
            l.append(i * col + j)

p = list(combinations(l, 3))
max_val = 0

for i in p :
    queue = deque()
    shallow_copy(matrix, visit, i)
    for i in range(row) :
        for j in range(col) :
            if visit[i][j] == 2 :
                queue.append([i, j])

    while queue :
        N, M = queue.popleft()
        for i in range(4) :
            n_row = N + dx[i]
            n_col = M + dy[i]
            if 0 <= n_row < row and 0 <= n_col < col :
                if visit[n_row][n_col] == 0 :
                    visit[n_row][n_col] = 2
                    queue.append([n_row, n_col])

    if zero_count(visit) > max_val :
        max_val = zero_count(visit)

print(max_val)

 

 

 

 

 

 

 

결과