Coding 공부

import sys
import heapq

def input():
    return sys.stdin.readline().rstrip()


N = int(input())

graph = [list(map(int,input().split())) for _ in range(N)]

node_list = []

INF = float('inf')
distance_list = [INF for _ in range(N)]
visited = [False for _ in range(N)]
heapq.heappush(node_list,(0,0))
distance_list[0] = 0
result = 0
while node_list:
    cur_dis,cur_node = heapq.heappop(node_list)
    if visited[cur_node]:continue
    if cur_dis > distance_list[cur_node]:continue
    result += cur_dis
    visited[cur_node] = True
    for next_node in range(N):
        if next_node == cur_node:continue
        if visited[next_node]:continue
        if distance_list[next_node] > graph[cur_node][next_node]:
            distance_list[next_node] = graph[cur_node][next_node]
            heapq.heappush(node_list,(distance_list[next_node],next_node))

print(result)

 프림 알고리즘

import sys

def input():
    return sys.stdin.readline().rstrip()

def find_parents(X):
    if X == make_set[X]:
        return X
    make_set[X] = find_parents(make_set[X])
    return make_set[X]


def union(x,y):
    X = find_parents(x)
    Y = find_parents(y)

    if X !=Y:
        if ranks[X]< ranks[Y]:
            X,Y = Y,X
        make_set[Y] = X
        if ranks[X] == ranks[Y]:
            ranks[X] += 1
        return True
    return False



N = int(input())
edge_list = []
for x in range(N):
    temp = list(map(int,input().split()))
    for y in range(N):
        if x == y:continue
        edge_list.append((temp[y],x,y))


edge_list.sort(reverse=True)

cnt = 1
make_set = [i for i in range(N)]
ranks = [1 for _ in range(N)]
result = 0
while cnt <N:
    dis,node_a,node_b = edge_list.pop()
    if union(node_a,node_b):
        cnt += 1
        result += dis

print(result)

크루스칼 알고리즘

전형적인 MST 문제이다. MST 문제를 푸는 방식대로 풀면 된다.

import sys
import heapq
def convert_Numner(x):
    global total_sum,INF
    if x.islower():
        num = ord(x) - ord('a') + 1
        total_sum += num
    elif x.isupper():
        num = ord(x) - ord('A')+ 27
        total_sum += num
    else:
        num = INF
        total_sum += 0
    return num


def input():
    return sys.stdin.readline().rstrip()


N = int(input())


total_sum = 0
INF = float('inf')
arr = [list(map(convert_Numner,list(input()))) for _ in range(N)]


cnt = 0
mst_dis = 0
distance_list = [INF for _ in range(N)]
visited = [False for _ in range(N)]
node_list = []

heapq.heappush(node_list,(0,0))
distance_list[0] = 0
while node_list:
    cur_dis,cur_node = heapq.heappop(node_list)
    if visited[cur_node]:continue
    cnt += 1
    mst_dis += cur_dis
    visited[cur_node] = True
    for next_node in range(N):
        if visited[next_node]:continue
        min_value = min(arr[cur_node][next_node],arr[next_node][cur_node])
        if distance_list[next_node] > min_value:
            distance_list[next_node] = min_value
            heapq.heappush(node_list,(min_value,next_node))

if cnt == N:
    print(total_sum-mst_dis)
else:
    print(-1)

처음에 프림알고리즘으로 풀었다. MST에서 익숙한 알고리즘이 프림알고리즘이라, 우선적으로 푼 방식이다.

여기서 여러번 틀렸었는데 그 이유는 다음과 같다. 우리가 연결을 하는 통로는 무방향이다.

즉 1번방에서 2번방으로 연결하는 랜선과 2번방에서 1번방으로 연결하는 랜선은 둘중 하나만 선택을 하면, 둘이 연결이 된것으로 본다.

이 문제를 풀때 무조건 0번방부터 시작을 했기때문에

3

zzz

abc

abc

와 같은 입력이 들어왔을때, 오히려 더 짧은 반대편방에서 오는 경우를 체크하지 못했다.

