Search

연구소

문제 : 연구소

풀이

해결에 필요한 핵심 아이디어: BFS(너비 우선 탐색), 조합

해결 시나리오

인접 행렬로 표현한 그래프에서
벽을 세울 수 있는 좌표(값이 0)를 튜플 형태로 wall 리스트에 따로 저장
wall 리스트에서 세 지점을 뽑는 모든 조합을 구하고 각각의 경우마다 다음을 반복
graph의 카피본을 뜨고 뽑은 세 지점에 벽 세우기
초기 바이러스 위치를 큐에 넣고 BFS 수행
graph_copy에서 값이 0인 갯수 계산 → 해당 케이스의 안전구역 크기
구한 안전구역 크기를 결과 리스트 result에 저장
최종적으로 result에 저장된 요소 중 가장 큰 값을 출력

시간 복잡도

인접행렬로 구현한 그래프의 BFS 탐색 시간 복잡도 O(N²)
최대 시간 복잡도는 O((NM)²) (최대 NM개의 지점에서 BFS 수행)
파이썬의 deque으로 큐를 대체한다면 케이스 하나당 시간복잡도는 O(NM) (NM은 최대 64)
총 케이스의 수는 최대 ₆₄C₃ = 41,664
따라서 총 연산횟수는 최대 64 × 41,664 으로 시간 제한(2초)를 무난히 통과
풀이

나동빈님 컨텐츠를 이용하시면 더 많고 자세한 내용을 얻을 수 있습니다.