문제 : 연구소
풀이
해결에 필요한 핵심 아이디어: 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초)를 무난히 통과
풀이
