[Programmers/파이썬] 프로그래머스(Lv.2) 전력망을 둘로 나누기 문제풀이

문제 풀이

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

프로그래머스

 

 

사고 흐름

1. 그래프 문제 -> dfs (재귀) 이용하자

2. 분할된 그래프의 송전탑의 차이가 최소가 되야하는데,, n은 최대 100, wires는 최대 99 이므로 -> 모든 wires(간선)에 대해 분할하는 완전 탐색

3. 큰 흐름은 알겠는데, 분할은 어떻게 처리하면 좋을까?

3-1. 분할한것을 이미 방문한 것으로 취급한다면? (그쪽으로 안가게)

3-2. 분할되지 않을 수도 있지 않을까? (이어진 다른 경로로 이동한다면)

3-3. 문제 조건에서 wires 길이, 즉 간선의 개수는 n-1 이고, 트리는 하나라고 했으므로 간선 하나만 끊으면 아예 그래프는 분할 된다. 즉 방문처리만 해도 분할된다고 판단! 

4. 코드 짜자~

 

문제 핵심과 알고리즘

dfs + 완전 탐색 

 

from collections import defaultdict

# 완전 탐색 - dfs 
def dfs(v, visited, graph) :
    
    visited.append(v)
    for w in graph[v] :
        if w not in visited :
            dfs(w, visited, graph)
    return visited

def solution(n, wires):
    ans = 100
    graph = defaultdict(list)
    
    for wire in wires :     # graph 생성 
        graph[wire[0]].append(wire[1])
        graph[wire[1]].append(wire[0])
    
    # 끊는다=이미방문함 으로 취급하고 방문한 노드 개수 리턴 
    for wire in wires :
        a,b = wire[0],wire[1]
        a_res = dfs(a, [b], graph)
        b_res = dfs(b, [a], graph)
        ans = min(ans, abs(len(a_res)-len(b_res)))
        
    return ans

 

이런 그래프 문제는 우선 그래프를 생성한다. 그리고 모든 간선(wires)에 대해 dfs를 실행한다. 위에서 말했듯이 분할은 이미 방문한 것으로 취급하기 때문에 초기 visited에 분할된 노드를 넣는다. 그리고 visited의 길이를 이용해 송전탑의 개수를 계산한다. 

 

문제 풀면서 헤맸던 부분

딱히 없었다

 

총평 

그래프 문제는 별로 안좋아해서 쫄았는데 생각보다 바로 풀어서 자신감을 가지게 됐다. dfs는 스택 사용해서 구현하는 것을 좋아하지만 재귀를 더 많이 쓰는 것 같아서 재귀에 익숙해져야겠다! (특히 return 부분)