[BOJ/python] 17141번 연구소 2

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

17141번: 연구소 2

 

 

문제 해석

 

1은 벽이고, 2는 바이러스를 놓을 수 있는 연구소에 m개의 바이러스를 선택하여 퍼지도록 하였을 때 최소 시간이 되는 경우의 시간을 출력하시오.

---

코드

 

# BOJ 17141
from collections import deque

n, virusNum = map(int, input().split())
arr = []
start = []
wall = []
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]

# Input
for i in range(n):
    arr.append(list(map(int, input().split())))
    for j in range(n):
        if arr[i][j] == 2: start.append((i, j))
        if arr[i][j] == 1: wall.append((i, j))

# 방문 노드 초기화 함수
def mkvisit():
    visit = [[0] * n for _ in range(n)]
    for i, j in wall:
        visit[i][j] = 1
    return visit

setXY = []

# m개의 바이러스를 놓을 좌표를 선택할 경우
def selectXY(out, l):
    if len(out) == virusNum:
        setXY.append(out.copy())
        return
    else:
        for k in range(l, len(start)):
            i, j = start[k]
            out.append((i, j))
            selectXY(out, k + 1)
            out.pop()

def bfs(startList):
    q = deque()
    visit = mkvisit()
    for i, j in startList:
        q.append((i, j))
        visit[i][j] = 1
    while q:
        i, j = q.popleft()
        for k in range(4):
            x, y = i + dx[k], j + dy[k]
            if not(0 <= x < n and 0 <= y < n): continue
            if visit[x][y] >= 1 or arr[x][y] == 1: continue
            if visit[x][y] == 0:
                visit[x][y] = visit[i][j] + 1
                q.append((x, y))

    # for k in visit:
    #     print(*k)
    ans = 0
    for i in range(n):
        for j in range(n):
            if visit[i][j] == 0: return -1
            else: ans = max(ans, visit[i][j])
    return ans - 1

selectXY([], 0)

ans = 3000
flag = False
for k in setXY:
    t = bfs(k)
    # print(t)
    # print()
    if t != -1: ans = min(ans, t)

if ans == 3000: ans = -1
print(ans)

---

문제 풀이

 

연구소에 2가 존재하는 위치들 중에서 m개를 선택하는 경우의 수를 모두 구한뒤 해당 좌표를 BFS 큐에 넣어 바이러스가 모두 퍼지는 시간을 구한다.

# Input
for i in range(n):
    arr.append(list(map(int, input().split())))
    for j in range(n):
        if arr[i][j] == 2: start.append((i, j))
        if arr[i][j] == 1: wall.append((i, j))

먼저 Input에서 벽과 놓을수 있는 바이러스의 좌표를 배열에 따로 저장해 주었다.

# 방문 노드 초기화 함수
def mkvisit():
    visit = [[0] * n for _ in range(n)]
    for i, j in wall:
        visit[i][j] = 1
    return visit

경우의 수를 구한뒤 BFS를 여러번 돌리면 방문 노드를 초기화 시켜주어야 한다. 이때 벽들의 좌표는 방문 노드에 미리 1을 넣어 방문 노드를 초기화 하는 함수를 구현한다.

setXY = []
# m개의 바이러스를 놓을 좌표를 선택할 경우
def selectXY(out, l):
    if len(out) == virusNum:
        setXY.append(out.copy())
        return
    else:
        for k in range(l, len(start)):
            i, j = start[k]
            out.append((i, j))
            selectXY(out, k + 1)
            out.pop()

setXY에 m개의 바이러스를 놓을 경우의 수를 조합을 통해 모두 넣어주는 함수이다.

def bfs(startList):
    q = deque()
    visit = mkvisit()
    for i, j in startList:
        q.append((i, j))
        visit[i][j] = 1
    while q:
        i, j = q.popleft()
        for k in range(4):
            x, y = i + dx[k], j + dy[k]
            if not(0 <= x < n and 0 <= y < n): continue
            if visit[x][y] >= 1 or arr[x][y] == 1: continue
            if visit[x][y] == 0:
                visit[x][y] = visit[i][j] + 1
                q.append((x, y))
    ans = 0
    for i in range(n):
        for j in range(n):
            if visit[i][j] == 0: return -1
            else: ans = max(ans, visit[i][j])
    return ans - 1

BFS 함수이다. 인자로 m개의 바이러스를 선택한 배열을 입력받는다.

방문 노드를 초기화시키고, m개의 좌표들을 모두 큐에 넣고, 해당 방문 노드를 설정한 뒤 while문을 통해 BFS 탐색을 시작한다.

방문노드가 0일 때 이전 방문 좌표에 +1 한 값을 현재 방문 노드 좌표에 넣어주었다.

탐색이 종료된 뒤 다시 0,0 부터 n,n까지 돌며 최대값을 저장해주어 소요 시간을 구한다.

만약 이때 방문노드가 0인 곳이 존재한다면 바이러스가 모두 퍼지지 못한 경우이기 때문에 -1을 반환해주도록 구현했다.

selectXY([], 0)
ans = 3000
for k in setXY:
    t = bfs(k)
    if t != -1: ans = min(ans, t)

if ans == 3000: ans = -1
print(ans)

실제 실행 부분이다.

먼저 selectXY 함수를 통해 setXY 배열에 m개의 바이러스를 선택한 좌표들의 리스트가 담도록 해준다.

최대 소요시간은 2500이므로 해당 수보다 큰 3000을 지정하고, BFS를 돌린다.

만약 결과가 -1 이라면 ans값을 바꾸지 않고, 아니라면 더 작은 값을 선택해준다.

모든 탐색이 완료된 뒤 ans 값이 3000이라면 모든 경우에서 바이러스가 전부 퍼진 경우가 없기 때문에 답을 -1로 바꾸어 주어 출력한다.