파이썬 변수할당(call by reference) - 플로이드 워셜(Floyd-warshall) 최종본
파이썬 변수할당(call by reference) - 플로이드 워셜(Floyd-warshall) 최종본 — #플로이드워셜 #floydwarshall #파이썬알고리즘 #파이썬변수 #callbyreference #개발자의도구들 AI스쿨 m...
#플로이드워셜 #floydwarshall #파이썬알고리즘 #파이썬변수 #callbyreference #개발자의도구들
AI스쿨 msa기반 java 백엔드 코스 중에 공부한 내용을 작성하였습니다
\* 하루 1코테 도전중에 있습니다. 어떤건지 궁굼하신 분들은 여기를 눌려주세요.
파이썬의 변수할당
| import sys, heapq# 무 방향 가중치 그래프class Graph: def \_\_init\_\_(self): self.graph = {} self.node = \[\] def add\_node(self, node): self.node.append(node) def add\_edge(self, u, v, w): if u not in self.graph: self.graph\[u\] = {} if v not in self.graph: self.graph\[v\] = {} self.graph\[u\]\[v\] = w self.graph\[v\]\[u\] = wdef floyd\_warshall(graph): distance\_map = {} for vertext in graph.graph: node\_map = graph.graph\[vertext\] node\_map\[vertext\] = 0 for node in graph.node: if node not in node\_map: node\_map\[node\] = float("INF") distance\_map\[vertext\] = node\_map return distance\_mapgraph = Graph()n = int(sys.stdin.readline().rstrip())m = int(sys.stdin.readline().rstrip())for i in range(1, n + 1): graph.add\_node(i)for \_ in range(m): a, b, c = map(int, sys.stdin.readline().rstrip().split()) graph.add\_edge(a, b, c)print(graph.graph)print(floyd\_warshall(graph)) |
|---|
이전글에서 floyd\_warshall내에서 모든 정점에 대한 거리에 대한 정보를 dictionary형태로 구현하고자 해당 코드를 사용하였습니다. 해당 코드로 문제를 풀어보니 동작하지 않아, 어디가 문제인지 찾고 치명적인 실수를 했다는 것을 깨닫게 되었습니다.
여러분들은 찾으셨나요?
문제원인
| def floyd\_warshall(graph): distance\_map = {} for vertext in graph.graph: node\_map = graph.graph\[vertext\] node\_map\[vertext\] = 0 for node in graph.node: if node not in node\_map: node\_map\[node\] = float("INF") distance\_map\[vertext\] = node\_map return distance\_map |
|---|
우선적으로 나타날 수 있는 문제는 node\_map에 변수를 초기화할 때 입니다. 파이썬에서는 변수를 할당할 때 변수의 복사본을 할당하는 것이 아닌, 실제 변수가 들어있는 주소를 할당(call by reference)합니다.
변수는 메모리상에 특정한 곳에 저장되는데 이는 OS에 의해 주소로 관리됩니다. 제가 원했던건 해당 메모리의 값을 복사해서 그 값만 전달하기를 원했으나, 실제로는 메모리에 있는 dictionary 객체 자체가 node\_map으로 전달된 것이나 다름이 없게되는 것이지요.
--> 찾고보니 파이썬은 자료 형태에 따라 call by value로 할당하는 경우도 있습니다. 예전에 공부한건데 까먹고 있었네요 ㅠㅠ.파이썬 call by value vs call by reference
그러니 node\_map을 초기화하면 실제 graph.graph\[vertext\]부분이 변경됩니다.
node\_map의 현재 node만 0으로 넣으려 했는데 찍어보니 grap.graph\[현재노드\]도 들어간걸 볼 수 있습니다. 그럼 distance\_map도 graph.graph\[vertext\]를 가리키게 되겠군요.
| for central\_node in range(1, len(graph.node) + 1): central\_node\_map = distance\_map\[central\_node\] for each\_node in graph.node: dist\_map = distance\_map\[each\_node\] for neighbor in dist\_map: if dist\_map\[neighbor\] > dist\_map\[central\_node\] + central\_node\_map\[neighbor\]: dist\_map\[neighbor\] = dist\_map\[central\_node\] + central\_node\_map\[neighbor\] |
|---|
그럼 길을 탐색하는 알고리즘에서도 같은 문제가 발생할 수 있겠습니다. central\_node\_map이 distance\_map을 참조하고 있으닌깐요!
최종 구현
| def floyd\_warshall(graph): # 노드 리스트 초기화 nodes = graph.node # 거리 맵 초기화 distance\_map = {i: {j: float('inf') for j in nodes} for i in nodes} # 자기 자신으로의 거리는 0 for node in nodes: distance\_map\[node\]\[node\] = 0 # 간선의 가중치를 거리 맵에 반영 for u in graph.graph: for v, w in graph.graph\[u\].items(): distance\_map\[u\]\[v\] = w # 플로이드-워셜 알고리즘 for k in nodes: for i in nodes: for j in nodes: if distance\_map\[i\]\[j\] > distance\_map\[i\]\[k\] + distance\_map\[k\]\[j\]: distance\_map\[i\]\[j\] = distance\_map\[i\]\[k\] + distance\_map\[k\]\[j\] return distance\_map |
|---|
GPT의 도음을 받아 작성된 최종 코드입니다. distance\_map을 새로운 딕셔너리로 만든 후 계속 초기화 해주고 return하는 방식입니다. 그 외에 작동원리는 동일합니다.
파이썬의 call by reference라는 개념을 이번에 제대로 익히는 시간이 되었습니다.