전력망을 둘로 나누기

visited = [False for i in range(101)]
answer = 987654321

def dfs(node_num, nodes):
    global visited
    visited[node_num] = True
    
    for item in nodes[node_num]:
        visited[item] = True
        for x in nodes[item]:
            if not visited[x]:
                dfs(x, nodes)
    
def simulate(nodes, edge_to_cut, total_size):
    global visited, answer
    nd1, nd2 = edge_to_cut[0], edge_to_cut[1]
    nodes[nd1].remove(nd2)
    nodes[nd2].remove(nd1)
    
    # DFS - 트리 크기 탐색
    tree_size = []
    for i in range(1, total_size+1):
        if not visited[i]:
            dfs(i, nodes)
            tree_size.append(visited.count(True))
    diff = abs(tree_size[0] - (total_size - tree_size[0]))
    answer = min(answer, diff)
    
    nodes[nd1].append(nd2)
    nodes[nd2].append(nd1)


def solution(n, wires):
    global visited
    
    # 노드 관계 생성
    nodes = [[] for i in range(n+1)]
    for info in wires:
        node1, node2 = info[0], info[1]
        nodes[node1].append(node2)
        nodes[node2].append(node1)
    
    # 전선 한 개씩 제외하며 탐색
    for wr in wires:
        simulate(nodes, wr, n)
        visited = [False for i in range(n+1)]
        
    return answer

한개씩 트리의 간선을 끊어보고 둘로 나누어진 트리 크기 차를 구할 수 있느냐의 문제였다.
처음으로 든 생각은 DFS였다. 나누어진 두 트리의 노드를 기준으로 dfs를 수행하면 트리의 개수가 나오고, 나머지는 전체에서 그 크기를 뺀 만큼의 크기일 것이다.

풀이를 마치고, 다른 사람의 풀이를 살펴보았는데 역시 나와 같이 graph로 푼 풀이도 있었고, union-find로 접근한 사람도 있었다.

어느 쪽의 풀이든 상관없지만 dfs 로직을 구현할 때 조금 더 정제되고 깔끔한 코드를 짜도록 노력해야 겠다는 생각이 든 문제였다.

문제 출처: https://school.programmers.co.kr/learn/courses/30/lessons/86971