알고리즘 문제 풀이
129. [삼성기출25]Python 백준 17142 번 연구소 3
코딩하는 덕구 🐶
2023. 6. 23. 15:04
728x90
반응형
안녕하세요 코딩하는 덕구입니다.
백준 17142 연구소 3 입니다.
https://www.acmicpc.net/problem/17142
17142번: 연구소 3
인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고,
www.acmicpc.net
먼저 백준 17142 연구소 3 코드입니다. 설명은 아래에 있습니다.
import sys
input = sys.stdin.readline
from itertools import combinations
from collections import deque
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
N, M = map(int, input().split())
lab = []
virus = []
total_empty = 0
for _ in range(N):
lab.append(list(map(int, input().split())))
for i in range(N):
for j in range(N):
if lab[i][j] == 2:
virus.append([i, j])
elif lab[i][j] == 0:
total_empty += 1
def bfs(board, virus_list, remain):
global min_time
visited = [[False for _ in range(N)] for _ in range(N)]
queue = deque()
for v in virus_list:
i, j = v
visited[i][j] = True
queue.append([i, j, 0])
while queue:
x, y, time = queue.popleft()
if time >= min_time:
return 1e9
if board[x][y] == 0:
remain -= 1
if remain == 0:
return time
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < N and 0 <= ny < N:
if board[nx][ny] != 1:
if not visited[nx][ny]:
visited[nx][ny] = True
queue.append([nx, ny, time + 1])
return 1e9
min_time = 1e9
for c in combinations(virus, M):
min_time = min(min_time, bfs(lab, c, total_empty))
if min_time == 1e9:
min_time = -1
print(min_time)
문제 접근
모든 빈공간에 바이러스를 퍼트려야 됩니다.
combinations로 M개의 바이러스를 선택하고 바이러스를 BFS로 퍼트리며 최단 시간을 업데이트 합니다.
BFS시에 활성화가 안 된 바이러스, 빈 공간은 같은 취급 해주면 되고 (방문처리 후 큐에 삽입)
빈 공간의 남아있는 개수를 추적하여 0이 되면 bfs를 종료하고 걸린 시간을 출력하면 됩니다.
Python 코드 구현
빈 공간의 개수, 바이러스의 위치를 파악합니다.
import sys
input = sys.stdin.readline
from itertools import combinations
from collections import deque
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
N, M = map(int, input().split())
lab = []
virus = []
total_empty = 0
for _ in range(N):
lab.append(list(map(int, input().split())))
for i in range(N):
for j in range(N):
if lab[i][j] == 2:
virus.append([i, j])
elif lab[i][j] == 0:
total_empty += 1
조합을 통해 M개의 바이러스를 선택해서 BFS에 넣어주고, 최솟값을 업데이트 한 후 출력하면 됩니다.
min_time = 1e9
for c in combinations(virus, M):
min_time = min(min_time, bfs(lab, c, total_empty))
if min_time == 1e9:
min_time = -1
print(min_time)
BFS입니다. 단순하게 그래프 내의 모든 빈 공간을 탐색하면 됩니다.
만약 불가능하다면 1e9를 출력합니다.
def bfs(board, virus_list, remain):
global min_time
visited = [[False for _ in range(N)] for _ in range(N)]
queue = deque()
for v in virus_list:
i, j = v
visited[i][j] = True
queue.append([i, j, 0])
while queue:
x, y, time = queue.popleft()
if time >= min_time:
return 1e9
if board[x][y] == 0:
remain -= 1
if remain == 0:
return time
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < N and 0 <= ny < N:
if board[nx][ny] != 1:
if not visited[nx][ny]:
visited[nx][ny] = True
queue.append([nx, ny, time + 1])
return 1e9
파이썬 백준 17142 연구소3 최종 코드입니다.
import sys
input = sys.stdin.readline
from itertools import combinations
from collections import deque
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
N, M = map(int, input().split())
lab = []
virus = []
total_empty = 0
for _ in range(N):
lab.append(list(map(int, input().split())))
for i in range(N):
for j in range(N):
if lab[i][j] == 2:
virus.append([i, j])
elif lab[i][j] == 0:
total_empty += 1
def bfs(board, virus_list, remain):
global min_time
visited = [[False for _ in range(N)] for _ in range(N)]
queue = deque()
for v in virus_list:
i, j = v
visited[i][j] = True
queue.append([i, j, 0])
while queue:
x, y, time = queue.popleft()
if time >= min_time:
return 1e9
if board[x][y] == 0:
remain -= 1
if remain == 0:
return time
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < N and 0 <= ny < N:
if board[nx][ny] != 1:
if not visited[nx][ny]:
visited[nx][ny] = True
queue.append([nx, ny, time + 1])
return 1e9
min_time = 1e9
for c in combinations(virus, M):
min_time = min(min_time, bfs(lab, c, total_empty))
if min_time == 1e9:
min_time = -1
print(min_time)
백준 17142 연구소 3 Python 코드였습니다.
감사합니다.
728x90
반응형