(전공복습) 데이터과학 4. 시각화
차례
백준(BOJ) 24339 가희와 쓰레기 놀이 파이썬(Python)
그래프에 대한 정보를 저장하고 불러오는 문제.
우선, 노드 번호가 \(10^9\)까지 가능하지만 실제 생성 가능한 노드의 수는 최대 \(4 \times 10^5\)개이므로 딕셔너리와 같은 해시 자료구조를 사용해야 한다.
이후에는 하나씩 구현하면 되는데, 우선 연결이 두 종류가 있고, 노드의 원활한 삭제를 위해 진입, 진출 간선 모두를 확인해야 하고, 추가로 간선 ID로도 간선을 룩업할 수 있어야 하므로 총 \(2\times 2 + 1 = 5\)개의 간선 딕셔너리가 필요하다.
M 또는 m 연산을 할 때는 그래프 탐색(BFS 또는 DFS)으로 루트에서부터 가능한 노드들을 방문한 이후 방문하지 않은 노드들을 제거하면 된다.
이때, 노드에 연결된 진입, 진출 간선들 역시 삭제해야 한다.
MADE 연산을 할 때는 그냥 노드를 추가하고 간선 목록 집합을 초기화하면 된다.
ADD 연산을 할 때는 해당하는 연결을 나타내는 간선 목록에 간선을 추가하고 전체 간선 목록에도 추가하면 된다.
REMOVE 연산을 할 때는 해당하는 ID의 간선을 각각의 목록에서 삭제하면 된다.
파이썬이야 딕셔너리가 구현되어 있으니 크게 어렵지는 않고, 노드나 간선 삭제할 때 꼬이지 않도록 조심만 하면 쉽게 구현할 수 있다.
#!python
from sys import stdin
input = stdin.readline
# root 여부를 확인하고 id를 가진 노드를 추가하는 함수
# 노드의 진입, 진출 간선 집합을 초기화하고 루트면 루트 집합에 넣는다
def add_node(id, root):
strong[id] = set()
weak[id] = set()
strong_back[id] = set()
weak_back[id] = set()
if root == 'ROOT':
roots.add(id)
# id가 edge이면서 src에서 dst로 가는 간선을 추가하는 함수
# 약한 연결인지 강한 연결인지 판단하고 진입, 진출 간선 목록에 추가한다
def add_edge(edge, src, type, dst):
if type == '->':
graph = weak
graph_back = weak_back
else:
graph = strong
graph_back = strong_back
edges[edge] = (src, dst)
graph[src].add(edge)
graph_back[dst].add(edge)
# 모든 루트에서 출발하여 dfs로 그래프를 순회하는 함수
# flag가 True면 두 종류의 연결을 모두 고려하고 False면 강한 연결만 고려한다
# 이후, 방문하지 않은 모든 노드를 삭제하고 남은 노드 수를 출력한다
def dfs(flag):
q = list(roots)
visited = dict(zip(strong, [False] * len(strong)))
while q:
node = q.pop()
if visited[node]:
continue
visited[node] = True
for succ in strong[node]:
q.append(edges[succ][1])
if not flag:
continue
for succ in weak[node]:
q.append(edges[succ][1])
for node, not_del in visited.items():
if not_del:
continue
remove_node(node)
return len(strong)
# id에 따라 노드를 삭제하는 함수로, dfs에서만 호출된다
# 약한, 강한 연결의 진입, 진출 간선을 삭제하고 이후에 남은 집합도 삭제한다
def remove_node(id):
for prev in strong_back[id]:
strong[edges[prev][0]].discard(prev)
del edges[prev]
for prev in weak_back[id]:
weak[edges[prev][0]].discard(prev)
del edges[prev]
for succ in strong[id]:
strong_back[edges[succ][1]].discard(succ)
del edges[succ]
for succ in weak[id]:
weak_back[edges[succ][1]].discard(succ)
del edges[succ]
del strong[id]
del weak[id]
del strong_back[id]
del weak_back[id]
# id에 따라 간선을 삭제하는 함수
# 엣지 목록 딕셔너리, 진입, 진출 간선 집합에서 모두 삭제한다
def remove_edge(id):
src, dst = edges.pop(id)
strong[src].discard(id)
weak[src].discard(id)
strong_back[dst].discard(id)
weak_back[dst].discard(id)
# 약한, 강한 연결, 진입, 진출 간선에 따라 총 4가지 경우의 간선이 있다
# 예를 들어 strong[id]는 고유번호가 id인 노드에서 출발하는 간선들의 id를 저장한다
# (목적지가 저장된 게 아니라 간선의 id가 저장되어 있음에 유의하라)
# 루트인 노드를 따로 보관한다
# edge[id]는 고유번호가 id인 엣지의 출발 노드와 도착 노드를 튜플로 저장한다
o, e = map(int, input().split())
strong = {}
weak = {}
strong_back = {}
weak_back = {}
roots = set()
edges = {}
# 이미 만들어져 있는 노드들을 생성한다
for _ in range(o):
id, root = input().split()
add_node(id, root)
# 쿼리를 처리한다
for _ in range(e):
q, *args = input().split()
if q == 'M':
print(dfs(False))
elif q == 'm':
print(dfs(True))
elif q == 'MADE':
add_node(*args)
elif q == 'ADD':
add_edge(*args)
else:
remove_edge(*args)
2024
맨 위로 이동 ↑2023
백준(BOJ) 2045 마방진 / 3192 매직 스퀘어 파이썬(Python)
문제 링크 문제 링크
세그먼트 트리
개요 선형적인 자료구조에서는 값에 접근하는 데에 \(O(1)\)이면 충분하지만, 대신 부분합을 구하는 데에는 \(O(N)\)이 필요하다. 그렇다면 이 자료구조를 이진 트리로 구성하면 어떨까? 값에 접근하는 데에 걸리는 시간이 \(O(\lg N)\)으로 늘어나지만 대신 부분합을 구하...
벨만-포드 알고리즘
개요 다익스트라 알고리즘과 함께 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 다익스트라 알고리즘보다 느리지만, 음수 가중치 간선이 있어도 작동하며, 음수 가중치 사...
다익스트라 알고리즘
개요 다익스트라 알고리즘은 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘 중 하나이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 단, 다익스트라 알고리즘은 음수 가중치 엣지를 허용하지 않는다. 이 경우에는 벨만-...