정보
문제 바로가기 [클릭]
난이도: Gold5
관련 개념: #구현 #그래프이론 #그래프탐색 #너비 우선 탐색 #브루트포스
조건
| 시간 제한 | 메모리 제한 |
|---|---|
| 2 초 | 512 MB |
문제
인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.
연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다.
일부 칸은 바이러스가 존재하며, 이 바이러스는 상하좌우로 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.
예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자.
1
2
3
4
5
6
7
2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0
이때, 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 곳이다. 아무런 벽을 세우지 않는다면, 바이러스는 모든 빈 칸으로 퍼져나갈 수 있다.
2행 1열, 1행 2열, 4행 6열에 벽을 세운다면 지도의 모양은 아래와 같아지게 된다.
1
2
3
4
5
6
7
2 1 0 0 1 1 0
1 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 1 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0
바이러스가 퍼진 뒤의 모습은 아래와 같아진다.
1
2
3
4
5
6
7
2 1 0 0 1 1 2
1 0 1 0 1 2 2
0 1 1 0 1 2 2
0 1 0 0 0 1 2
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0
벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다. 위의 지도에서 안전 영역의 크기는 27이다.
연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최댓값을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8)
둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다.
빈 칸의 개수는 3개 이상이다.
출력
첫째 줄에 얻을 수 있는 안전 영역의 최대 크기를 출력한다.
예제 입출력 1
입력
1
2
3
4
5
6
7
8
7 7
2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0
출력
1
27
예제 입출력 2
입력
1
2
3
4
5
4 6
0 0 0 0 0 0
1 0 0 0 0 2
1 1 1 0 0 2
0 0 0 0 0 2
출력
1
9
예제 입출력 3
입력
1
2
3
4
5
6
7
8
9
8 8
2 0 0 0 0 0 0 2
2 0 0 0 0 0 0 2
2 0 0 0 0 0 0 2
2 0 0 0 0 0 0 2
2 0 0 0 0 0 0 2
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
출력
1
3
코드(파이썬)
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
from itertools import combinations
from copy import deepcopy
def bfs():
queue = start.copy()
tmp_lab = deepcopy(lab)
while queue:
y, x = queue.pop()
tmp_lab[y][x] = 2
for i in range(4):
next_x = x + dx[i]
next_y = y + dy[i]
if -1 < next_y < n and -1 < next_x < m and tmp_lab[next_y][next_x] == 0:
queue.append((next_y, next_x))
return sum([row.count(0) for row in tmp_lab])
n, m = map(int, input().split())
lab = [list(map(int, input().split())) for _ in range(n)]
blank = [(i,j) for i in range(n) for j in range(m) if lab[i][j] == 0]
start = [(i,j) for i in range(n) for j in range(m) if lab[i][j] == 2]
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
result = 0
for walls in combinations(blank, 3):
for i, j in walls:
lab[i][j] = 1
result = max(result, bfs())
for i, j in walls:
lab[i][j] = 0
print(result)
특이사항
- 해결방법
- 연구소 최대 크기가 8x8이어서 브루트포스로 진행
- 최대 조합의 수는 62C3 = 37820이므로 시간초과가 없었지만 풀이의 방법은 시간복잡도가 높아 간신히 통과
- 내 코드(30,966KB, 5,665ms)에 비해 우수한 코드(바로가기, 32,528KB, 1,552ms)와 비교
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 52 53 54 55 56 57 58 59 60 61
import sys; input = sys.stdin.readline from itertools import combinations from collections import deque N, M = map(int, input().split()) graph = [] for _ in range(N) : graph.append(input().split()) total = N * M wall = 0 virus = 0 virus_pos = [] zero_pos = [] for i in range(N) : for j in range(M) : if graph[i][j] == '1' : wall += 1 elif graph[i][j] == '2' : virus_pos.append((i, j)) virus += 1 else : zero_pos.append((i, j)) def bfs(set_wall_yx, new_graph) : for sy, sx in set_wall_yx : new_graph[sy][sx] = '1' safe_cnt = total - virus - wall - 3 que = deque(virus_pos) while que : length = len(que) infected_cnt = 0 for _ in range(length) : vi, vj = que.popleft() if 0 <= vi - 1 and new_graph[vi-1][vj] == '0' : new_graph[vi-1][vj] = '2' que.append((vi-1, vj)) infected_cnt += 1 if vi + 1 < N and new_graph[vi+1][vj] == '0' : new_graph[vi+1][vj] = '2' que.append((vi+1, vj)) infected_cnt += 1 if 0 <= vj - 1 and new_graph[vi][vj-1] == '0' : new_graph[vi][vj-1] = '2' que.append((vi, vj-1)) infected_cnt += 1 if vj + 1 < M and new_graph[vi][vj+1] == '0' : new_graph[vi][vj+1] = '2' que.append((vi, vj+1)) infected_cnt += 1 safe_cnt -= infected_cnt if not infected_cnt : return safe_cnt max_safe_cnt = 0 for set_wall_yx in combinations(zero_pos, 3) : copy_graph = [graph[i][:] for i in range(N)] each_safe_cnt = bfs(set_wall_yx, copy_graph) if each_safe_cnt > max_safe_cnt : max_safe_cnt = each_safe_cnt print(max_safe_cnt)
- 안전 영역 계산
- 기존: lab의 모든 0의 개수를 더함
- 개선: lab의 0을 지날 때마다 cnt를 1씩 증가시키고 마지막에 이를 뻄
참고문헌
-
Comments powered by Disqus.