이러한 문제점을 해결하기 위해, 거리를 비교할때, 양방향의 최소값으로 비교를 하고, 그값을 넣어주는 방식으로 했다.

이런식이 아니라, 처음부터 graph라는 딕셔너리를 만들어서 최소값을 저장해주어도 된다.

이 점만 주의하면, 나머지는 일반적인 프림알고리즘을 이용한 MST 문제이다.

cnt개수가 N보다 부족할시에는 모든 노드들이 연결이 된것이 아니므로, -1을 출력해주면 된다.

import sys
def convert_Numner(x):
    global total_sum,INF
    if x.islower():
        num = ord(x) - ord('a') + 1
        total_sum += num
    elif x.isupper():
        num = ord(x) - ord('A')+ 27
        total_sum += num
    else:
        num = INF
        total_sum += 0
    return num


def find_parents(X):
    if X == make_set[X]:
        return X
    make_set[X] = find_parents(make_set[X])
    return make_set[X]


def union(x,y):
    X = find_parents(x)
    Y = find_parents(y)

    if X !=Y:
        if ranks[X]< ranks[Y]:
            X,Y = Y,X
        make_set[Y] = X
        if ranks[X] == ranks[Y]:
            ranks[X] += 1
        return True
    return False

def input():
    return sys.stdin.readline().rstrip()

N = int(input())


total_sum = 0
INF = float('inf')


edge_list = []
for x in range(N):
    input_string = input()
    temp = []
    for y in range(N):
        num = convert_Numner(input_string[y])
        if x == y:continue
        if num == INF:continue
        edge_list.append((num,x,y))
edge_list.sort(reverse=True)
cnt = 1
result = 0
make_set = [i for i in range(N)]
ranks = [1 for _ in range(N)]
while cnt <N and edge_list:
    pay,node_a,node_b = edge_list.pop()
    if union(node_a,node_b):
        cnt += 1
        result += pay


if cnt == N:
    print(total_sum-result)
else:
    print(-1)

크루스칼을 이용한 풀이이다. 푸는 방법은 위와 동일하다 대신 edge_list에 x와 y가 같은경우와 연결이 되지않는 경우는 제외시켰다.

import heapq
import sys

input = sys.stdin.readline
N,M = map(int,input().split())


graph = [{} for _ in range(N+1)]
total_pay = 0
for _ in range(M):
    x,y,pay = map(int,input().split())
    graph[x][y] = pay
    graph[y][x] = pay
    total_pay += pay

INF = float('inf')

distance = [INF for _ in range(N+1)]
visited = [False for _ in range(N+1)]
node_list = []
heapq.heappush(node_list,(0,1))
result = 0
distance[1] = 0
cnt = 0
while node_list:
    dis,node = heapq.heappop(node_list)

    if visited[node]:
        continue
    result += dis
    cnt += 1
    visited[node] = True
    for next_node in graph[node]:
        if distance[next_node] > graph[node][next_node]:
            distance[next_node] = graph[node][next_node]
            heapq.heappush(node_list,(distance[next_node],next_node))


if cnt == N:
    print(total_pay-result)
else:
    print(-1)

이 문제는 전형적인 MST 문제였다.

그래서 나는 MST에서 익숙한 프림알고리즘을 이용해, 돌렸으며, 방문한 전체 노드의 수를 세주었다.

만약 전체 노드의 개수가 일치 하지 않으면, 모든 노드들을 연결 할 수 없으므로, -1을 출력해주었고,

전체 노드의 개수가 같으면, 원래 전체 비용에서 MST했을때의 비용을 빼주어서, 절약한 값을 출력해주었다.

import heapq
import sys
input = sys.stdin.readline
def find_parents(X):
    if make_set[X] ==X:
        return X
    else:
        make_set[X] = find_parents(make_set[X])
        return make_set[X]


def union(a,b):
    X = find_parents(a)
    Y = find_parents(b)
    if X == Y:
        return False
    if rank[X]< rank[Y]:
        X,Y = Y,X
    make_set[Y] = X
    if rank[X] == rank[Y]:
        rank[X] += 1
    return True


P,W = map(int,input().split())

