Coding 공부

import sys


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


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

def union(x,y):
    X = find_parents(x)
    Y = find_parents(y)
    if ranks[X] < ranks[Y]:
        X,Y = Y,X
    make_set[Y] = X
    if ranks[X] == ranks[Y]:
        ranks[X] += 1


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

arr = [0] + list(input().split())
weight_list = []
for _ in range(M):
    x,y,pay = map(int,input().split())
    if arr[x] != arr[y]:
        weight_list.append((pay,x,y))

weight_list.sort(reverse=True)
make_set = [i for i in range(N+1)]
ranks = [1 for _ in range(N+1)]

cnt = 0
result = 0
while weight_list:
    pay,x,y = weight_list.pop()
    X,Y = find_parents(x), find_parents(y)

    if X != Y:
        union(X,Y)
        cnt += 1
        result += pay
    if cnt == N-1:
        break

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

이 문제는 처음부터 간선을 저장할때 두 노드가 남초+여초인 조합인 경우에만 저장을 해서 크루스칼을 해주면 된다.

그리고 크루스칼을 진행하고, 전체 cnt의 개수가 N-1이 안되는 경우에는 전부 연결이 안되는 경우이니 -1을 출력해주고

같을 때에는 result를 출력해주면 된다.

import sys

def input():
    return sys.stdin.readline().rstrip()
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
        return True
    return False

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

def kruskal():
    value = 0
    for p,x,y, in weight_list:
        if union(x,y):
            value += 1^p
    return value


N,M = map(int,input().split())
weight_list = []
for _ in range(M+1):
    x,y,p = map(int,input().split())
    weight_list.append((p,x,y))
make_set = list(range(N+1))
rank = [1]*(N+1)
weight_list.sort()
a = kruskal()
weight_list.sort(reverse=True)
make_set = list(range(N+1))
rank = [1]*(N+1)
b = kruskal()
print(a**2-b**2)

이 문제는 크루스칼을 활용해서 풀면 되는 문제이고, 크루스칼에 사용되는 간선을 오름차순과 내림차순으로 각각 정렬해서 

그때 크루스칼을 해서 값을 구한뒤 제곱값을 빼주면딘다.

import sys
import heapq
from collections import deque
def input():
    return sys.stdin.readline()

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

arr = [list(input()) for _ in range(N)]

start = [0,0,0]
node_list = []
total_cnt = 0
for x in range(N):
    for y in range(N):
        if arr[x][y] == 'S':
            start = [0,x,y]
            arr[x][y] = '0'



heapq.heappush(node_list,start)
INF = float('inf')
visited = [[True for _ in range(N)] for _ in range(N)]
distance = [[INF for _ in range(N)] for _ in range(N)]
result = 0
dx = [-1,1,0,0]
dy = [0,0,-1,1]
cnt = 0
while node_list:
    cur_dis,x,y, = heapq.heappop(node_list)
    if not visited[x][y]:
        continue
    if cur_dis > distance[x][y]:
        continue
    result += cur_dis
    cnt += 1
    visited[x][y] = False

    temp_visited = [[True for _ in range(N)] for _ in range(N)]
    queue = deque()
    queue.append((x,y,0))
    temp_visited[x][y] = False
    while queue:
        qx,qy,dis = queue.popleft()

        for i in range(4):
            nx = qx + dx[i]
            ny = qy + dy[i]

            if temp_visited[nx][ny] and arr[nx][ny] != '1':
                temp_visited[nx][ny] = False
                queue.append((nx,ny,dis+1))
                if arr[nx][ny] == 'K' and distance[nx][ny] > dis+1:
                    distance[nx][ny] = dis + 1
                    heapq.heappush(node_list,(dis+1,nx,ny))
if cnt<M+1:
    print(-1)
else:
    print(result)

 이 문제는 MST와 너비 우선 탐색을 활용한 문제였다.

일단 경계선은 전부 1로 되어있으므로, 경계체크를 해줄 필요는 없다.

문제를 푸는 아이디어는 다음과 같다. 

프림알고리즘을 이용한다.

그런데 프림 알고리즘을 활용할려면, 각 노드 사이의 간선의 정보를 알아야한다.

이 것은 BFS를 통해 로봇과 K들 사이의 간선들을 구하는 것이다.

즉, heap에 들어온 Node를 기준으로 다른 열쇠들 간의 간선의 정보를 찾으면 된다.

