[백준 17142번] 연구소 3 - Python으로 구현하기

[백준 17142번] 연구소 3 - Python으로 구현하기

 

문제 접근

• BFS 문제이고, 역시나 itertools의 combinations로 조합의 수를 구해보자
• 단, 문제에서 구해야 되는 건 그냥 dist가 아닌, 활성화바이러스가 아닌 칸의 dist 최대값으로 구해줘야한다.
• 따라서 if map_data[nx][ny]==0: 의 조건안에 최대 dist를 구하는 부분으로 해결

 

생각해볼 점

• list(sum(ar,[])) 대신 itertools의 chain 모듈을 쓰는게 훨씬 빠르다. Chain(*ar)

 

오답 분석

• 비활성화 -> 활성화 되는 바이러스의 dist를 고려하는 실수가 많다.

 

from collections import deque
from itertools import combinations as cm

def bfs(virus_list):
    dist = [[-1] * N for _ in range(N)]
    dq=deque()
    for pos in virus_list:
        dq.append(pos)
        dist[pos[0]][pos[1]] = 0
    max_dist=0
    while dq:
        x,y=dq.popleft()
        for k in range(4):
            nx=x+di[k][0]
            ny=y+di[k][1]

            if 0<=nx<N and 0<=ny<N and map_data[nx][ny]!=1 and dist[nx][ny]==-1:
                dist[nx][ny]=dist[x][y]+1
                if map_data[nx][ny]==0:
                    max_dist=max(max_dist,dist[nx][ny])
                dq.append([nx,ny])

    a = list(sum(dist,[]))
    if a.count(-1)==list(sum(map_data,[])).count(1):	# 방문 안 한 곳이 벽의 개수와 동일한지
        ans.append(max_dist)	# 리스트없이 바로 min값 구해도 됨

N,M = map(int,input().split())
map_data = [list(map(int,input().split())) for _ in range(N)]
di = [[1,0],[0,1],[-1,0],[0,-1]]

virus_pos=deque()
ans=[]
for i in range(N):
    for j in range(N):
        if map_data[i][j]==2:
            virus_pos.append([i,j])

for now_virus_list in cm(virus_pos,M):
    bfs(now_virus_list)

print(min(ans) if ans else -1)

 

* 틀린 부분이나 더 나은 방법이 있을 수 있습니다. 지적해주시면 감사하겠습니다!!