https://www.acmicpc.net/problem/14502
14502번: 연구소
인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크
www.acmicpc.net
문제
문제 해결을 위한 과정
이 문제의 경우 조건을 보면 8 x 8로 크기가 제한이 되어있는 것을 알 수 있습니다. 또한 3가지의 벽을 세우는 경우 이므로 64가지의 경우에서 순서에 상관없이 3을 뽑는 즉 64C3이기 때문에 완전 탐색으로 해결해야 함을 알 수 있습니다. 따라서 그래프를 입력받을 때 바이러스인 좌표를 저장하는 리스트와 빈칸을 저장하는 리스트를 각각 만든 후 빈칸의 영역에서 combinations을 사용하여 3개의 구역에 벽을 세운 후 BFS를 이용하여 문제를 해결합니다.
문제 해결을 위한 팁
조합을 이용해 3가지 구역에 대해서 벽을 세운 후 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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
from itertools import combinations
from collections import deque
import copy
N, M = map(int, input().split())
graph = []
blank = []
virus = []
for i in range(N):
graph.append(list(map(int, input().split())))
for j in range(M):
if graph[i][j] == 0:
blank.append((i, j))
elif graph[i][j] == 2:
virus.append((i, j))
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def bfs():
testgraph = copy.deepcopy(graph)
q = deque(virus)
while q:
x, y = q.popleft()
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0 <= nx < N and 0 <= ny < M:
if testgraph[nx][ny] == 0:
testgraph[nx][ny] = 2
q.append((nx, ny))
count = 0
for i in range(N):
for j in range(M):
if testgraph[i][j] == 0:
count += 1
return count
answer = 0
for data in combinations(blank, 3):
for x, y in data:
graph[x][y] = 1
answer = max(answer, bfs())
for x, y in data:
graph[x][y] = 0
print(answer)
|
cs |
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 알고리즘 14888: 연산자 끼워 넣기(Python) (0) | 2020.12.05 |
|---|---|
| 백준 알고리즘 18405: 경쟁적 전염(Python) (0) | 2020.12.05 |
| 백준 알고리즘 18352: 특정 거리의 도시 찾기(Python) (0) | 2020.12.04 |
| 백준 알고리즘 15686: 치킨 배달 (Python) (0) | 2020.11.30 |
| 백준 알고리즘 3190: 뱀(Python, c++) (0) | 2020.11.29 |