c,v = map(int,input().split())

weight_list = [list(map(int,input().split())) for _ in range(W)]
make_set = [i for i in range(P)]
weight_list.sort(key=lambda x : x[2])
rank = [1 for _ in range(P)]
result = float('inf')
while find_parents(c) != find_parents(v):
    node_a,node_b,pay = weight_list.pop()
    if union(node_a,node_b):
        result = pay


print(result)

  이 문제를 푸는 방식은 다음과 같다. 최대 길이를 구하고, 그때의 최소 너비를 구하면 되는 것이다.

그러므로 크루스칼 알고리즘대로 푸는 대신 가장 앞에서부터 pop을 하던것에서 가장 뒤에서부터 pop을 하면서

그 두 노드가 같은 집합이 아닐때 합쳐주면서 그때의 pay를 result에 저장해주면 되는 방식으로 풀면 된다.

import sys
import heapq


input = sys.stdin.readline

P,W = map(int,input().split())

start_city,end_city = map(int,input().split())

graph = [{} for i in range(P)]

for _ in range(W):
    x,y,pay = map(int,input().split())
    graph[x][y] = max(graph[x].get(y,0),pay)
    graph[y][x] = max(graph[y].get(x,0),pay)


max_width_list = [0]*P
max_width_list[start_city] = float('inf')

node_list = []

heapq.heappush(node_list,(-float('inf'),start_city))


while node_list:
    maximun_width,cur_node  = heapq.heappop(node_list)
    maximun_width = -maximun_width
    for next_node in graph[cur_node]:
        
        cur_maximun_width = min(graph[cur_node][next_node],maximun_width)

        if cur_maximun_width > max_width_list[next_node]:
            max_width_list[next_node] = cur_maximun_width
            heapq.heappush(node_list,(-max_width_list[next_node],next_node))


print(max_width_list[end_city])

프림 알고리즘으로 푸는 방식은 거의 동일하다. 대신 cur_maximun_width가 다른데, 현재의 간선의 너비와 지금까지 최대 간선의 너비와 비교해서

그 중 더 큰 값을 비교에 쓴다.

이 점만 주의하고, 최소힙이 아니라 최대힙을 사용하면 해당 문제를 풀 수 있다.

import sys
import heapq
input = sys.stdin.readline



N = int(input())
node_list = []
pay_list = []

for i in range(N):
    pay = int(input())
    heapq.heappush(node_list,(pay,i))
    pay_list.append(pay)


connect_list = [list(map(int,input().split())) for _ in range(N)]

result = 0
visited = [False]*N
while node_list:
    pay,node = heapq.heappop(node_list)
    if visited[node]:
        continue
    visited[node] = True
    result += pay

    for next_node in range(N):
        if next_node != node:
            if pay_list[next_node] > connect_list[node][next_node]:
                pay_list[next_node] = connect_list[node][next_node]
                heapq.heappush(node_list,(pay_list[next_node],next_node))


print(result)

이 문제는 MST 문제로 기존의 MST와 다르게 여러개의 출발점을 동시에 가지는 MST라고 생각을 했다.

각 출발지점에 따라, 다른거이기 때문에 프림 알고리즘을 크루스칼 알고리즘보다 먼저 생각했다.

그래서 각 출발지점을 전부 입력으로 주어진 우물 개설비용으로 초기화 시켜준 점이 기존의 프림알고리즘하고

다른 방식이었다.

그리고 우물을 파는 비용,논의 위치를 heapq에 넣은듯 프림알고리즘을 해주었다.

그리고 방문 표시를 해서, 한번 들린곳은 다시 들리지 않도록 예외 처리를 해줬다.

기존의 MST에서 1곳의 출발지점을 정했던것과 달리, 모든 곳을 출발지점으로 생각하고, 비용을 갱신하면 되는 문제였다.

import sys

input = sys.stdin.readline

N = int(input())
edge = []
cost = []
def find_parent(ind):
    if make_set[ind] == ind:
        return ind
    make_set[ind] = find_parent(make_set[ind])
    return make_set[ind]


