[알고리즘 문제 풀이][파이썬] 백준 17142번: 연구소 3

백준 17142 문제 링크: https://www.acmicpc.net/problem/17142

📑 문제 설명
1. NxN 정사각형 연구소가 주어짐
2. 연구소는 0: 빈방, 1: 벽, 2: 바이러스를 놓을 수 있는 곳으로 이루어져 있음
3. 바이러스 개수 M이 주어짐
4. 연구소 중 2번 위치 개수 중 M개의 위치에만 바이러스를 놓을 수 있음
5. 바이러스를 M개만큼 놓았을 때 연구소 전체에 바이러스가 퍼지는 가장 최단 시간 구하기

입력: 첫째 줄에 연구소 크기 N과 바이러스를 놓을 수 있는 개수 M이 주어짐. 둘째줄부터 NxN으로 구성된 연구소가 주어짐.

출력: 연구소에서 바이러스가 퍼져나가는 최소 시간 출력

• 단, 모든 빈칸에 바이러스를 퍼뜨릴 수 없는 경우 -1 출력

💡 문제 해결 방법
알고리즘: bfs

알고리즘 선택 이유

• 바이러스 시작점으로부터 넓게 퍼져나가야 함 --> 깊게 퍼져나가는 것은 의미 없음

예외처리

• M을 놓을 위치의 조합
• 2번 위치에서 BFS는 무조건 다 실행되어야 함(그래야 어떤 위치에서 최솟값이 나오는지 확인할 수 있음)
• 내가 생각하는 알고리즘

1. 모든 2번 위치에서 BFS를 수행하며 각 위치마다 소요되는 시간을 depth라는 배열에 기록한다.
2. 모든 2번의 위치 중에서 M개씩 조합하여 모든 위치에 대해 시간을 비교하여 최소시간으로 수정한다.
3. 조합을 1회 완료했을 시에 depth 배열에서 가장 긴 시간을 출력한다.
4. 조합을 반복하면서 3번에서 출력한 시간과 비교하며 min 값을 찾고 출력한다.
   내가 여기서 모르겠는 것 조합을 어떻게 해야 하는지

스터디 내용

• 2번 위치를 저장(combination) + BFS
• combination 문제는 DP로 풀어야 함
  - r: [2번의 위치 저장 리스트] --> list
  • c: [] 골라진 버택스
    • r에 대한 인덱스와 c에 대한 인덱스 별개로 저장
  • comb(): 1월 13일 촬영 이미지 참고(칠판)
• 2는 0과 같이 처리하는 것은 맞으나 최대값을 갱신할 때는 포함되어서는 안됨

💻 코드

import sys
from collections import deque

n, m = map(int, sys.stdin.readline().split())
graph = []
room = 0
for x in range(n):
    graph.append(list(map(int, sys.stdin.readline().split())))
point2 = []
for x in range(n):
    for y in range(n):
        if graph[x][y] == 2:
            point2.append([x, y])
        elif graph[x][y] == 0:
            room += 1

combinationresults = []
def combination(comb, idxc, idxr):
    if len(comb) == m and idxc == m:
        combinationresults.append(comb[:])
        return
    for i in range(idxr, len(point2)):
        comb[idxc] = point2[i]
        combination(comb, idxc+1, i+1)

def bfs(queue, room):
    max_t = -1
    infectplace = 0
    while(queue):
        x, y = queue.popleft()
        adjlist = [[x-1, y], [x+1, y], [x, y-1], [x, y+1]]
        for point in adjlist:
            nx = point[0]
            ny = point[1]
            if nx >= 0 and nx < n and ny >= 0 and ny < n:
                if graph[nx][ny] == 0:
                    if visit[nx][ny] == -1:
                        visit[nx][ny] = visit[x][y] + 1
                        queue.append((nx, ny))
                        infectplace+=1
                        max_t = max(visit[nx][ny], max_t)
                if graph[nx][ny] == 2:
                    if visit[nx][ny] == -1:
                        visit[nx][ny] = visit[x][y] + 1
                        queue.append((nx, ny))

    if room == infectplace:
        if room == 0:
            return 0
        else:
            return max_t
    else:
        return 1e10



comb = [0] * m
combination(comb, 0, 0)
result = 1e10
for c in combinationresults:
    visit = [[-1 for x in range(n)] for x in range(n)]
    queue = deque()
    for point in c:
        queue.append((point[0], point[1]))
        visit[point[0]][point[1]] = 0
    result = min(result, bfs(queue, room))
print(result if result != 1e10 else -1)

💟 추가적으로 알게 된 점
1. 드디어 해결한 연구소 3...
2. 제일 처리하기 어려웠던 부분은 2를 처리하는 부분
- 2는 빈 공간처럼 처리하면 됨
- 단, 한 조합 내에서는 최대 시간을 선택하고, 여러 조합에서는 최소 시간을 선택해야 함
- 따라서 한 조합 내에서 최대 시간을 선택할 때 2의 위치에 있는 시간의 영향을 받아선 안됨
- 그러므로 시간을 선택하는 조건문은 0을 방문할 때에만 추가해주고 2는 그냥 방문처리만 해줌
3. 나 같은 경우는 빈 공간의 개수를 그래프를 입력 받으면서 체크하고 만약 빈 공간 개수만큼 방문을 완료했다면 --> 최대 시간을 리턴하고 / 빈 공간 개수와 방문 개수가 0개로 일치한다면 빈 공간이 존재하지 않는다는 의미이므로 --> 0을 리턴하도록 설정
4. 이게 min, max를 동시에 쓰는 문제는 예외에 대한 값을 정할 때 아주 작아야 할 지, 커야 할 지 잘 고민해 보고 써야 함