전력망을 둘로 나누기

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

코딩테스트 연습 - 9주차

 

파이썬

def solution(n, wires):
    answer = n
    tree = {k: set() for k in range(1, n + 1)}
    for a, b in wires:
        tree[a].add(b)
        tree[b].add(a)
    for a, b in wires:
        tree[a].remove(b)
        tree[b].remove(a)
        result = abs(2 * dfs(a, tree) - n)
        tree[a].add(b)
        tree[b].add(a)
        answer = min(answer, result)
    return answer


def dfs(start, tree):
    stack = [start]
    marked = {start}
    while stack:
        v = stack.pop()
        for w in tree[v]:
            if w not in marked:
                stack.append(w)
                marked.add(w)
    return len(marked)

테스트 1 〉	통과 (0.11ms, 10.3MB)
테스트 2 〉	통과 (1.59ms, 10.3MB)
테스트 3 〉	통과 (2.00ms, 10.3MB)
테스트 4 〉	통과 (2.15ms, 10.2MB)
테스트 5 〉	통과 (2.36ms, 10.3MB)
테스트 6 〉	통과 (0.02ms, 10.2MB)
테스트 7 〉	통과 (0.01ms, 10.3MB)
테스트 8 〉	통과 (0.10ms, 10.3MB)
테스트 9 〉	통과 (0.06ms, 10.3MB)
테스트 10 〉	통과 (1.28ms, 10.3MB)
테스트 11 〉	통과 (1.27ms, 10.3MB)
테스트 12 〉	통과 (1.43ms, 10.3MB)
테스트 13 〉	통과 (1.27ms, 10.3MB)

level 2의 문제.. 
tree 또는 graph의 의미를 알고,
너비 우선 검색 또는 깊이 우선 검색을 할 수 있으면,
전수조사(brute force)로도 풀 수 있는 문제이다. 

주어진 wires 중에 하나의 wire를 제외하면
트리는 둘로 나눠지게 된다. 

제외된 wire의 두 노드(원소)는
둘로 나눠진 트리에 각각 포함된다. 

두 노드를 각각 시작점으로 트리를 검색하여
각 트리의 원소를 갯수를 확인한 뒤... 
이를 비교하면 된다...

비교할 때 2개의 트리의 노드의 합은 n 이니까
1개의 트리만 검색하는 것이 더 빠르다. 

abs(len(tree1) - len(tree2))
= abs(len(tree1) - (n - len(tree1)))
= abs(2 * len(tree1) - n)

 

bfs도 한 번.. 

def solution(n, wires):
    answer = n
    tree = {k: set() for k in range(1, n + 1)}
    for a, b in wires:
        tree[a].add(b)
        tree[b].add(a)
    for a, b in wires:
        tree[a].remove(b)
        tree[b].remove(a)
        result = abs(2 * bfs(a, tree) - n)
        tree[a].add(b)
        tree[b].add(a)
        answer = min(answer, result)
    return answer


def bfs(start, tree):
    queue = [start]
    marked = {start}
    while queue:
        v = queue.pop(0)
        for w in tree[v]:
            if w not in marked:
                queue.append(w)
                marked.add(w)
    return len(marked)

테스트 1 〉	통과 (0.12ms, 10.3MB)
테스트 2 〉	통과 (1.41ms, 10.3MB)
테스트 3 〉	통과 (1.99ms, 10.3MB)
테스트 4 〉	통과 (2.25ms, 10.2MB)
테스트 5 〉	통과 (2.77ms, 10.2MB)
테스트 6 〉	통과 (0.02ms, 10.3MB)
테스트 7 〉	통과 (0.01ms, 10.3MB)
테스트 8 〉	통과 (0.09ms, 10.3MB)
테스트 9 〉	통과 (0.06ms, 10.3MB)
테스트 10 〉	통과 (1.42ms, 10.3MB)
테스트 11 〉	통과 (1.39ms, 10.2MB)
테스트 12 〉	통과 (1.55ms, 10.3MB)
테스트 13 〉	통과 (1.40ms, 10.3MB)