[백준 17141번] 연구소2(파이썬)

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

17141번: 연구소 2

이 문제는 유사한 연구소1,연구소3 등의 문제를

예전에 풀어본 적이 있어서 체감적으로 쉬웠습니다.

 

구현할 건 2가지.

 

1. 어떤 지점에서 바이러스를 처음 둘 것인가

 

2. 바이러스를 어떻게 퍼트리고 최댓값을 구할 것인가

 

1의 경우, 저는 combination을 사용했습니다.

백트레킹도 좋긴한데

저는 이 방식이 가장 간편했습니다.

2의 경우에는 bfs를 사용했습니다.

사전에 visited라는, -1로 되어있는 배열을 선언.

그리고 바이러스가 놓여질 위치는 0으로 만들어주고

bfs를 선언해줍니다.

만약에 bfs를 끝냈는데

벽이 아닌 곳 좌표의 visited가 -1이라면

바이러스가 채워진 게 아니므로

넘겨줍니다.

만약 모두 바이러스가 통과했다면

가장 마지막으로 카운트된 초랑

최종 답 중 최솟값을 받는 식입니다.

 

#백준 17141번 연구소2
from collections import deque
from itertools import combinations

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

N,M=map(int,input().split())
room=[]
p_virus=[]

answer=1e9

for i in range(N):
    tmp=list(map(int,input().split()))
    for j in range(N):
        if tmp[j]==2:
            p_virus.append([i,j])
    room.append(tmp)


c=combinations(p_virus,M)
for com in c:
    q=deque()
    visited=[[-1]*N for _ in range(N)]
    for put in com:
        q.append(put)
        x,y=put
        visited[x][y]=0
    cnt=0
    while q:
        x,y=q.popleft()

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

            if nx<0 or nx>=N or ny<0 or ny>=N:
                continue
            if visited[nx][ny]>=0:
                continue
            if room[nx][ny]==1:
                continue
            q.append([nx,ny])
            visited[nx][ny]=visited[x][y]+1
            cnt=max(cnt,visited[nx][ny])

    no=0
    out=0
    for x in range(N):
        for y in range(N):
            if not room[x][y]==1 and visited[x][y]==-1:
                out=1
                break
        if out==1:
            no=1
            break
    if no==1:
        continue

    answer=min(answer,cnt)

if answer==1e9:
    answer=-1

print(answer)

https://chldkato.tistory.com/134

백준 17141 연구소 2 (파이썬)

바이러스의 경우를 구할 때

이렇게 DFS로 구하는 경우도 있습니다.

학습에 참고하시면 좋을 것 같습니다.