[프로그래머스] Graph 복습 및 실습문제(전력망을 둘로 나누기) 풀이 - 파이썬

📖 문제

 

📃 코드

cnt = 0
def DFS(v, ch, graph):
    global cnt
    ch[v] = 1
    cnt += 1
    for i in graph[v]:
        if ch[i] == 0:
            DFS(i, ch, graph)
        

def solution(n, wires):
    global cnt
    answer = n
    graph = [[] for _ in range(n+1)]
    cnt = [0] * (n-1)
    
    for v1, v2 in wires:
        graph[v1].append(v2)
        graph[v2].append(v1)
    
    for v1, v2 in wires:
        ch = [0]*(n+1)
        # 끊는 역할
        ch[v2] = 1
        cnt = 0
        DFS(v1, ch, graph)
        answer = min(answer, abs(cnt - (n-cnt)))
    
    return answer

 

🗝️ 요약

[개념]

DFS를 이용해서 가능한 경우의 수를 모두 체크해서  최대, 최소 값을 찾는다.

[활용]
DFS의 대표적 문제 유형: 경로탐색(최단거리, 시간), 네트워크(연결), 조합(모든 조합 만들기)

연결을 끊는다는 건 한 노드에서 다른 노드로 visited를 체크(True) 처리해 주는 것과 같다.