python 백준 17142 연구소3

https://www.acmicpc.net/problem/17142

코드

from itertools import combinations
from collections import deque
N,M = map(int,input().split())
arr = [list(map(int,input().split())) for _ in range(N)]
virus_total = []
total = 0
for r in range(N):
    for c in range(N):
        if arr[r][c] == 1:
            continue
        total += 1
        if arr[r][c] == 2:
            virus_total.append((r,c))
virus_comb = list(combinations(virus_total,M))
dr,dc = (1,-1,0,0,),(0,0,1,-1)
max_cnt = 2500
ans = max_cnt

for virus in virus_comb:
    que = deque(virus)
    check = [[False]*N for _ in range(N)]
    for r,c in virus:
        check[r][c] = True

    value,cnt = 0,len(virus_total)
    while que:
        # 1.맵 전체에 바이러스가 깔렸는지 확인
        if cnt == total:
            ans = min(ans,value)
            break
        for _ in range(len(que)):
            r,c = que.popleft()
            for d in range(4):
                nr,nc = r+dr[d], c+dc[d]
                if 0<=nr<N and 0<=nc<N and arr[nr][nc] !=1 and not check[nr][nc]:
                    que.append((nr,nc))
                    check[nr][nc] = True
                    if arr[nr][nc] != 2:
                        cnt += 1
        value += 1
if ans != max_cnt:
    print(ans)
else:
    print(-1)

로직

• 연구소 분석

  • 바이러스가 몇 개 깔려야 하는지 확인
  • 초기 바이러스 위치 체크

• combination을 이용하여 바이러스 M 개 선택하여 브루트포스 방식 채택

  • 어떤 바이러스를 선택해야 하는지 조건 설정하기(그리드 방식) 어렵기에

• bfs 방식으로 넓혀가면서 맵 전체에 바이러스가 깔렸을 때 몇초가 걸리는지 확인

  • 초 계산은 value를 이용하여 계산
  • 이중 반복문으로 만들어 for _ in range(len(que))가 끝날 때 마다 일초가 지나가는 방식

• 이렇게 구한 시간을 출력

  • 만약 연구소 전체에 바이러스가 깔릴 수가 없으면 ans가 갱신되는 일이 없어짐
  • ans가 갱신이 안됬을 경우 -1 출력
  • 이를 확인하기 위해 ans가 나올수가 없는 높은 값(max_cnt)을 초기값으로 설정

신경쓴 점

• 비활성 상태의 바이러스를 무조건 활성화 할 이유가 없음
  • 그렇기에 방문한 숫자를 계산하는 것이 아닌 맵에 있는 바이러스의 수를 계산
  • 주석1번 코드를 보면 cnt와 total을 비교하는데, cnt는 기존에 깔린 바이러스 수 + 방문하면서 생긴 바이러스 수