그래서 프림 알고리즘을 해서 나오는 노드를 기준으로 BFS를 돌리고, 열쇠이고, 현재 누적된 거리가 더 짧으면

거리를 갱신하고, 그 때의 위치 정보 및 거리를 heap에 넣어준다.

이런식으로 해서 프림알고리즘을 돌리면서 매번 BFS를 돌려서 해당 노드에서 다음노드로 갈수 있는 간선정보를 찾아

heap에 넣어주는 식으로 해주면 된다.

그리고 여기서 주의해야할 점은 모든 열쇠를 찾지 못하는 경우도 있다.

우리는 총 M + 1개의 노드를 가진 그래프에서 프림 알고리즘을 돌린것과 마찬가지이므로,

프림 알고리즘에서 방문한 노드의 수가 M+1개 보다 적으면 -1을 출력 해주며 된다.

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 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,M = map(int,input().split())

edge_list = []

for x in range(N):
    temp = list(input())
    for y in range(x+1,N):
        if temp[y] == 'Y':
            heapq.heappush(edge_list,(x,y))
city_cnt = 0
if len(edge_list) >= M:
    result = [0 for _ in range(N)]
    make_set = [i for i in range(N)]
    ranks = [1 for _ in range(N)]
    remain_list = []
    while edge_list:
        node_a,node_b = heapq.heappop(edge_list)
        if union(node_a,node_b):
            city_cnt += 1
            result[node_b] += 1
            result[node_a] += 1
        else:
            heapq.heappush(remain_list,(node_a,node_b))
    if city_cnt != N-1:
        print(-1)
    else:
        remain_cnt = M - city_cnt

        while remain_cnt>0:
            node_a,node_b = heapq.heappop(remain_list)
            result[node_a] += 1
            result[node_b] += 1
            remain_cnt -= 1
        print(*result)
else:
    print(-1)

이 문제는 문제를 이해하는데 힘들었고, 구현을 하는데 어려운 점이 많았었다.

평소에 MST 관련 문제는 프림 알고리즘을 주로 이용해서 풀었지만, 이 문제를 푸는데에는 크루스칼 알고리즘을 이용했다.

문제를 푸는 방식은 다음과 같다. 모든 간선들을 저장을 해주는데, 그 조건은 x,y 에서 y는 무조건 x보다 큰 경우의 간선만 저장을 시켜준다.

그래서 모든 간선을 저장시켰는데 주어진 M보다 적을때에는 -1을 출력을 해준다.

그리고 크루스칼 알고리즘을 이용해서 풀면된다.

그러나, 여기서 다른 점은 우리가 이미 union이 된 간선들을 버리게 되는데, 이걸 따로 저장을 시켜놓는다.

그리고 우리는 모든 크루스칼 알고리즘을 돌린뒤에, 모든 도시가 연결이 안되어있으면 -1을 출력을 해주고,

그리고 우리는 무조건 도로 M개를 무조건 연결을 해야하므로, 우리는 크루스칼 알고리즘을 통해 N-1개를 연결을 해놓은 상태이다.

그러므로 M-(N-1)개의 도로를 추가적으로 연결을 시켜주면 된다.

그래서 우리는 저장시켜놓은 도로들을 우선순위가 높은 것부터 뽑아서 연결을 시켜주면 된다.

import sys
from collections import deque
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,M = map(int,input().split())

edge_list = deque()
result = [0 for _ in range(N)]
make_set = [i for i in range(N)]
ranks = [1 for _ in range(N)]

city_cnt = 0
for x in range(N):
    temp = list(input())
    for y in range(x+1,N):
        if temp[y] == 'Y':
            if union(x,y):
                city_cnt += 1
                result[x] += 1
                result[y] += 1
            else:
                edge_list.append((x,y))


if city_cnt<N-1 or city_cnt+len(edge_list)<M:
    print(-1)
else:
    remain_cnt = M - city_cnt

    while remain_cnt>0:
        x,y = edge_list.popleft()
        result[x] += 1
        result[y] += 1
        remain_cnt -= 1
    print(*result)

이건 코드를 좀 더 개선시킨 버전이다.

달라진것은 heapq 대신 그냥 앞에서부터 차근차근 해주는 방식으로 바꿔준 것이다.

이 문제는 크루스칼을 이용하는 것뿐만 아니라, 문제를 잘 분석해야 풀 수 있었떤 문제였다.

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 sys
import heapq
input = sys.stdin.readline


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



