Python
14502. 연구소 시간 단축 코드 - 백트래킹 말고, python 문제 풀이
BrianaAI
2024. 2. 14. 19:46
안녕하세요.
브리아나입니다.
오늘은 백트래킹 말고,
시간 더 단축시킬 수 있는 경우를 풀어보겠습니다.
그래도 3개라는 숫자가 주어지니까 가능한 버전입니다.
문제.
https://www.acmicpc.net/problem/14502
14502번: 연구소
인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크
www.acmicpc.net
풀이.
N, M = map(int, input().split())
arr = []
path = []
virus = []
for i in range(N):
arr.append(list(map(int, input().split())))
for j in range(M):
if arr[i][j] == 0:
path.append((i, j))
elif arr[i][j] == 2:
virus.append((i, j))
dx, dy = [-1, 1, 0, 0], [0, 0, -1, 1]
def bfs(tlst):
# [1] make wall 3 times
for tx, ty in tlst:
arr[tx][ty] = 1
# [2] initialize virus info
q = []
w = [[0]*M for _ in range(N)]
for vx, vy in virus:
w[vx][vy] = 1
q.append((vx, vy))
chance = cnt-3
while q:
cx, cy = q.pop(0)
for i in range(4):
nx, ny = cx+dx[i], cy+dy[i]
if 0<=nx<N and 0<=ny<M and w[nx][ny] == 0 and arr[nx][ny] == 0:
w[nx][ny] = 1
q.append((nx, ny))
chance-=1
# reset
for tx, ty in tlst:
arr[tx][ty] = 0
return chance
cnt = len(path)
ans = 0
for i in range(cnt-2):
for j in range(i+1, cnt-1):
for k in range(j+1, cnt):
ans = max(ans, bfs([path[i], path[j], path[k]]))
print(ans)
참고하세요 ~~