def union(A,B):
    X = find_parent(A)
    Y = find_parent(B)

    if X != Y:
        if rank[X] < rank[Y]:
            X,Y = Y,X
        make_set[Y] = X
        if rank[X] == rank[Y]:
            rank[X] += 1

for i in range(N):
    pay = int(input())
    edge.append((pay,0,i+1))
    cost.append(pay)

arr = [list(map(int,input().split())) for _ in range(N)]
for i in range(N):
    for j in range(i):
        edge.append((arr[i][j],i+1,j+1))



make_set = [i for i in range(N+1)]
rank = [0 for _ in range(N+1)]
edge.sort()
cnt = 0
result = 0
for pay,a,b in edge:
    if find_parent(a) != find_parent(b):
        cnt += 1
        result += pay
        union(a,b)
    if cnt == N:
        break
print(result)

크루스칼을 활용한 풀이이다.

여기서도 기존의 MST와 비슷하지만, 다른점은 물이 생성을 하는곳을 0이라는 인덱스를 부모로 가지도록

설정을 해주었다. 우물을 파서, 공급을 받는 곳은, 위치가 다를지라도, 물을 공급받고 있는 것이기 때문에

하나의 집합이라고 볼수 있기 때문이다. 이와 같은 작업을 N개가 이어질때까지 반복해주면 된다.

이 문제는 사실 https://boj.kr/10423 의 문제와 거의 동일하다고 볼 수 있다.

import sys
import heapq

input = sys.stdin.readline

N,M,K = map(int,input().split())

graph = [{} for i in range(N+1)]
plant = list(map(int,input().split()))
INF = float('inf')
for _ in range(M):
    u,v,w = map(int,input().split())
    graph[u][v] = min(graph[u].get(v,float('inf')),w)
    graph[v][u] = min(graph[v].get(u,float('inf')),w)



MST_DISTANCE = [INF for i in range(N+1)]
visited = [True]*(N+1)

result = 0
node_list = []
for start in plant:
    heapq.heappush(node_list,(0,start))
    MST_DISTANCE[start] = 0

while node_list:
    dis,node = heapq.heappop(node_list)
    if not visited[node]:
        continue
    result += dis
    visited[node] = False
    for next_node in graph[node]:
        if MST_DISTANCE[next_node] >graph[node][next_node]:
            MST_DISTANCE[next_node] = graph[node][next_node]
            heapq.heappush(node_list,(MST_DISTANCE[next_node],next_node))


print(result)

서로 다른 발전소끼리 연결이 되면 안되므로, 프림알고리즘을 하는데, 발전소의 위치를 전부 0으로 초기화 해주고,

전부 heapq에 넣어주고, Prim 알고리즘을 돌려주면 된다.

import sys
input = sys.stdin.readline

def union(a,b):
    A = find_parent(a)
    B = find_parent(b)
    if A != B:
        if rank[A] < rank[B]:
            A,B = B,A
        make_set[B] = A
        if rank[A] == rank[B]:
            rank[A] += 1

def find_parent(ind):
    if make_set[ind] == ind:
        return ind
    else:
        make_set[ind] = find_parent(make_set[ind])
        return make_set[ind]


N,M,K = map(int,input().split())


plant = list(map(int,input().split()))
make_set = [i for i in range(N+1)]
rank = [1 for _ in range(N+1)]
edges = []
for _ in range(M):
    u,v,w = map(int,input().split())
    edges.append((u,v,w))

edges.sort(key=lambda x : -x[2])


for k in range(1,K):
    union(plant[k],plant[k-1])

cnt = 1
result = 0
while cnt <(N-K+1):
    x,y,weight = edges.pop()
    if find_parent(x) != find_parent(y):
        union(x,y)
        result += weight
        cnt += 1

print(result)

    두번째 풀이는 크루스칼을 이용해서 풀었다.

발전소가 서로 연결이 되면 안되므로, 처음부터 모든 발전소를 하나의 union으로 merge를 해준다.

그리고 난뒤에 크루스칼 알고리즘을 해주면 된다.

