[TIL]211006(프로그래머스 위클리챌린지 9주차)

from collections import defaultdict
def solution(n, wires):
    graph=defaultdict(list)
    res = 101
    for a,b in wires:
        graph[a].append(b)
        graph[b].append(a)
    for a,b in wires:
        nodes,cnt,visited=[a],0,[b]
        while nodes:
            node = nodes.pop()
            if node in visited: continue
            visited.append(node)
            cnt+=1
            nodes+=graph[node]
        res = min(res,abs(n-cnt*2))
    return res

아이디어가 좋은 풀이는 아니지만 무난한 풀이가 나중에 써먹기는 좋은 것 같다.

그래프를 기록하기 위해서 defaultdict를 사용했다. defaultdict는 3번째줄 처럼 기본형태를 지정할 수 있다. 그래서 일반 딕셔너리를 사용한다면 만약 graph[a]가 없으면 graph[a]를 새로 만들고, b를 추가하라 라는 내용을 추가해야 되지만, defaultdict를 사용하면 애초에 빈 문자열이 할당되어 있기 때문에 번거롭지 않고 코드 가독성이 올라간다.

그리고 두 번째 for문에서 계산을 한다. 나는 a를 기준으로 계산했다. 어차피 두 그래프의 차를 계산하기 때문에 a,b중 하나를 잡고 기준으로 계산하면 되기 때문이다.
이후 while문을 이용해 dfs방식으로 계산한다. 한가지 주의할 점은 a->b는 안되기 때문에 visited에 처음부터 b를 넣어놓고 시작한다는 점이다.
여기서는 굳이 사용하지 않았지만, 만약 시간초과가 걸렸다면, nodes를 deque로 바꿨을 것 같다.