[프로그래머스 86971 파이썬] 전력망을 둘로 나누기 (level 2, DFS or UF)

알고리즘 유형 : DFS or 유니온 파인드(UF)
풀이 참고 없이 스스로 풀었나요? : O (유니온 파인드는 풀이 참고)

https://school.programmers.co.kr/learn/courses/30/lessons/86971

SOLVE 1

DFS 풀이

def DFS(v, graph, visited, check_link):
    cnt = 1
    visited[v] = True
    
    for adj_v in graph[v]:
        # 방문 이력이 없고, 그 간선이 임시로 없앤 간선이 아닌 경우
        if visited[adj_v] == False and check_link[v][adj_v]:
            cnt += DFS(adj_v, graph, visited, check_link)
    
    return cnt

def solution(n, wires):
    answer = INF
    
    # 없앤 간선인지 아닌지 체크 값이 들어있는 리스트
    check_link = [[True]*(n+1) for _ in range(n+1)]
    
    graph = [[] for _ in range(n+1)]
    cnt_all = []
    
    for a, b in wires:
        graph[a].append(b)
        graph[b].append(a)
    
    for a, b in wires:
        visited = [False]*(n+1)
        
        check_link[a][b] = False # a-b 간선 끊기
        cnt_a = DFS(a, graph, visited, check_link)
        cnt_b = DFS(b, graph, visited, check_link)
        check_link[a][b] = True # a-b 간선 다시 연결
        
        answer = min(answer, abs(cnt_a - cnt_b))
    
    return answer

SOLVE 2

UF 풀이

import sys
input = sys.stdin.readline
INF = sys.maxsize

def find(x, parent):
    if parent[x] < 0:
        return x
    
    parent[x] = find(parent[x], parent)
    return parent[x]

def union(a, b, parent):
    root_a = find(a, parent)
    root_b = find(b, parent)
    
    if root_a == root_b:
        return False
    
    if parent[root_a] < parent[root_b]:
        # 루트 노드의 parent 값의 절댓값은 트리의 크기를 의미
        parent[root_a] += parent[root_b]
        parent[root_b] = root_a
    elif parent[root_a] > parent[root_b]:
        parent[root_b] += parent[root_a]
        parent[root_a] = root_b
    else:
        parent[root_b] += parent[root_a]
        parent[root_a] = root_b
    
    return True

def solution(n, wires):
    answer = INF
    for exclude in range(len(wires)):
        parent = [-1]*(n+1)
        
        # 간선을 차례대로 제외해보면서, 이외의 간선들로 유니온 파인드
        for a, b in (wires[:exclude] + wires[exclude+1:]):
            union(a, b, parent)
        
        # 제외한 간선의 양 끝 점은 서로 독립된 트리의 어느 한 점이므로,
        # 그 두 점의 루트 노드의 parent 값의 차의 절댓값이 두 트리
        # 사이의 노드 개수 차이이다.
        sub_cnt1 = parent[find(wires[exclude][0], parent)]
        sub_cnt2 = parent[find(wires[exclude][1], parent)]
        answer = min(answer, abs(sub_cnt1 - sub_cnt2))
    
    return answer

print(solution(9, [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]]))

SOLVE 1) 풀이 요약 (DFS 풀이)

1. 주어진 간선을 하나하나씩 순서대로 제외시켜가보면서, 제외한 간선의 양 끝 점에서 DFS를 돌려서 양 끝 점이 소속된 두 개의 서로소인 트리의 노드의 개수를 구할 수 있고, 그 값의 차의 절댓값들 중 가장 최소인 값을 출력해주면 된다.

2. 그렇다면 간선을 제외하는 것은 어떻게 구현할까?

   우선 모든 간선을 graph에 넣어준다.

   이 후, check_link 리스트를 선언한다.

   check_list[a][b]는 a-b 간선이 제외시킨 간선인지에 대한 여부를 의미한다.

   즉, a-b 간선을 제외시키기 위해선 check_list[a][b]를 True로 설정해주면 되고,

   a와 b에서 DFS를 돌려 두 트리의 크기 차의 절댓값을 구해서 answer를 갱신해준 후,

   다시 check_list[a][b]를 False로 되돌려준 후, 다음 간선으로 넘어가 또 제외시킨 후 DFS를 돌리고..

   이걸 모든 간선에 대해 차례차례 반복해주면 된다.

SOLVE 2 풀이 요약 (DP 풀이)

1. 트리에서 하나의 간선을 끊으면 두 개의 서로소 트리가 생긴다.

   따라서, 간선을 끊어준 후 나머지 간선들로 유니온 파인드를 실행하여 두 트리를 만든 후, 두 트리의 크기의 차를 연산해주기만 하면 된다.

2. 여기서 간선을 끊는 것은 이렇게 구현하자.

   wires를 처음부터 끝까지 순회하면서, 각 간선을 제외한 나머지 wires 리스트를 인덱싱과 합연산으로 구하여, 이 새로운 리스트를 순회하며 유니온 파인드를 연결 간선에 대해 모두 실행해주면 된다.

3. 그리고 유니온 파인드로 만든 트리의 크기는, union 함수를 실행할 때, 합치는 주체가 되는 트리의 루트 노드의 parent 값에, 합침 당하는 트리의 루트 노드의 parent 값을 더해준다. 트리의 루트 노드의 parent 값은 음수이며, 절댓값은 트리의 크기를 의미하도록 구현하자.

배운 점, 어려웠던 점

• 구현력과 알고리즘 적재적소 활용력을 기를 수 있는 문제였다.

• 처음에는 유니온 파인드로 구현하려고 했었다. 다만 전체 간선에 대해 유니온 파인드를 실행하되, 각 노드에 대해 본인이 루트 노드일 때의 부분 트리의 크기를 리스트에 따로 저장하여, 이 리스트를 활용하여 답을 구하려고 했다가 댕같이 망했다.