반응형
https://www.acmicpc.net/problem/14502
14502번: 연구소
인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크
www.acmicpc.net
import copy
import sys
x_lim, y_lim = map(int, input().split())
table = []
virus = []
empty = []
for i in range(x_lim):
table.append(list(map(int, input().split())))
for j in range(y_lim):
if table[i][j] == 2:
virus.append([i, j])
elif table[i][j] == 0:
empty.append([i, j])
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
def dfs(x, y, map): # spread viruses
sum= 1
for j in range(4):
nx = x + dx[j]
ny = y + dy[j]
if 0 <= nx < x_lim and 0 <= ny < y_lim and map[nx][ny]==0:
map[nx][ny] = 2
sum += dfs(nx, ny,map)
return sum
answer = -sys.maxsize
# select places to put walls by brute force
for i in range(len(empty) - 2):
for j in range(i + 1, len(empty) - 1):
for k in range(j + 1, len(empty)):
x1, y1 = empty[i]
x2, y2 = empty[j]
x3, y3 = empty[k]
sub_table = copy.deepcopy(table)
sub_table[x1][y1] = 1
sub_table[x2][y2] = 1
sub_table[x3][y3] = 1
infected = 0
for v in range(len(virus)):
x, y = virus[v]
infected += dfs(x, y, sub_table)
infected -= 1
safe = len(empty) - 3 - infected
answer = max(answer, safe)
print(answer)문제를 보면 가장 먼저 떠오르는 게 어느 위치에 벽 3개를 세울 것인가다. 처음에 엄청 고민했지만
문제에서 연구소의 위치가 최대 8*8이라고 했기 때문에 벽3개를 고르는 경우는 최대 64C3 = 약 6천여개다.
따라서 브루트 포스로 풀릴 것이라 생각을 했다.
문제를 엄청 오래 걸려서 풀었는데 사소한 실수로 인하여 시간을 많이 잡아먹었다.
첫번째, 브루트 포스를 하는 과정에서 안에 for문 하나를 사용했는데
이 인자를 i로 놓는 바람에 엄청 꼬이고 헤맸다. 그래서 v로 바꿔주었다.
두번째, dfs 함수 내에서 map[nx][ny]를 계속 map[x][y]로 하고 못찾는 바람에 이걸로도 시간을 많이 썼다.
사소한 실수는 금물이다!!
배운점
- copy를 임포트하고 copy.deepcopy를 사용하면 리스트 내부의 리스트까지도 얕은 복사를 할 수 있다.
(그냥 copy()는 리스트 내부 리스트의 얕은 복사는 안됨)
++++ copy 안쓰고 풀기
근데 소요시간이 2배나 걸리네...?
import sys
x_lim, y_lim = map(int, input().split())
table = []
virus = []
empty = []
for i in range(x_lim):
table.append(list(map(int, input().split())))
for j in range(y_lim):
if table[i][j] == 2:
virus.append([i, j])
elif table[i][j] == 0:
empty.append([i, j])
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
def dfs(x, y):
if table[x][y] == 2 or table[x][y] == 1:
return 0
sum = 1
for j in range(4):
nx = x + dx[j]
ny = y + dy[j]
if 0 <= nx < x_lim and 0 <= ny < y_lim:
table[x][y] = 2
sum += dfs(nx, ny)
return sum
answer = -sys.maxsize
# select places to put walls by brute force
for i in range(len(empty) - 2):
for j in range(i + 1, len(empty) - 1):
for k in range(j + 1, len(empty)):
x1, y1 = empty[i]
x2, y2 = empty[j]
x3, y3 = empty[k]
table[x1][y1] = 1
table[x2][y2] = 1
table[x3][y3] = 1
infected = 0
for v in range(len(virus)):
x, y = virus[v]
table[x][y] = 0
infected += dfs(x, y)
infected -= 1
safe = len(empty) - 3 - infected
answer = max(answer, safe)
# return table to original
table[x1][y1] = 0
table[x2][y2] = 0
table[x3][y3] = 0
for a in range(x_lim):
for b in range(y_lim):
if table[a][b] == 2:
if [a,b] not in virus:
table[a][b] = 0
print(answer)dfs 내부만 조금 바꾼것 성능이 조금은 개선되었으나 첫번째 방법보단 훨씬 뒤떨어짐
import sys
x_lim, y_lim = map(int, input().split())
table = []
virus = []
empty = []
for i in range(x_lim):
table.append(list(map(int, input().split())))
for j in range(y_lim):
if table[i][j] == 2:
virus.append([i, j])
elif table[i][j] == 0:
empty.append([i, j])
dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
def dfs(x, y):
sum = 1
for j in range(4):
nx = x + dx[j]
ny = y + dy[j]
if 0 <= nx < x_lim and 0 <= ny < y_lim and table[nx][ny]==0:
table[nx][ny] = 2
sum += dfs(nx, ny)
return sum
answer = -sys.maxsize
# select places to put walls by brute force
for i in range(len(empty) - 2):
for j in range(i + 1, len(empty) - 1):
for k in range(j + 1, len(empty)):
x1, y1 = empty[i]
x2, y2 = empty[j]
x3, y3 = empty[k]
table[x1][y1] = 1
table[x2][y2] = 1
table[x3][y3] = 1
infected = 0
for v in range(len(virus)):
x, y = virus[v]
infected += dfs(x, y)
infected -= 1
safe = len(empty) - 3 - infected
answer = max(answer, safe)
# return table to original
table[x1][y1] = 0
table[x2][y2] = 0
table[x3][y3] = 0
for a in range(x_lim):
for b in range(y_lim):
if table[a][b] == 2:
if [a,b] not in virus:
table[a][b] = 0
print(answer)
댓글