[백준 10335] There is No Alternative
1. 문제 설명
2. 문제 분석
원본 MST를 형성하는 간선 집합과 MST 비용을 구한 뒤, 각 간선을 원본 그래프에서 제외한 뒤 다시 한번 MST를 구해보자. 만일 MST 값이 달라진다면 그 간선은 '대체 불가능한' 간선이다.
- 파이썬에서는 시간 단축을 위해 원본 그래프를
copy
로 긁어왔고, 이번 크루스칼 알고리즘에서는 heap
이 아니라 정렬한 값을 deque
로 주고 사용했다. 원래는 heap
을 원본 그래프에 사용한 뒤 복사하고, 제외할 간선을 remove
한 뒤 heappify
로 만들어주었는데, 이 과정이 다소 시간을 잡아먹었기 때문이다. 처음부터 정렬한 뒤 remove
해주면 다시 한 번 정렬할 필요가 없기 때문에 이번에는 deque
를 사용했다.
3. 나의 풀이
import sys
from collections import deque
def find(node):
if parents[node] == node: return node
else:
parents[node] = find(parents[node])
return parents[node]
def union(node1, node2):
root1, root2 = find(node1), find(node2)
if root1 == root2: return False
else:
parents[root2] = root1
return True
def Kruskal(MST_check=False):
if MST_check:
total = 0
edge_cnt = 0
edges = []
while pq2:
cost, node1, node2 = pq2.popleft()
if union(node1, node2):
total += cost
edge_cnt += 1
edges.append([cost, node1, node2])
if edge_cnt == n-1: break
if edge_cnt == n-1: return edges, total
else: return edges, -1
# MST 형성 간선 집합 및 MST 비용 리턴
else:
total = 0
edge_cnt = 0
while pq2:
cost, node1, node2 = pq2.popleft()
if union(node1, node2):
total += cost
edge_cnt += 1
if edge_cnt == n-1: break
if edge_cnt == n-1: return total
else: return -1
# 특정 간선을 제외했을 때의 MST 비용 리턴
n, m = map(int, sys.stdin.readline().rstrip().split())
pq = []
for _ in range(m):
a, b, c = map(int, sys.stdin.readline().rstrip().split())
pq.append([c, a, b])
pq.sort()
pq = deque(pq)
pq2 = pq.copy()
# 원본 pq를 계속해서 활용해야 하므로 copy
parents = [i for i in range(n+1)]
MST_edges, total = Kruskal(MST_check=True)
no_alternative_cnt = 0
no_alternative_cost = 0
for edge in MST_edges:
parents = [i for i in range(n+1)]
pq2 = pq.copy()
pq2.remove(edge)
# edge가 alternative하다면 이 edge를 원본 그래프에서 지우고 MST를 구해도 동일한 MST 비용이 나올 것이다.
total2 = Kruskal(MST_check=False)
if total != total2:
no_alternative_cnt += 1
no_alternative_cost += edge[0]
print(no_alternative_cnt, no_alternative_cost)
Author And Source
이 문제에 관하여([백준 10335] There is No Alternative), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@j_aion/백준-10335-There-is-No-Alternative
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
원본 MST를 형성하는 간선 집합과 MST 비용을 구한 뒤, 각 간선을 원본 그래프에서 제외한 뒤 다시 한번 MST를 구해보자. 만일 MST 값이 달라진다면 그 간선은 '대체 불가능한' 간선이다.
- 파이썬에서는 시간 단축을 위해 원본 그래프를
copy
로 긁어왔고, 이번 크루스칼 알고리즘에서는heap
이 아니라 정렬한 값을deque
로 주고 사용했다. 원래는heap
을 원본 그래프에 사용한 뒤 복사하고, 제외할 간선을remove
한 뒤heappify
로 만들어주었는데, 이 과정이 다소 시간을 잡아먹었기 때문이다. 처음부터 정렬한 뒤remove
해주면 다시 한 번 정렬할 필요가 없기 때문에 이번에는deque
를 사용했다.
3. 나의 풀이
import sys
from collections import deque
def find(node):
if parents[node] == node: return node
else:
parents[node] = find(parents[node])
return parents[node]
def union(node1, node2):
root1, root2 = find(node1), find(node2)
if root1 == root2: return False
else:
parents[root2] = root1
return True
def Kruskal(MST_check=False):
if MST_check:
total = 0
edge_cnt = 0
edges = []
while pq2:
cost, node1, node2 = pq2.popleft()
if union(node1, node2):
total += cost
edge_cnt += 1
edges.append([cost, node1, node2])
if edge_cnt == n-1: break
if edge_cnt == n-1: return edges, total
else: return edges, -1
# MST 형성 간선 집합 및 MST 비용 리턴
else:
total = 0
edge_cnt = 0
while pq2:
cost, node1, node2 = pq2.popleft()
if union(node1, node2):
total += cost
edge_cnt += 1
if edge_cnt == n-1: break
if edge_cnt == n-1: return total
else: return -1
# 특정 간선을 제외했을 때의 MST 비용 리턴
n, m = map(int, sys.stdin.readline().rstrip().split())
pq = []
for _ in range(m):
a, b, c = map(int, sys.stdin.readline().rstrip().split())
pq.append([c, a, b])
pq.sort()
pq = deque(pq)
pq2 = pq.copy()
# 원본 pq를 계속해서 활용해야 하므로 copy
parents = [i for i in range(n+1)]
MST_edges, total = Kruskal(MST_check=True)
no_alternative_cnt = 0
no_alternative_cost = 0
for edge in MST_edges:
parents = [i for i in range(n+1)]
pq2 = pq.copy()
pq2.remove(edge)
# edge가 alternative하다면 이 edge를 원본 그래프에서 지우고 MST를 구해도 동일한 MST 비용이 나올 것이다.
total2 = Kruskal(MST_check=False)
if total != total2:
no_alternative_cnt += 1
no_alternative_cost += edge[0]
print(no_alternative_cnt, no_alternative_cost)
Author And Source
이 문제에 관하여([백준 10335] There is No Alternative), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@j_aion/백준-10335-There-is-No-Alternative
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
import sys
from collections import deque
def find(node):
if parents[node] == node: return node
else:
parents[node] = find(parents[node])
return parents[node]
def union(node1, node2):
root1, root2 = find(node1), find(node2)
if root1 == root2: return False
else:
parents[root2] = root1
return True
def Kruskal(MST_check=False):
if MST_check:
total = 0
edge_cnt = 0
edges = []
while pq2:
cost, node1, node2 = pq2.popleft()
if union(node1, node2):
total += cost
edge_cnt += 1
edges.append([cost, node1, node2])
if edge_cnt == n-1: break
if edge_cnt == n-1: return edges, total
else: return edges, -1
# MST 형성 간선 집합 및 MST 비용 리턴
else:
total = 0
edge_cnt = 0
while pq2:
cost, node1, node2 = pq2.popleft()
if union(node1, node2):
total += cost
edge_cnt += 1
if edge_cnt == n-1: break
if edge_cnt == n-1: return total
else: return -1
# 특정 간선을 제외했을 때의 MST 비용 리턴
n, m = map(int, sys.stdin.readline().rstrip().split())
pq = []
for _ in range(m):
a, b, c = map(int, sys.stdin.readline().rstrip().split())
pq.append([c, a, b])
pq.sort()
pq = deque(pq)
pq2 = pq.copy()
# 원본 pq를 계속해서 활용해야 하므로 copy
parents = [i for i in range(n+1)]
MST_edges, total = Kruskal(MST_check=True)
no_alternative_cnt = 0
no_alternative_cost = 0
for edge in MST_edges:
parents = [i for i in range(n+1)]
pq2 = pq.copy()
pq2.remove(edge)
# edge가 alternative하다면 이 edge를 원본 그래프에서 지우고 MST를 구해도 동일한 MST 비용이 나올 것이다.
total2 = Kruskal(MST_check=False)
if total != total2:
no_alternative_cnt += 1
no_alternative_cost += edge[0]
print(no_alternative_cnt, no_alternative_cost)
Author And Source
이 문제에 관하여([백준 10335] There is No Alternative), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@j_aion/백준-10335-There-is-No-Alternative저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)