문제: https://www.acmicpc.net/problem/14502
처음 문제를 봤을 때, 벽을 세울 3개의 좌표를 어떻게 찾아줘야 좋을까 고민을 많이 했다.
그런데 경우의 수가 너무 많았고, 경우의 수들 중 안전 영역의 크기가 최대가 되도록 하는 좌표를 특정해줄 수 없겠다고 판단하였다.
따라서 가능한 모든 경우의 수에 대해 안전영역 크기를 계산하고, 그 값들 중 최댓값을 구하는 방식으로 풀이해야겠다고 생각했다.
모든 경우의 수에 대해 계산할 때, 시간복잡도를 만족할지 알아보기 위해 다음과 같이 계산해보았다.
지도의 최대 크기는 8*8이고, 여기서 바이러스의 최대 개수 2를 빼면 62개의 빈자리가 있을 수 있다.
나머지가 모두 빈자리라고 가정했을 때 나올 수 있는 좌표 개수는 62*61*60 (n*n-1*n-2)개이다.
이는 약 23만개이므로 시간복잡도 2초 이내에 풀 수 있겠다고 판단하였다.
모든 경우의 수는 itertools의 combinations를 사용하여 순서와 상관없는 조합을 생성해주었다.
벽을 (0, 1) (1, 0) (3, 5)에 세우는 것과 (3, 5) (1, 0) (0, 1)에 세우는 것은 모두 동일하기 때문이다.
from itertools import combinations
from collections import deque
n, m = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(n)]
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
def bfs():
count = len(idx)
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 and not visited[nx][ny] and board[nx][ny] == 0:
count -= 1
visited[nx][ny] = 1
q.append((nx, ny))
return count-3
idx = []
virus = []
for i in range(n):
for j in range(m):
if board[i][j] == 0:
idx.append((i, j))
elif board[i][j] == 2:
virus.append((i, j))
combi = list(combinations(idx, 3))
answer = -1
for c in combi:
x1, y1 = c[0][0], c[0][1]
x2, y2 = c[1][0], c[1][1]
x3, y3 = c[2][0], c[2][1]
board[x1][y1] = 1
board[x2][y2] = 1
board[x3][y3] = 1
visited = [[0]*m for _ in range(n)]
for i in range(len(virus)):
visited[virus[i][0]][virus[i][1]] = 1
cnt = bfs()
board[x1][y1] = 0
board[x2][y2] = 0
board[x3][y3] = 0
if answer < cnt:
answer = cnt
print(answer)
풀이 중 유의해야할 점은 좌표에 벽을 세워 계산을 한 뒤, 벽을 다시 제거해줘야 한다는 것이었다.
그래야 다음번 벽좌표에 대해 계산할때 이전 벽좌표와 중복되지 않기 때문이다!
'코딩테스트' 카테고리의 다른 글
[Python] 백준 15686번 - 치킨 배달 (0) | 2023.07.17 |
---|---|
[Python] 백준 21608번 - 상어 초등학교 (0) | 2023.07.13 |
[Python] 백준 18870번 - 좌표 압축 (0) | 2023.07.11 |
[Python] 백준 1654번 - 랜선 자르기 (0) | 2023.07.03 |
[Python] 백준 5427번 - 불 (0) | 2023.06.29 |