[파이썬] 백준 17141 : 연구소2 (골드4)

[파이썬] 백준 17141 : 연구소2 (골드4)

 

17141번: 연구소 2

 

---

문제

---

풀이

0. 방향성 생각

완탐 + BFS

1. 입력

from itertools import combinations as C
from collections import deque
import sys
input = sys.stdin.readline

N,M = map(int,input().split())
arr = [list(map(int,input().split())) for i in range(N)]

virus = set()
for i in range(N):
    for j in range(N):
        if arr[i][j] == 2:
            virus.add((j,i))

 

virus에 바이러스 위치 넣기

 

2. BFS 함수 정의

activation = list(C(virus,M))
step = [[1,-1,0,0],[0,0,1,-1]]

def bfs(array,act_virus):
    visit = [[-1]*N for _ in range(N)]
    q = deque()
    for a,b in act_virus:
        q.append((a,b))
        visit[b][a] = 0
        
    while q:
        x,y = q.popleft()
        
        for i in range(4):
            nx = x + step[0][i]
            ny = y + step[1][i]
            if 0<=nx<N and 0<=ny<N :
                if array[ny][nx] != 1 and visit[ny][nx] == -1:
                    visit[ny][nx] = visit[y][x] + 1
                    q.append((nx,ny))
    time = 0
    for i in range(N):
        for j in range(N):
            if visit[i][j] == -1 and array[i][j] == 0 :
                return -1
            if time < visit[i][j] :
                time = visit[i][j]
    return time

virus 중 바이러스 M개를 뽑는다.

반복작업 해야해서 함수 지역변수에서 돌리는게 빠름

array에 바이러스를 놓고 바이러스를 놓지 않는 곳에는 빈공간으로 수정해준 지도 array을 넣는다.

큐에 virus 위치 넣으주고 BSF 돌리기.

3. 출력

answer = []
for act in activation:
    temp = [row[:] for row in arr]
    for x,y in virus:
        if (x,y) not in act:
            temp[y][x] = 0
    answer.append(bfs(temp,act))
if set(answer) == set([-1]) : print(-1)
else : print(min([i for i in answer if i != -1]))

계속 arr의 copy본을 사용해야함. deep copy 사용해도 상관 없는데 [:]형태로 써주면 새로운 객체 생성 가능.

활성바이러스를 놓지 않는 곳은 0으로 수정.

answer의 원소가 -1 뿐이면 전부 실패 -> -1 출력

그렇지 않은 경우는 -1 제외 가장 작은값

---

전체코드

from itertools import combinations as C
from collections import deque
import sys
input = sys.stdin.readline

N,M = map(int,input().split())
arr = [list(map(int,input().split())) for i in range(N)]

virus = set()
for i in range(N):
    for j in range(N):
        if arr[i][j] == 2:
            virus.add((j,i))

activation = list(C(virus,min(M,len(virus))))
step = [[1,-1,0,0],[0,0,1,-1]]

def bfs(array,act_virus):
    visit = [[-1]*N for _ in range(N)]
    q = deque()
    for a,b in act_virus:
        q.append((a,b))
        visit[b][a] = 0
        
    while q:
        x,y = q.popleft()
        
        for i in range(4):
            nx = x + step[0][i]
            ny = y + step[1][i]
            if 0<=nx<N and 0<=ny<N :
                if array[ny][nx] != 1 and visit[ny][nx] == -1:
                    visit[ny][nx] = visit[y][x] + 1
                    q.append((nx,ny))
    time = 0
    for i in range(N):
        for j in range(N):
            if visit[i][j] == -1 and array[i][j] == 0 :
                return -1
            if time < visit[i][j] :
                time = visit[i][j]
    return time

answer = []
for act in activation:
    temp = [row[:] for row in arr]
    for x,y in virus:
        if (x,y) not in act:
            temp[y][x] = 0
    answer.append(bfs(temp,act))
if set(answer) == set([-1]) : print(-1)
else : print(min([i for i in answer if i != -1]))

 

코멘트

연구소 2풀다가 3으로 넘어가서 풀다가 삽질함.

바이러스 안놓으면 빈칸인거 까먹어서 삽질함