문제 바로가기
문제:
한 회사는 본사와 지사의 컴퓨터들을 연결하는 네트워크 시설을 보유하고 있다. 각 지사에는 네트워크용 컴퓨터가 한 대씩 있으며, 이들은 본사의 메인 컴퓨터와 직접 연결되어 있다. 몇몇 지사들끼리 연결되어 있는 경우도 있다. 네트워크 시설에서는 두 컴퓨터가 직접 연결되어 있지 않더라도 다른 컴퓨터들을 경유하여 연결될 수 있다. 예를 들어 1, 2번 컴퓨터가 직접 연결되어 있고, 1, 3번 컴퓨터가 직접 연결되어 있다면, 이것은 2, 3번 컴퓨터가 연결되어 있는 효과도 발휘한다는 것이다. 회사 측에서는 네트워크에 고장이 발생하더라도 컴퓨터들이 연결되어 있도록 안정적인 네트워크를 구축하고자 한다. 네트워크에 고장이 발생하는 경우는 두 가지가 있다. 첫 번째는 직접 연결되어 있는 두 컴퓨터의 연결이 끊어지는 경우이다. 회사 측은 이런 경우에도 이 두 컴퓨터가 다른 컴퓨터들을 경유하여 연결되어 있기를 원한다. 두 번째는 컴퓨터가 고장 나는 경우이다. 회사 측은 이런 경우에는 고장 나지 않은 컴퓨터들끼리 연결되어 있기를 원한다. 예제로 주어진 입력에서 1, 2번 컴퓨터의 연결이 끊어지더라도, 이 두 컴퓨터는 3번 컴퓨터를 통해서 연결되게 된다. 하지만 1번 컴퓨터가 고장 나는 경우에는 5번 컴퓨터가 다른 컴퓨터들과 연결되어 있지 못하게 된다. 따라서 5번 컴퓨터를 다른 컴퓨터와 직접 연결해 주어야 한다. 두 컴퓨터를 연결하는 데 소요되는 비용은 일정하지 않다. 당신은 네트워크의 연결 상태를 입력받아 이 네트워크가 안정적인 네트워크인지 판별하고, 만약 아닐 경우에는 최소 비용으로 회사의 네트워크가 안정적이 되도록 하여야 한다.
입력:
첫째 줄에 두 정수 n(1 ≤ n ≤ 1,000), m(0 ≤ m ≤ 10,000)이 주어진다. n은 컴퓨터의 개수이며, m은 연결되어 있는 지사 컴퓨터들의 쌍의 개수이다. 다음 m개의 줄에는 두 정수 x, y가 주어진다. 이는 서로 다른 두 컴퓨터, x번 컴퓨터와 y번 컴퓨터가 직접 연결되어 있음을 의미한다. 다음 n개의 줄에는 인접 행렬의 형태로 두 컴퓨터를 연결할 때 드는 비용이 주어진다. 이 값은 1 이상 30,000이하의 정수이며, i번 컴퓨터와 j번 컴퓨터를 연결할 때 드는 비용은 j번 컴퓨터와 i번 컴퓨터를 연결할 때 드는 비용과 같다. 본사의 컴퓨터는 항상 1번 컴퓨터이다.
출력:
첫째 줄에 최소 비용 X와 연결할 컴퓨터들의 쌍의 개수 K를 출력한다. 다음 K개의 줄에는 두 정수로 연결할 컴퓨터들의 번호를 출력한다. 만약 주어진 입력이 안정적인 네트워크라면 X=0이고 K=0이 된다.
풀이:
처음에 문제를 읽을때는 잘 이해가 되지 않았다. 왜 1번은 연결은 안하는거지,,?
4-5 만 연결하면 된다고?? 라고 생각했지만 계속 문제를 보니
이들은 본사의 메인 컴퓨터와 직접 연결되어 있다
라는 문장이 있었다. 즉 1번 컴퓨터는 제외하고 나머지 애들 크루스칼 알고리즘을 사용하면 된다.
프림보다 크루스칼 을 사용한 이유는 간선 중심으로 하기 때문이다. 간선이 너무 많으면 프림 알고리즘을 사용하면 된다.
import sys
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
n, m = map(int,input().split())
def find(x):
if x != parent[x]:
parent[x] = find(parent[x])
return parent[x]
def union(left, right):
left = find(left)
right = find(right)
if left < right:
parent[right] = left
else:
parent[left] = right
parent = [i for i in range(n+1)]
count = 0
for _ in range(m):
a,b = map(int,input().split())
if find(a) != find(b):
union(a,b)
count += 1
if count == n-2 :
print(0,0)
exit()
board = [list(map(int, input().split())) for _ in range(n)]
edges = []
# 1번은 모든 컴퓨터와 연결 되어 있으므로 패스, 양방향이므로 체크 해줌
for i in range(1, n - 1):
for j in range(i + 1, n):
edges.append((i + 1, j + 1, board[i][j]))
edges.sort(key = lambda x:x[2])
mst = 0 # 비용
connect_mst = [] # 연결한 mst
for u, v, e in edges:
# 부모가 다르면 연결이 안된 상태
if find(u) != find(v):
union(u,v)
count += 1
mst += e
connect_mst.append((u,v))
if count == n - 2: # 안정적인 네트워크가 되었다면
print(mst, len(connect_mst)) # 답 출력 후, 중지
for u, v in connect_mst:
print(u, v)
break
자세 설명
def find(x):
if x != parent[x]:
parent[x] = find(parent[x])
return parent[x]
find 함수 부모님 함수를 찾는 것이다. 처음의 각 수의 부모는 자기 자신이다.
def union(left, right):
left = find(left)
right = find(right)
if left < right:
parent[right] = left
else:
parent[left] = right
parent = [i for i in range(n+1)]union 합치는 함수
find 로 부모를 찾아 온 후 작은 숫자가 부모가 된다.
만약 left 1 right 5 일 경우
parent[5] = 1 이 된다. 작은 숫자가 부모 이며 연결 됨
count = 0
for _ in range(m):
a,b = map(int,input().split())
if find(a) != find(b):
union(a,b)
count += 1
if count == n-2 :
print(0,0)
exit()
count 는 총 연결 된 갯수 정점이 5개 일때 1은 다 연결되서 빠지고 -1개 해준 >> n-2와 비교를 해주기 위해
만약 여기서 다 연결이 돼 (count == n-2 ) 안정적인 네트워크라면 0,0 을 출력
그렇지 않을 경우
board = [list(map(int, input().split())) for _ in range(n)]
edges = []
# 1번은 모든 컴퓨터와 연결 되어 있으므로 패스, 양방향이므로 체크 해줌
for i in range(1, n - 1):
for j in range(i + 1, n):
edges.append((i + 1, j + 1, board[i][j]))
edges.sort(key = lambda x:x[2])
mst = 0 # 비용
connect_mst = [] # 연결한 mst
for u, v, e in edges:
# 부모가 다르면 연결이 안된 상태
if find(u) != find(v):
union(u,v)
count += 1
mst += e
connect_mst.append((u,v))
if count == n - 2: # 안정적인 네트워크가 되었다면
print(mst, len(connect_mst)) # 답 출력 후, 중지
for u, v in connect_mst:
print(u, v)
break
for i in range(1, n - 1):
for j in range(i + 1, n):
edges.append((i + 1, j + 1, board[i][j]))1번 컴퓨터는 다 연결되어있기때문에 2번 컴퓨터 부터 하고, 양방향으로 중복되어 들어가지 않기 위해 다음과 같이 써주었다.
간선 중심이므로 간선으로 오름차순해주고, 크러스컬 알고리즘 실행해주면 된다.
댓글