from itertools import combinations
from collections import deque
def bfs(mp, target, info, visited):
dx, dy = [1, -1, 0, 0], [0, 0, 1, -1]
result, ones = 0, N*M - len(zeros) - len(twos)
for r, c in target:
mp[r][c] = 1
q = deque()
for r, c in info:
q.append([r, c])
result += 1
while q:
cur = q.popleft()
r, c = cur[0], cur[1]
visited[r][c] = True
for xx, yy in zip(dx, dy):
nx, ny = r + xx, c + yy
if 0 <= nx < N and 0 <= ny < M:
if not visited[nx][ny] and mp[nx][ny] == 0:
q.append([nx, ny])
visited[nx][ny] = True
result += 1
for r, c in target:
mp[r][c] = 0
return N*M - (result + ones + 3)
if __name__ == '__main__':
N, M = map(int, input().split())
maps = [list(map(int, input().split())) for i in range(N)]
zeros, twos = [], []
maxAns = 0
# BFS + 백트래킹
for row, items in enumerate(maps):
for col, item in enumerate(items):
if item == 0:
zeros.append([row, col])
elif item == 2:
twos.append([row, col])
for item in combinations(zeros, 3):
visit = [[False for i in range(M)] for j in range(N)]
maxAns = max(maxAns, bfs(maps, item, twos, visit))
print(maxAns)BFS 응용에 관한 간단한 문제였다. 처음엔 시간 초과가 약간 염려되긴 했지만 맵 최대 크기가 8*8 이여서 괜찮다고 판단했다.
여기서 한 가지 새로 안 사실은 파이썬에서 리스트를 메서드 파라미터로 넘겨서 메서드 안에서 바꿔도 그대로 반영 된다는 점이다. 즉, Passed by reference로 넘어간다는 것이다.
난 당연하게 메서드 파라미터로 넘긴 변수는 shallow copy가 되는 줄 알았다. 그런데 특이하게 파이썬에서는 Immutable object와 Mutable object를 다르게 생각해야 한다.
Immutable object 같은 String, int 자료형은 메서드 안에서 바꿀 수 없다. 왜냐하면 global, local 같은 scope 개념이 있기 때문이다.
그러나 Mutable object인 List, Dictionary 같은 경우는 그대로 레퍼런스 카피가 넘어가고 변경이 실제로 일어난다.
파이썬으로 알고리즘을 푼지 오래되지 않았고, 메서드를 여러 개로 분리해서 디버깅할 때마다 애를 먹었던 부분이 바로 이 점을 몰라서 였던 것 같다.
꼭 알아두어야 겠다.
ChatGPT 의 설명
This can be a bit confusing because the behavior depends on the type of the object being passed.
Immutable objects (like strings, integers, and tuples) are passed by object reference but cannot be modified inside the function.
Mutable objects (like lists, sets, and dictionaries) can be modified inside the function, and any changes made to the object will persist outside the function.
