[파이썬] 백준 연구소3 : 17142 (골드3)

[파이썬] 백준 연구소3 : 17142 (골드3)

 

17142번: 연구소 3

---

문제

---

풀이

0. 방향성 생각

완탐 + BFS

 

1. 입력

from itertools import combinations as C
from collections import deque
import sys
input = lambda: sys.stdin.readline().rstrip()

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

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

마지막 테스트 케이스 같은 경우 (빈칸이 없는 경우) 0 출력해야함.

이를 잡기위해 집합 a 정의하고 계속 업데이트

virus에는 바이러스 위치 구하기

 

2. BFS 함수 정의

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] and array[i][j] == 0:
                time = visit[i][j]
    return time

이전 연구소 2와 비슷한 방식으로 진행.

방문 안했고 벽이 아닌 경우에 방문처리 + 도달거리 업데이트

visit 순회하면서 빈공간인데 방문처리 못했으면 return -1

visit 순회하면서 현재 최대 시간이 visit보다 작고 그게 빈칸인 경우 time 업데이트

 

3. 출력

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

0 없으면 0 출력

아닌 경우에는 BFS 실행. 

정답에 -1 만 있는 경우 (모두 실패) -1 출력, 아닌 경우는 -1 제외 가장 작은 값 출력

---

전체코드

from itertools import combinations as C
from collections import deque
import sys
input = lambda: sys.stdin.readline().rstrip()

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

a = set()
virus = set()
for i in range(N):
    a.update(arr[i])
    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] and array[i][j] == 0:
                time = visit[i][j]
    return time

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

코멘트

빈칸 0 없으면 0 출력인데 -1 해놓고 삽질함

코드 복붙해서 대충 날먹하는거보다 조건 확인하면서 첨부터 짜는게 빠른듯