14502번: 연구소
인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크�
www.acmicpc.net
<내 코드>
import copy
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
answer = 0
def bfs():
global answer
v = copy.deepcopy(virus) # 원본 유지한채 복사(바이러스 좌표값)
tmp = [[0]*M for _ in range(N)]
# 지도 복사
for i in range(N):
for j in range(M):
tmp[i][j] = maps[i][j]
# 4방향 탐색 후 바이러스 감염
while len(v) != 0:
vir = v.pop()
vir_x = vir[0]
vir_y = vir[1]
for k in range(4):
nx = vir_x + dx[k]
ny = vir_y + dy[k]
if 0 <= nx < N and 0 <= ny < M:
if tmp[nx][ny] == 0:
tmp[nx][ny] = 2
v.append([nx, ny])
# 0(안전구역) 갯수 파악
result = 0
for i in tmp:
for j in i:
if j == 0:
result += 1
answer = max(result, answer)
# 벽 3개를 세우는 모든 경우의 수
def wall(cnt):
if cnt == 3:
bfs()
return
for i in range(N):
for j in range(M):
if maps[i][j] == 0:
maps[i][j] = 1
wall(cnt+1)
maps[i][j] = 0
N, M = map(int, input().split())
maps = [list(map(int, input().split())) for _ in range(N)]
virus = []
# 바이러스 좌표값 저장
for i in range(N):
for j in range(M):
if maps[i][j] == 2:
virus.append([i, j])
wall(0)
print(answer)
벽 3개를 세우는 방법을 알지 못해 다른 사람들의 코드를 참고했다. 여기서 입력의 크기가 크지 않기 때문에 브루트포스를 사용해 벽3개를 세우는 경우의 수를 다 구했다. 모든 경우의 수를 구하는 코드를 이해하는데 쉽지 않았다..
앞으로 자주 사용될 것 같다.
반응형
'알고리즘 문제풀기 > 백준 - Python' 카테고리의 다른 글
[백준 13458] 시험 감독 - Python (수학) (0) | 2020.09.23 |
---|---|
[백준 14503] 로봇 청소기 - Python (구현, 시뮬레이션) (0) | 2020.09.23 |
[백준 14499] 주사위 굴리기 - Python (구현) (0) | 2020.09.22 |
[백준 1316] 그룹 단어 체커 - Python (문자열) (0) | 2020.09.10 |
[백준 2941] 크로아티아 알파벳 - Python (문자열) (0) | 2020.09.10 |