G4 14502. 연구소

문제 보기 :  14502번: 연구소

---

문제

• 정답률 : 55%

---

작성 코드

# 벽 세울 수 있는 공간 조합
def combinations(n,new,c):
    answer = []
    if len(new) == n:
        return [new]
    for i in range(c,len(possible)):
        answer.extend(combinations(n,new+[possible[i]],i+1))
    return answer

from collections import deque
#바이러스 퍼지기
direction = [(-1,0),(0,-1),(0,1),(1,0)]
def spread(graph,start):
    dd = deque([start])
    while dd:
        x, y = dd.popleft()
        for dx, dy in direction:
            xx = x+dx ; yy = y+dy
            if 0<=xx<n and 0<=yy<m and graph[xx][yy]==0:
                graph[xx][yy] = 2
                dd.append((xx,yy))

n,m = map(int,input().split()) #리스트 n개, 각 원소 개수 m개
arr = [list(map(int,input().split())) for _ in range(n)]
possible = []
for i in range(n):
    for j in range(m):
        if arr[i][j] == 0:
            possible.append((i,j))

all_combi = combinations(3,[],0)
maxdanger = 0
for combi in all_combi:
    for i,j in combi:
        arr[i][j]=1 # 벽 세우기
    
    # 바이러스 전파
    for i in range(n):
        for j in range(m):
            if arr[i][j]==2:
                spread(arr,(i,j))
    
    danger = sum(list(1 for ls in arr for i in ls if i==0))
    maxdanger = max(maxdanger, danger)

    for p in possible:
        arr[p[0]][p[1]] = 0

print(maxdanger)

---

풀이

이 문제는 뭐랄까.. 모든게 짬뽕된 느낌...?
combinations, bfs를 합친 문제였다.
그래서 시간복잡도는 고려안해도 될 것 같다고는 생각했지만, 점점 길어지는 코드에 불안해졌다...

코드 해설을 해보자면, combinations 함수를 구현해서 0인 빈칸 공간 중 3개를 선택할 수 있는 모든 경우의 수를 all_combi로 두었다.
그리고 한 세트씩 돌아가면서 i,j 좌표에 벽을 세우고 바이러스가 모두 퍼지게 한 뒤, 0이 몇개가 남는지를 계산했다.

가장 해결이 난감했던 부분은 2이나 1로 변경된 기존의 arr를 원형태로 변경시키는 작업이었다.
처음에는 반복문 안에 new_arr=arr를 두어 해결하려했지만, 재귀? 때문에 원형태로 돌아오지 않는 문제가 발생했고..
써도 되나 싶었던 방법을 사용해서 해결했다. 그 방법은 possible 내 모든 좌표를 0으로 변경시키는 것이었다.

이렇게 풀이하니 모든 테스트 케이스를 패스했다.