[백준 17142번] 연구소3 (파이썬)

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

17142번: 연구소 3

 

저같은 경우에는

문제 예시는 다 풀었는데

제출해보니

시간초과로 헤매여서

인터넷의 도움을 받았습니다.

 

이 문제에서 풀어야할 것은 

 

1. 바이러스 활성화시킬 케이스 구하기

 

2. 각각의 케이스별로 바이러스 활성화시키고

몇 초 걸리는지 계산하기

 

3. 그 중 최솟값 구하기

 

1은 백트레킹도 가능하지만

저는 이런 류의 문제에 대해서

바로 combination이 떠올랐습니다.

2022.03.24 - [알고리즘 공부] - [백준 15686] 치킨배달(파이썬)

[백준 15686] 치킨배달(파이썬)

취향차이지만

저는 combination이 더 좋은 느낌이네요.

 

2번이 제가 시간초과가 많이 떴던 경우고

인터넷을 찾아보니

오답이 많이 유도되는 케이스입니다.

 

먼저, 시간을 어떻게 구할까 하는 문제입니다.

처음에 저는 단순하게

while문 돌리고

이게 얼마 돌아가는지 시간을 구했습니다.

아마 이것때문에 시간초과가 뜬 것 같은데

인테넷을 참조해보니

last change라는 변수를 따로 두어서

바이러스가 될 때 카운트 해주더군요.

 

바로 그 다음으로 해결해야할 포인트.

빈칸에 바이러스가 옮는 경우와

바이러스가 활성화되는 경우

두 케이스입니다.

빈칸에 바이러스가 옮는 경우에는

바이러스가 옮기는 경우이므로

시간이 증가한다고 볼 수 있습니다.

하지만 활성화시키는 경우에는

'원래 있던 게 켜진 것'

이라고 보기 때문에

증가를 해줘서는 안됩니다.

이게 뭔소리인지

코드를 보겠습니다.

 

# 백준 17142 연구소3
from itertools import combinations
from collections import deque
from copy import deepcopy
import sys

input = sys.stdin.readline

N, M = map(int, input().split())
room = []
virus_po = []
wall = []
for i in range(N):
    data = list(map(int, input().split()))
    room.append(data)
    for j in range(N):
        if data[j] == 2:
            virus_po.append([i, j, 0])
virus_case = []
# 활성,비활성에 대한 모든 케이스를 combination으로 받음


for c in list(combinations(virus_po, M)):
    virus_case.append(c)

min_time = 1e9

dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
for case in virus_case:
    # print(case)
    # 모든 바이러스 케이스에 대해서 바이러스를 퍼트릴 때 최소시간을 구한다
    q = deque()
    visited = [[False] * N for _ in range(N)]
    now_room = deepcopy(room)
    for v in case:
        q.append(v)
        v_x, v_y = v[0], v[1]
        visited[v_x][v_y] = True
        now_room[v_x][v_y] = -2
    last_change = 0
    while q:
        # 현재 바이러스가 한칸씩 움직일때를 구한다
        n_x, n_y, cnt = q.popleft()
        for i in range(4):
            nx = n_x + dx[i]
            ny = n_y + dy[i]
            # 범위
            if nx < 0 or nx >= N or ny < 0 or ny >= N:
                continue
                # 벽을 만나면 스킵
            if now_room[nx][ny] == 1:
                continue
                # 빈칸 & 활성화
            if not now_room[nx][ny] == 1 and not visited[nx][ny]:
                visited[nx][ny] = True
                # 빈칸을 만날 때만 바이러스가 퍼지는 경우이므로, 이 경우에서만 생각해준다.
                # (바이러스 활성화는 엄밀히 말하면 바이러스가 퍼지는게 아니라, 활성화만 시켜주는 것이다)
                if now_room[nx][ny] == 0:
                    now_room[nx][ny] = 2
                    last_change = cnt + 1
                q.append((nx, ny, cnt + 1))

    # 0이 있는 케이스라면 넘긴다
    flag = 0
    for x in range(N):
        count = now_room[x].count(0)
        if count > 0:
            flag = 1
            break
    if flag == 1:
        continue
    min_time = min(min_time, last_change)
    # print(min_time)
    # print()

 

