BFS, 백트래킹 문제이다. 거창한 백트래킹.. 이라기 보다, 그냥 모든 경우의 수를 찾기 위한 부분에서 백트래킹이 사용되었다. BFS가 메인이고 백트래킹은 거드는 느낌의 문제이다.
# BFS, 백트래킹
# 백트래킹으로 벽 3개를 세우는 경우의 수를 전부 구한 후, BFS로 바이러스를 전파시킨 후 안전 영역의 개수를 센다
from collections import deque
import sys
import copy
input= sys.stdin.readline
N, M =map(int, input().split()) # 행, 열
graph = [] # 지도
for _ inrange(N):
graph.append(list(map(int, input().split())))
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# 3개의 벽을 세우는 경우의 수를 구하는 함수
defcreateWall(wall):
if wall ==3: # 벽 3개가 세워졌다면 안전영역 개수 센다
BFS()
return
for i inrange(N):
for j inrange(M):
if graph[i][j] ==0: # 안전 영역일 경우 벽을 세운다
graph[i][j] =1
createWall(wall +1) # 벽 개수 1개 추가하고 탐색
graph[i][j] =0# 갔다 왔으니 다시 벽 허물어 준다
result =0# 결과 담을 변수
# BFS로 바이러스를 퍼트린 후 안전 영역 개수를 세는 함수
defBFS():
global result
trashGraph = copy.deepcopy(graph)
queue = deque()
for i inrange(N):
for j inrange(M):
if trashGraph[i][j] ==2: # 바이러스일 경우 큐에 추가
queue.append([i, j])
while queue:
x, y = queue.popleft()
# 상하좌우 퍼뜨리기
for i inrange(4):
nx = x + dx[i]
ny = y + dy[i]
# 좌표가 지도 안에 있고 안전 영역일 경우 퍼뜨린다
if0<= nx < N and0<= ny < M and trashGraph[nx][ny] ==0:
trashGraph[nx][ny] =2
queue.append([nx, ny])
# 다 퍼뜨렸으면 안전영역 개수 센다
cnt =0
for g in trashGraph:
cnt += g.count(0)
# 더 큰 값을 결과값으로 갱신한다
result =max(result, cnt)
createWall(0)
print(result)
첫번째 통과 코드이다. pypy3으로 제출할 때만 통과한다.
문제를 어떻게 풀지 고민해 봤는데, 아무리 생각해도 벽 3개를 놓는 경우의 수를 모두 체크하는 방법밖에 없다고 생각되었다. 하지만 분명히 더 효율적인 방법이 있지만 내가 못 알아내는 거라고 생각해서, 너무 답답한 마음에 정답 코드를 참고했는데, 그렇게 푼 사람은 거의 없었다. 그냥 백트래킹으로 모든 경우의 수를 다 찾아도 풀리는 것이었다... 내 생각대로 먼저 풀어볼 걸 그랬다.
항상 너무 완벽하게 풀려는 마음에 조금만 내 생각이 불완전한 것 같다면 코드를 짜기가 싫어져 버린다. 이런 마음을 버리고 그냥 코드를 짜봐도 될 텐데. 고쳐야 할 부분이다.
python3으론 통과가 안되고 pypy3으로만 통과가 되는데 메모리와 시간을 꽤 많이 먹어서 이걸 어떻게 개선할 수 있을까 고민하다가, BFS함수에서 바이러스의 위치를 찾는 반복문이 중복된다는 걸 깨달았다.
# BFS, 백트래킹
# 백트래킹으로 벽 3개를 세우는 경우의 수를 전부 구한 후, BFS로 바이러스를 전파시킨 후 안전 영역의 개수를 센다
from collections import deque
import sys
import copy
input= sys.stdin.readline
N, M =map(int, input().split()) # 행, 열
graph = [] # 지도 입력받기
for _ inrange(N):
graph.append(list(map(int, input().split())))
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# 바이러스 위치 미리 찾아놓기
virus = []
for i inrange(N):
for j inrange(M):
if graph[i][j] ==2:
virus.append([i, j])
# 백트래킹으로 벽 3개를 세우는 모든 경우의 수를 구하는 함수
defcreateWall(wall):
if wall ==3: # 벽 3개를 세웠으면 BFS 함수 실행
BFS()
return
for i inrange(N):
for j inrange(M):
if graph[i][j] ==0: # 안전 영역에 한해 벽을 세운다
graph[i][j] =1
createWall(wall +1) # 세웠으면 다음 벽을 세우러 간다
graph[i][j] =0# 돌아왔으면 벽을 허문다. 다른 경우의 수를 찾는다
result =0# 최종 결과 저장할 변수
# BFS로 바이러스를 퍼뜨리고 안전 영역의 개수를 세는 함수
defBFS():
global result
trashGraph = copy.deepcopy(graph)
# 미리 찾아놓은 바이러스 위치를 큐에 넣는다
queue = deque()
for v in virus:
queue.append(v)
# 큐가 빌 때까지 실행한다
while queue:
x, y = queue.popleft()
# 상하좌우로 바이러스 퍼뜨리기
for i inrange(4):
nx = x + dx[i]
ny = y + dy[i]
# 좌표가 지도 안에 있고 안전 영역일 경우 퍼뜨린다
if0<= nx < N and0<= ny < M and trashGraph[nx][ny] ==0:
trashGraph[nx][ny] =2
queue.append([nx, ny])
# 안전 영역의 개수를 세고 더 큰 값을 result로 갱신한다
cnt =0
for g in trashGraph:
cnt += g.count(0)
result =max(result, cnt)
createWall(0)
print(result)
개선한 코드이다. 벽의 위치만 바뀔 뿐 바이러스의 시작 위치는 계속해서 동일하므로, 처음에 위치를 미리 구해두고 BFS 함수에서 그것을 사용했다. 근데 드라마틱한 효율 개선은 일어나지 않았다. 해봤자 100ms ~ 200ms 줄어드는 정도? 메모리는 거의 비슷했고.
바이러스의 시작 위치를 찾는 부분보다, 벽 3개 경우의 수를 찾는 부분의 영향력이 크게 높아서 그런 듯 하다. 근데 내 생각으로는 경우의 수 찾는 부분을 어떻게 개선해야 할 지 잘 모르겠다. 어쨌든 조금이라도 시간을 줄이긴 했다.
참고로 초기 바이러스 위치를 deepcopy로 복사해 봤는데, 오히려 시간이 증가했었다. 직접 반복문으로 담는 게 더 효율적인 듯 하다. deepcopy는 객체를 하나 더 만들기 때문에 비효율적인 것 같다. 어차피 바이러스 개수는 해봐야 10개가 최대이기도 하고. 여기에 굳이 deepcopy를 쓸 필요는 없을 것 같다.
