[BFS] 백준 17141 : 연구소2 - 파이썬 Python

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

17141번: 연구소 2

 

생각하기

연구소 전체를 점령할 수 있는 최소시간을 구하는 문제이므로

BFS를 통해 점령하다가 

점령이 완료되면 그 때의 time을 min_time과 비교하면 되는 문제로 생각했다

 

바이러스를 놓을 수 있는 후보 여러 개중에서 M개를 선택하여 바이러스를 놓는다 -> 조합을 사용

 

처음에 모든 빈칸 + 바이러스 놓을 수 있는 후보지를 counting한 후 

BFS 큐를 돌면서 counting을 차감해주는 방식으로 점령 여부를 확인

 

 

시간복잡도

M<=10이므로 일부 빈칸 ( <= 10) 인 것 중에서 M개를 고르고 -> 최대 2^10

바이러스가 상하좌우로 N<=50인 칸을 가중치 1로 움직이고 -> 최대 O(N^2)

=> 2^10 * N^2 => 1024 * 2500 = 2500000 

 

# 연구소의 특정 위치에 바이러스 M개
# N X M  - 0 : 빈칸 / 1 : 벽 / 2 : 바이러스를 놓을 수 있는 칸
# 바이러스는 상하좌우 복제 -> 1초 

# 모든 빈칸에 바이러스를 퍼뜨리는 최소 시간


from itertools import combinations
from collections import deque

# 시간 복잡도
# N = 50 개수 M = 10 2500 * 10 = 25000

N, M = map(int, input().split())

lab_origin = []
virus = []
blank_cnt_static = 0
for i in range(N):
    lab_origin.append(list(map(int, input().split())))
    for j in range(N):
        if lab_origin[i][j] == 2:
            virus.append((i, j))
            blank_cnt_static += 1
        elif lab_origin[i][j] == 0:
            blank_cnt_static += 1


# blank_cnt_static -= M # 빼주지 않는다 추후 큐에서 popleft할 때 빼줄것이다

virus_comb =list(combinations(virus, M))


# 포인트는 바이러스가 여러개라는 것 - 동시에 퍼져나가는 것이기 때문에
# 각 comb마다의 최소 시간을 구하고 
# 각 comb에서 최소시간을 초과시 바로 종료

dy = [0, 1, 0, -1]
dx = [1, 0, -1, 0]


min_time = int(1e9)
for vc in virus_comb:
    visited = [[0]*N for _ in range(N)]
    q = deque()
    for v in vc:
        q.append((v[0], v[1], 0))
        visited[v[0]][v[1]] = -1

    blank_cnt = blank_cnt_static
    
    while q:
        row, col, time = q.popleft()
        blank_cnt-= 1

        if blank_cnt == 0:
            if min_time > time:
                min_time = time
            break
        
        else:
            # if min_time < time:
            #     break

            for d in range(4):
                ny = row + dy[d]
                nx = col + dx[d]

                if 0<=ny<N and 0<=nx<N and visited[ny][nx] == 0:
                    if (lab_origin[ny][nx] == 0 or lab_origin[ny][nx] == 2):
                        q.append((ny, nx, time+1))
                        visited[ny][nx] = time+1
                        # blank_cnt -= 1 # 여기서 마지막 빈칸을 없애는 0 처리를 해주게 되면 큐에 들어있는 값이 다음에 걸린다 

    
if min_time == int(1e9):
    print(-1)
else:
    print(min_time)

헤맷던 포인트

빈칸을 카운팅 하던 blank_cnt가 0이되면 바로 min_time을 설정해주고 break하는 방식을 사용했었는데

이게 큐의 작동 방식을 생각하면 큐에 마지막 빈칸을 넣을 때, blank_cnt를 1차감하면 안된다!!!

stack이 아니기 때문에 마지막 칸의 time이 나오는 것이 아니라 큐에있는 다음 요소의 time이 나오게 된다

 

 

다른 방법으로 풀이

각 조합을 돌면서 blank_cnt를 차감하는 방식이 아닌

전염을 시키며 visited에 time을 저장하고 

다시 한번 visited를 돌아서 가장 큰 time을 찾아서 result와 비교하는 방식

# 연구소의 특정 위치에 바이러스 M개
# N X M  - 0 : 빈칸 / 1 : 벽 / 2 : 바이러스를 놓을 수 있는 칸
# 바이러스는 상하좌우 복제 -> 1초 

# 모든 빈칸에 바이러스를 퍼뜨리는 최소 시간


from itertools import combinations
from collections import deque

# 시간 복잡도
# N = 50 개수 M = 10 2500 * 10 = 25000

N, M = map(int, input().split())

lab_origin = []
virus = []
blank_cnt_static = 0
for i in range(N):
    lab_origin.append(list(map(int, input().split())))
    for j in range(N):
        if lab_origin[i][j] == 2:
            virus.append((i, j))


virus_comb =list(combinations(virus, M))


# 포인트는 바이러스가 여러개라는 것 - 동시에 퍼져나가는 것이기 때문에
# 각 comb마다의 최대 시간을 구하고 
# 다른 comb 와의 최대 시간을 비교

dy = [0, 1, 0, -1]
dx = [1, 0, -1, 0]


result = int(1e9)
for vc in virus_comb:
    visited = [[0]*N for _ in range(N)]
    q = deque()
    for v in vc:
        q.append((v[0], v[1], 0))
        visited[v[0]][v[1]] = -1

    
    while q:
        row, col, time = q.popleft()
    
        for d in range(4):
            ny = row + dy[d]
            nx = col + dx[d]

            if 0<=ny<N and 0<=nx<N and visited[ny][nx] == 0:
                if (lab_origin[ny][nx] == 0 or lab_origin[ny][nx] == 2):
                    q.append((ny, nx, time+1))
                    visited[ny][nx] = time+1

    comb_max_time = -1
    for i in range(N):
        for j in range(N):
            if visited[i][j] == 0 and lab_origin[i][j] != 1:
                comb_max_time = int(1e9)
                break
            if comb_max_time < visited[i][j]:
                comb_max_time = visited[i][j]
    
    if comb_max_time != int(1e9) :
        if result > comb_max_time :
            result = comb_max_time
    
if result == int(1e9):
    print(-1)
else:
    print(result)