이 풀이같은 경우에는

pypy3로 제출하였습니다.

 

https://m.post.naver.com/viewer/postView.naver?volumeNo=26699948&memberNo=33264526 

[Python] 백준 17142. 연구소 3

저는 이 분의 풀이를 참고했습니다.

여러모로 공부할 것이 많았던 문제였습니다.

 

+++

#백준 17142 연구소3
from collections import deque
from itertools import combinations

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

graph=[]
virus=[]
wall=[]
for i in range(N):
    data=list(map(int,input().split()))
    for j in range(N):
        if data[j]==2:
            virus.append([i,j])
        if data[j]==1:
            wall.append([i,j])
    graph.append(data)


#바이러스를 M개 조합하는 경우를 combination으로 받음
virus_case=combinations(virus,M)

answer=1e9

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

for v in virus_case:
    visited=[[-1]*N for _ in range(N)]
    q=deque()
    #케이스에 있는 모든 바이러스 좌표를 받아줌
    for vir in v:
        vx,vy=vir
        visited[vx][vy]=0
        q.append(vir)
    for w in wall:
        wx,wy=w
        visited[wx][wy]=0
    last=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
            #빈칸이거나 비활성바이러스면 옮겨줌
            q.append([nx,ny])
            visited[nx][ny]=visited[x][y]+1
            #빈칸일 때는 바이러스가 퍼지므로 초 up
            #비활성이면 원래 있던 곳에 퍼지므로 count 생략
            if graph[nx][ny]==0:
                last=visited[x][y]+1


    flag=0
    for x in range(N):
        if visited[x].count(-1):
            flag=1
            break
    if flag==1:
        continue

    answer=min(answer,last)

if answer==1e9:
    print(-1)
else:
    print(answer)

다시 풀어본 코드입니다.

해당 코드는 python3로도 통과가 됩니다.

 

위의 코드와 다른 점은

 

위:원래 graph를 계속 deepcopy로 복사한 후

계속 케이스를 구했다

 

아래:visited에 숫자를 넣어줬고,

벽이 있는 곳은 0,

이미 간 곳은 숫자로 카운트해주면서 bfs시행

 

이 문제가 어려운 이유는

바로 저 부분입니다.

바이러스-->빈칸으로 가는 경우

'없던 바이러스가 생기는 경우'이니

퍼지는 시간에 반영해야합니다.

하지만 다른 경우

바이러스-->비활성으로 가는 경우는

'있던 바이러스가 활동'하는 경우이니

바이러스가 퍼지는 것이 아니므로

퍼지지는 최대 시간에는 반영이 안됩니다.

(있던 게 동작할 뿐이니)

이 두 케이스를 보고 설명드리겠습니다.

위의 3의 경우에는

빈칸에 바이러스가 들어간 경우이므로

퍼지는 시간에 반영이 됩니다.

하지만 아래의 경우에는

원래 있던 것이 활성화 되는 개념이라

시간 반영이 안됩니다.

이렇게 보면

예제 7이 왜 0인지

이해가 되실 겁니다.

만약 예제7이

저렇게 바뀐다면

8로 카운트가 되는 경우가 생깁니다.

킹냐.

빈칸이 바이러스가 퍼지는 케이스가 존재하기 때문에

저렇게 0로 count됩니다.

 

실제로 문제를 자세히 읽어보면

'모든 빈칸에 바이러스를 퍼트리는 최소시간'을 구하는 겁니다.

그러니 바이러스 활성화되는 건 당연히 반영하면 안되고

오로지 빈칸에 바이러스가 들어가는 것만을 반영해야합니다.

 

문제에 답이 있다는 건

이런 걸 두고 하는 건가...