[Graph] 알고리즘 및 문제풀이

그래프는 회로가 존재할 수 있지만

트리는 회로가 존재하지 않음(트리는 회로가 없기 때문에, 어느 한 선을 끊어주면은 둘로 나뉜다)

회로가 없는 그래프라고 가정하고 풀기

차례로 하나씩 끊어보기

check 배열 ch를 만들기

3-4를 끊고싶으면 ch[4]=1로 해놓고 DFS(3)을 돌려보기

 

def DFS(v,ch,graph)
 global cnt
 cnt += 1
 for i in graph[v]:
  if ch[i]==0
   DFS(i,ch,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+1
    graph = [[] for _ in range(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