[알고리즘 문제 풀이][완전탐색] 백준 12784번 - 인하니카 공화국

백준 12784번 인하니카 공화국 문제입니다.

(완전탐색 - DFS)

 

- 문제 설명: https://www.acmicpc.net/problem/12784

- 문제 풀이:

 

본 문제는 맨 끝 부분 노드 (리프 노드)와 가장 상위에 존재하는 1번 노드 (루트 노드) 사이의 연결을 끊는 문제입니다. 가장 최소로 다이너마이트 개수를 사용하고 싶다고 했으므로, 자식부터 부모로 올라가면서 자신의 아래 자식 사이 길을 끊는 게 이득인지 자신과 부모 사이 길을 끊는게 이득인지 판단하면 됩니다. 이 문제는 어떤 노드가 자식 노드인지 예제에서 주어지지 않아서 BFS를 하기 위해서는 한 번 for 문을 돌면서 찾아야한다는 귀찮음이 있어 대부분 DFS 로 구현한 코드가 많습니다.

 

- 코드: 

(1) DFS 코드

(출처) https://www.acmicpc.net/source/36691655

import sys
input = sys.stdin.readline

def dfs(x):
    visited[x] = True
    dynamite = 0
    for g in graph[x]:
        if not visited[g[0]]:
            dynamite += min(g[1], dfs(g[0]))
    return dynamite if dynamite else 10000


for _ in range(int(input().rstrip())):
    N, M = map(int, input().rstrip().split())
    if N == 1:
        print(0)
    else:
        graph = [[] for _ in range(N + 1)]
        visited = [False for _ in range(N + 1)]
        for _ in range(M):
            a, b, c = map(int, input().rstrip().split())
            graph[a].append((b, c))
            graph[b].append((a, c))
        print(dfs(1))

(2) BFS 코드

import sys
input = sys.stdin.readline

connect = [[0 for i in range(1000)] for j in range(1000)]
for _ in range(int(input())):
    n, m = map(int, input().split())
    for i in range(n):
        for j in range(n):
            connect[i][j] = 0
    indegree = [0]*n
    # 자식이 준 값
    compare = [0]*n

    # 반례 처리
    if m == 0:
        print(0)
        continue
    
    for __ in range(m):
        a, b, d = map(int, input().split())
        indegree[a-1] += 1
        indegree[b-1] += 1
        connect[a-1][b-1] = d
        connect[b-1][a-1] = d
    
    q = []
    qs = 0
    qe = 0

    # 개수가 1인 애들
    indegree[0] += 1 # 이것만 부모가 없어서 1이 덜 들어감
    for i in range(n):
        if indegree[i] == 1:
            q.append(i)
            qe += 1
            compare[i] = 1000000

    while qs < qe:
        current = q[qs]
        qs += 1
        indegree[current] -= 1

        for i in range(n):
            d = connect[current][i]
            if d > 0:
                connect[i][current] = 0
                indegree[i] -= 1
                # 내 부모에게 내가 가진 값과 연결 값 중 더 작은 걸 줌
                compare[i] += d if d < compare[current] else compare[current]
                if indegree[i] == 1:
                    q.append(i)
                    qe += 1
                break
                
    print(compare[0])

 

- 실수 포인트 & 반례:

1. 루트 노드만 존재하는 경우

입력
1
1 0
정답
0

 

2. 그 외 가능한 반례들

입력)
1
7 6
1 2 9
2 3 4
2 4 1
5 1 4
6 5 1
7 5 2

정답)
8

입력)
1
3 2
1 2 2
2 3 1

정답)
1