그리고 전체 간선 수는 전체 노드의 수 - 1 이지만, 여기서는 (N-1)-(K-1)의 수 만큼만 해주면 된다.

이 문제를 처음에 어렵게 생각해서 각 플랜트만의 프림알고리즘을 돌려서, 최저값을 갱신하는 식으로 했다.

하지만, 같이 연결이 안되기만 하면 되니깐 프림 알고리즘을 하면서, 처음 스타트 위치를 전부 넣어주기만 하면 됬다.

이 문제에 더 어울리는 알고리즘은 프림보다, 크루스칼 알고리즘인 것 같다.

import sys
input = sys.stdin.readline




V,E = map(int,input().split())
graph = [{} for _ in range(V+1)]

for _ in range(E):
    A,B,C = map(int,input().split())
    graph[A][B] = C
    graph[B][A] = C
INF = float('inf')
visited = [False]*(V+1)
distance = [INF]*(V+1)
distance[1] = 0

node_list = [(1,0)]
cnt = 1
result = 0
while cnt <V:
    node, dis = node_list.pop()
    current_min_dis = INF
    current_min_node = -1
    visited[node] = True
    for next_node in graph[node]:
        if distance[next_node] > graph[node][next_node]:
            distance[next_node] =  graph[node][next_node]

    for ind in range(1,V+1):
        if current_min_dis > distance[ind] and not visited[ind]:
            current_min_node = ind
            current_min_dis = distance[ind]
    node_list.append((current_min_node,current_min_dis))
    result += current_min_dis
    cnt += 1

print(result)

첫 풀이는 다익스트라랑 비슷한 프림 알고리즘을 이용한 풀이였다. 하지만 해당 풀이는 실행시간이 오래걸려서 또 다른 방식으로 풀었다.

import sys
import heapq

input = sys.stdin.readline
V,E = map(int,input().split())

graph = [{} for _ in range(V+1)]

for _ in range(E):
    A,B,C = map(int,input().split())
    graph[A][B] = C
    graph[B][A] = C
INF = float('inf')
distance = [INF]*(V+1)
visited = [False]*(V+1)
node_list = []
distance[1] = 0
heapq.heappush(node_list,(0,1))
result = 0
while node_list:
    key,node = heapq.heappop(node_list)
    if visited[node]:
        continue
    visited[node] = True
    result += key
    for next_node in graph[node]:
        if distance[next_node] > graph[node][next_node]:
            heapq.heappush(node_list,(graph[node][next_node],next_node))
            distance[node] = graph[node][next_node]
print(result)

두번째는 프림 알고리즘이지만, heapq를 활용한 풀이였다. 위의 방식과 똑같지만, distance가 갱신될때에만을 판단하고, 그때 node_list에 추가하는 방식이었다.

import sys

input = sys.stdin.readline
def union(A,B):
    x = find_parent(A)
    y = find_parent(B)
    if x > y:
        x,y = y,x
    make_set[y] = x

def find_parent(ind):
    if make_set[ind] == ind:
        return ind
    make_set[ind] = find_parent(make_set[ind])
    return make_set[ind]




V,E = map(int,input().split())

grpah = sorted([list(map(int,input().split())) for _ in range(E)],key=lambda x : x[2],reverse=True)

make_set = [i for i in range(V+1)]

cnt = 1 
result = 0

while cnt <V:
    p1,p2,weight = grpah.pop()
    if find_parent(p1) != find_parent(p2):
        union(p1,p2)
        result += weight
        cnt += 1

print(result)

크루스칼 알고리즘으로 푼 방식이다. 크루스칼 알고리즘이 편한사람들은 금방 푼다고하는데, 크루스칼 알고리즘에 익숙하지 못해서 시간이 오래걸렸다.

많이 실패했던것은 make_set에 저장된 parent_node로 비교를 했을때 틀렸다. find_parent 이후에, 루트노드가 바뀐 경우 make_set에 저장된 모든 parent들이 root_node로 갱신되는것이 아니기 때문에, 문제가 생겼었다.

프림 알고리즘과 크루스칼 알고리즘은 자주 쓰이므로 좀 더 익숙해져야겠다.