프로그래머스 위클리 챌린지 - 9주차 [그래프]

from collections import defaultdict
def TreeSize(start, excep, linkInfo, n):
    q = list(filter(lambda x: x != excep , linkInfo[start]))
    visited = [True if i in q else False for i in range(n+1)]
    visited[start] = True
    cnt = len(q) + 1

    while q:
        nextVal = q.pop()
        for i in linkInfo[nextVal]:
            if not visited[i]:
                q.append(i)
                visited[i] = True
                cnt += 1
    return cnt

def solution(n, wires):
    linkInfo = defaultdict(list)
    for i, j in wires:
        linkInfo[i].append(j)
        linkInfo[j].append(i)
    minimum = 100000000
    for i, j in wires:
        minVal = abs(TreeSize(i, j, linkInfo, n) - TreeSize(j, i, linkInfo, n))
        if minVal < minimum:
            minimum = minVal
    return minimum

 

📝해결 아이디어

 

1. 특정 간선이 잘렸을때 서브 그래프 두개의 size를 구해야한다.

2. 각 간선을 순회하면서 해당 간선이 잘렸을 때 두 그래프의 사이즈를 구해야한다.

3. 그림에 보이는 간선이 잘렸을 경우 4에서 7로 가는건 제외하고 4에서 시작해서 그래프를 순회하며 노드 갯수를 센다. 마찬가지로 7에서 4로 가는건 제외하고 7에서 시작하여 그래프를 순회한다.