백준 17141 연구소 2 Python

🐸 문제 정보

17141번: 연구소 2

 

🤖 알고리즘

BFS

 

⏱️ 풀이 시간

30.20m

 

📝 풀이

그냥 BFS로 절대 통과 못할 줄 알았는데... 시간이 간당간당하게 맞은 것 같다.

구현이랑 섞인 BFS의 대표적인 문제 같은 느낌이었다.

 

나의 경우, 바이러스를 올릴 수 있는 노드와, 벽의 노드를 입력 때 미리 저장해두고

바이러스를 올릴 수 있는 노드에서 m개 만큼의 조합으로 BFS를 돌린 후,

벽의 노드를 제외한 노드가 모두 방문처리 되었는지 확인했다.

 

코드가 꽤 복잡하게 짜여진 것 같..다..

하지만 BFS는..원래그..래ㄹ..걸..?

 

🧑‍💻 나의 답

# pypy3

import sys
from itertools import combinations
from collections import deque
input = sys.stdin.readline
INF = sys.maxsize

n, m = list(map(int, input().rstrip().split()))
graph = []
nodes = []
walls = []
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
res = INF

for i in range(n):
    row = list(map(int, input().rstrip().split()))
    for j in range(n):
        if row[j] == 2:
            nodes.append((i, j))
        elif row[j] == 1:
            walls.append((i, j))
    graph.append(row)

def bfs(frame):
    global res
    q = deque([])
    temp = 0
    for node in frame:
        q.append(node)
        times[node[0]][node[1]] = 0
    while q:
        px, py = q.popleft()
        for i in range(4):
            nx, ny = px + dx[i], py + dy[i]
            if (0 <= nx < n) and (0 <= ny < n) and (graph[nx][ny] != 1) and (times[px][py] + 1 < times[nx][ny]):
                times[nx][ny] = times[px][py] + 1
                temp = max(temp, times[nx][ny])
                q.append((nx, ny))
    flag = False
    for i in range(n):
        for j in range(n):
            if (i, j) in walls: continue
            if times[i][j] == INF:
                flag = True
                break
    if not flag:
        res = min(res, temp)

for frame in combinations(nodes, m):
    times = [[INF] * n for _ in range(n)]
    bfs(frame)

if res == INF:
    print(-1)
else:
    print(res)