https://www.acmicpc.net/problem/18405
18405번: 경쟁적 전염
첫째 줄에 자연수 N, K가 공백을 기준으로 구분되어 주어진다. (1 ≤ N ≤ 200, 1 ≤ K ≤ 1,000) 둘째 줄부터 N개의 줄에 걸쳐서 시험관의 정보가 주어진다. 각 행은 N개의 원소로 구성되며, 해당 위치
www.acmicpc.net
문제 해결을 위한 과정
이 문제의 경우 BFS만 알고 있다면 쉽게 해결할 수 있는 문제입니다. 그래프를 입력을 받을 때 0이 아닌 즉 바이러스가 있는 부분들에 대한 좌표를 따로 virus라는 리스트를 만들어서 그 리스트에 있는 좌표값들에 대해서만 BFS를 수행하면 되는 것입니다. 이때 문제에서 알 수 있듯이 이미 바이러스가 퍼진 구역에는 어떠한 바이러스도 퍼질 수 없으므로 그래프에서 해당 좌표의 지역이 0 인 경우 즉 비어있는 경우만 탐색을 할 수 있습니다. 또한 문제에서 숫자가 낮은 바이러스가 우선적으로 퍼지는 조건이 있습니다. 이 경우는 문제 해결을 위한 팁에서 알아보겠습니다.
문제 해결을 위한 팁
저의 경우는 바이러스가 있는 곳을 리스트에 넣을때 해당 좌표에 있는 바이러스에 값과 좌표를 리스트에 저장했습니다. 만약 입력 예시 1의 경우 0 행 0열에 있는 바이러스가 1 이기 때문에 virus.append((graph[i][j], i, j)) 이렇게 저장했습니다. 이 형태로 저장을 하게 되면 입력을 다 한 후 virus.sort()를 하게 되면 맨 앞 원소를 기준으로 오름차순으로 정렬을 하기 때문에 별도의 처리 없이 오름차순 된 virus 리스트 그대로 BFS를 수행하면 숫자가 낮은 바이러스부터 우선적으로 탐색을 할 수 있습니다.
소스코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
from collections import deque
N, K = map(int, input().split())
graph = []
virus = []
for i in range(N):
graph.append(list(map(int, input().split())))
for j in range(N):
if graph[i][j] != 0:
virus.append(((graph[i][j], i, j)))
S, X, Y = map(int, input().split())
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def bfs(s, X, Y):
q = deque(virus)
count = 0
while q:
if count == s:
break
for _ in range(len(q)):
prev, x, y = q.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < N and 0 <= ny < N:
if graph[nx][ny] == 0:
graph[nx][ny] = graph[x][y]
q.append((graph[nx][ny], nx, ny))
count += 1
return graph[X-1][Y-1]
virus.sort()
print(bfs(S, X, Y))
|
cs |
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 알고리즘 18428: 감시 피하기(Python) (0) | 2020.12.05 |
|---|---|
| 백준 알고리즘 14888: 연산자 끼워 넣기(Python) (0) | 2020.12.05 |
| 백준 알고리즘 14502: 연구소(Python) (0) | 2020.12.05 |
| 백준 알고리즘 18352: 특정 거리의 도시 찾기(Python) (0) | 2020.12.04 |
| 백준 알고리즘 15686: 치킨 배달 (Python) (0) | 2020.11.30 |