BOJ 12784(인하니카 공화국)풀이

solved.ac 티어 : 골드 3

https://www.acmicpc.net/problem/12784

12784번: 인하니카 공화국

이 문제의 풀이는 생각보다 간단하다.

1에서부터 시작해서 dfs으로 끝점(괴도 루팡이 있다는 곳)까지 탐색하면서 지나온 길의 가중 치중 가장 작은 값을 찾고 모아지는 부분에서 더해주면 된다.

문제에 있는 예시로 설명을 해보겠다

 

괴도 루팡이 있을 수 있는 곳은 3,4,6,7번 점이다.

1부터 3,4,6,7인곳으로 dfs으로 탐색하면 된다.

일단 3부터 시작하자

1에서부터 3까지 갔을 때를 2에서부터 3으로 갔을 때, 1에서부터 2로 갔을 때로 나눌 수 있다.

일단 2에서 부터 3으로 갔을 때 가중치가 가장 작은 값은 4이다.

 

이번에 4로 가보자 4로 갔을 때는 가중치가 가장 작은 값이 1이다.

이제 2와 연결된 탐색이 끝났는데 이때 두 값을 더해줘야 된다.

왜냐하면 2에서부터 끊는 다고 했을 때 가중치가 4인 간선과 1인 간선 모두 끊어야 되기 때문에 더해줘야 된다.

이제 1에서 2로 간 경우도 확인해보자

1에서부터 2로 갈 때는 가중치가 1이다. 이때 2에서부터 끊는다고 했을 때의 값과 지금 가중치를 비교해서 작은 값을 골라줘야 한다.

즉 1+4과 1을 비교해야 된다는 것이다.

비교했을 때 1인 부분이 더 작기 때문에 1을 골라주면 된다.

이제 반대 쪽도 똑같이 해주면 1+2가 더 작기 때문에 왼쪽에서 골랐던 값 1과 오른쪽에서 골랐던 값 1+2를 더해주면 최소로 사용하는 값이다.

이제 구현해주면 끝이다.

import sys,math
from queue import PriorityQueue
input=sys.stdin.readline
inf=math.inf
t=int(input())
def dfs(x,y):
    global uy,ry
    #print("#",x)
    uy[x]=1
    if st[x]==1 and x!=1:return inf
    k=0
    for next in graph[x]:
        if next[0]!=y:
            if uy[next[0]]==0:
                zv=dfs(next[0],x)
                k+=min(zv,next[1])
    ry[x]=k
    return k
for _ in range(t):
    a,b=map(int,input().split())
    st=[0]*(a+1)
    uy=[0]*(a+1)
    ry=[-inf]*(a+1)
    graph=[[]for i in range(a+1)]
    for i in range(b):
        y=list(map(int,input().split()))
        st[y[0]]+=1
        st[y[1]]+=1
        graph[y[0]].append([y[1],y[2]])
        graph[y[1]].append([y[0],y[2]])
    print(dfs(1,1))