연구소
접근 방법 [필수 작성]
제한 조건 확인
상하좌우
벽을 3개를 세울 수 있음
바이러스가 다 퍼진 후 안전영역 크기 최댓값을 구해야함
최대 8x8 매트릭스
바이러스는 최대 10까지 있을 수 있음
빈칸은 최소 3개
아이디어
굉장히 복잡한 케이스가 많고 제한 조건이 작기 때문에 완전탐색으로 해야할 것 같다
우선 모든 경우에 대해서 벽을 세운 후
각 모든 경우에 대해서 바이러스가 bfs 형식으로 퍼져나간 후 다 끝나면
0의 갯수를 세서 0의 갯수의 최댓값을 리턴하는 형식
시간복잡도
0이 있을 수 있는 위치는 최대(바이러스가2개일때)
→ 88-2 = 62 → 62C3 → 62 61 60 / 3 2 = 62 61 10 → ( 3600 + 180 + 2 ) 10 → 37,820 (보수적으로 접근했을때, 벽을 놓을 수 있는 최대 조합의 갯수)
바이러스 최대 10개 bfs 하는 횟수
생각1 → 88(전체매트릭스노드갯수)10(바이러스노드갯수)4(바이러스전파방향)8*8(바이러스가 최대 전파되는 횟수) → 163840 → 너무 큰데? 과연 이렇게 클까?
생각2 → 88(전체매트릭스노드갯수)10(바이러스노드갯수)4(바이러스전파방향)36(?지그재그가 최대?maybe?) → 92,160
호수에 돌을 던졌을때 물이 퍼져나가는 모양처럼 바이러스도 퍼지기 때문에, 최대전파횟수가 64인 경우는 없을것으로 예상해서 지그재그가 가능한 최대전파횟수라고 생각함
전체 탐색 해서 0갯수 반환 하는 연산수 → 64
더 생각해보니 이런 케이스도 있을 수 있음
어찌되었던,
각조합케이스갯수 ( 각 조합에 대한 바이러스 최대전파수 + 바이러스 전파완료된 매트릭스에 대해 0갯수카운팅 ) = 37,820 (92,160 + 64) = 3,487,911,680 → 34억 → 시간초과
→ 시간복잡도 초과 될 것 같기도한데, 중복된 바이러스 방문 횟수가 많아서 x4 되는 상당부분 지워질 것으로 예상 시간 초과 날수도 있긴 한데 다른 방법이 생각이 안나서 일단 구현
자료구조
코드 구현 [필수 작성]
1차 시도 (소요시간 1시간30분)
visited 와 matrix 가 모두 2중 리스트이기 때문에
virus 전파시, 각 case 별로 deepcopy 본을 만들어야했는데, 처음에는 그냥 얕은복사를 사용해서 참조로 인해 모든 구간에 다 적용되는 오류 때문에 한참을 헤맸다.
시간복잡도 관점에서는 다행히 중복 방문되는 바이러스 노드가 많아 시간절약이 되는것 같다.
from collections import deque
from itertools import combinations
import copy
N, M = map(int,input().split()) #N은 row, M 은 col
matrix = []
for _ in range(N):
matrix.append(list(map(int,input().split())))
visited = [[False]*M for _ in range(N)]
dr = [0,1,0,-1]
dc = [1,0,-1,0]
safe_area_count = 0
def virused_matrix(matrix):
global N,M,dr,dc
tmp_matrix = copy.deepcopy(matrix)
tmp_visited = copy.deepcopy(visited)
for r in range(N):
for c in range(M):
if tmp_matrix[r][c] == 2 and tmp_visited[r][c] == False :#추후에 문제 생길수도 있는 부분
q = deque([(r,c)])
tmp_visited[r][c] = True
while q:
tr, tc = q.popleft()
for i in range(4):
nr = tr + dr[i]
nc = tc + dc[i]
if 0 <= nr < N and 0 <= nc < M and tmp_visited[nr][nc] == False:
if tmp_matrix[nr][nc] == 0:
tmp_matrix[nr][nc] = 2
tmp_visited[nr][nc] = True
q.append((nr,nc))
elif tmp_matrix[nr][nc] == 2:
tmp_visited[nr][nc] = True
q.append((nr,nc))
return tmp_matrix
def count_safe_area(tmp_matrix):
global N,M
count = 0
for r in range(N):
for c in range(M):
if tmp_matrix[r][c] == 0:
count += 1
return count
def index_of_safe_area(tmp_matrix):
global N,M
list = []
for r in range(N):
for c in range(M):
if tmp_matrix[r][c] == 0:
list.append((r,c))
return list
for candidate_wall_index in combinations(index_of_safe_area(matrix),3):
tmp_matrix = copy.deepcopy(matrix)
first,second,third = candidate_wall_index
tmp_matrix[first[0]][first[1]] = 1
tmp_matrix[second[0]][second[1]] = 1
tmp_matrix[third[0]][third[1]] = 1
safe_area_count = max(safe_area_count,count_safe_area(virused_matrix(tmp_matrix)))
print(safe_area_count)
배우게 된 점 [ 필수 X ]
자유 형식
질문 [ 필수 X ]
Q1
제 로직의 시간복잡도를 계산하는게 어렵습니다.
제 로직의 아이디어는
벽을 놓을 수 있는 모든 조합의 case 에 대해서
실제로 벽을 놓고, 바이러스 전파를 진행시킨 후,
바이러스 전파 완료된 matrix 에서 0인 칸을 카운트하는 식으로 해서, 모든 벽조합case에 대해서 count 값이 가장 높은 값을 리턴하는 방식입니다.
이때, 시간복잡도 파트를 보시고, 제가 생각한 시간복잡도 계산 flow 가 충분히 논리적인지 궁금합니다. 사실상 시간초과가 될 것이라고 생각하고 구현했는데 그냥 시간내에 풀려버렸습니다.
그리고 실제 시간복잡도는 어떻게 계산하면 좋을지 여쭤보고 싶습니다.
→ 해설영상을 보고 왔는데, 해설 영상에서는 벽세우는조합수x최대전파횟수 로 계산하고 끝내버리더라구요. 물론 최대의 경우는 모든 노드가 바이러스가 전파되서 바이러스 노드 10개를 전파(탐색)하던 2개를 전파하던, 방향이 4개던 말던, 더 진행이 안되고(큐에 더 추가를 안하고) 끝나기때문에 해설영상도 맞는 말이라고 생각되지만, 뭔가 남에게 충분히 논리적으로 설명한다고 했을때 통쾌하게 설명이 되는것 같지는 않습니다… 그냥 해설영상을 제가 이해한대로 납득하고 넘어가는게 맞을까요?
피드백 [ 코치 작성 ]
우선 동연님의 코드의 알고리즘은 벽을 세운 후 “각각의” 바이러스에 대해 bfs를 수행하되 bfs 수행 중 방문한 바이러스는 bfs를 수행하지 않는 방식으로 구현되어 있습니다. 바이러스 들이 벽으로 분리된 경우를 고려하여 위와 같이 작성하신 것으로 보이지만 이는 큐에 초기값으로 모든 바이러스의 위치를 넣어주면 해결됩니다.
위와 같이 로직을 작성하셔서 시간 복잡도 계산 상 바이러스 수 바이러스 전파 방향…과 같이 계산하신 것으로 보이나 앞서 설명드렸듯 바이러스에 대해 bfs를 하는 경우는 바이러스가 분리된 경우이며 이와 같은 경우 한개의 바이러스에 대한 bfs에서 64(88)칸의 행렬을 전부 순회하지 않습니다. 그렇기에 모든 바이러스의 bfs의 합으로 계산하는 것이 적합합니다.
이를 고려할 경우 강사님의 계산과 같이 모든 노드의 개수를 기반으로 계산하게 되며 정확한 풀이는 바이러스 조합 수 bfs시간복잡도(O(n+e), 강사님의 강의에는 e가 빠져있습니다.) 0의 개수를 세는 시간(64)가 됩니다.