graph = [{} for _ in range(N+1)]
INF = float('inf')
for _ in range(M):
    x,y,pay = map(int,input().split())
    graph[x][y] = min(graph[x].get(y,INF),pay)
    graph[y][x] = min(graph[y].get(x,INF),pay)


conquer = -1
pay_list = [[INF for _ in range(N+1)] for _ in range(2)]
pay_list[0][1] = 0
visted = [False]*(N+1)
cur_pay,cur_node = 0,1
result = 0
total_city = set(range(1,N+1))
while conquer<N-1:
    if visted[cur_node]:
        continue
    visted[cur_node] = True
    result += cur_pay
    total_city.remove(cur_node)
    conquer += 1
    idx = conquer%2
    if conquer > 0:
        prev_idx = (conquer+1)%2
        for city_num in total_city:
            pay_list[idx][city_num] = pay_list[prev_idx][city_num]+T
    
    min_idx = -1
    min_pay = INF
    for next_node in graph[cur_node]:
        temp_pay = graph[cur_node][next_node] + conquer*T
        if pay_list[idx][next_node] > temp_pay:
            pay_list[idx][next_node] = temp_pay

    for city_num in total_city:
        if min_pay > pay_list[idx][city_num]:
            min_pay = pay_list[idx][city_num]
            min_idx = city_num
    cur_pay,cur_node = min_pay,min_idx


print(result)

 이 문제는 어렵게 생각해서 오래 걸렸던 문제였다. 이 문제를 쉽게 생각해보면, conquer 비용은 고정적이다.

이 conquer 비용을 생각지 않고, 가장 마지막까지 구하고 난뒤에 conquer 비용만 더해주면 되는 문제이긴했다.

하지만 풀때에는 이 방식에 대해 잘 몰랐고, 그걸 적용시키지 않고, conquer 비용을 바로바로 구해주었다.

이 풀이의 방식은 다음과 같다 pay_list를 2*(N+1)로 해주었다.

즉 우리가 프림알고리즘에서 pay를 저장하는걸 1차원 배열 하나로 했던 거에 비해 2차원 배열을 이용해서 문제를 풀었다.

각각의 의미는 다음과 같다. 현재의 conquer 수치를 같이 저장을 해주면서

현재 conquer가 짝수이면, 0이고, 그때의 이전 pay_list 비용은 1번 인덱스에 있다.

현재 conquer가 홀수이면 1이고, 그때의 이전 pay_list 비용은 0번 인덱스에 있다.

즉 슬라이딩 윈도우처럼 각 전단계의 pay_list를 가져와서 현재 우리가 구하고자 하는

pay_list에 덮어씌워주는 방식으로 했다.

그 뒤에는 일반적인 프림알고리즘과 비슷하다.

현재 노드에서 갱신될수 있는것들을 전부 갱신을 한뒤에

모든 도시들을 찾아다니면서 가장 작은 값을 구해주면 되는 것이다.

import sys
import heapq
input = sys.stdin.readline


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



graph = [{} for _ in range(N+1)]
INF = float('inf')
for _ in range(M):
    x,y,pay = map(int,input().split())
    graph[x][y] = min(graph[x].get(y,INF),pay)
    graph[y][x] = min(graph[y].get(x,INF),pay)



pay_list =[INF for _ in range(N+1)]
node_list = []
visited = [False]*(N+1)
heapq.heappush(node_list,(0,1))
pay_list[1] = 0
result = 0
while node_list:
    cur_pay,cur_node = heapq.heappop(node_list)
    if pay_list[cur_node] < cur_pay or visited[cur_node]:
        continue
    visited[cur_node] = True
    result += cur_pay
    for next_node in graph[cur_node]:
        if pay_list[next_node] > graph[cur_node][next_node] and not visited[next_node]:
            pay_list[next_node] = graph[cur_node][next_node]
            heapq.heappush(node_list,(pay_list[next_node],next_node))


conquer_pay = (N-2)*(T+(N-2)*T)//2
result += conquer_pay
print(result)

이 풀이는 위에서 말한것처럼 어차피 conquer는 등차수열로 균등하게 증가하기 때문에, conquer를 배제하고,

우리가 일반적으로 구하는 프림알고리즘을 이용해서 문제를 해결한다.

그리고 난뒤에 등차수열의 합의 공식을 이용해서, conquer_pay를 구한뒤 결과값에 더해주면 된다.