섬 연결하기

Kruskal algorithm

그래프 문제 해결 방법

• 마라톤처럼 node, edge, visit, val 자료구조를 만들고 시작했다.
• 그래프는 그래프를 그려야 한다

edge = [0 for i in range(100)]
node = [[0 for i in range(100)] for j in range(100)]
val = [[0 for i in range(100)] for j in range(100)]
visit = [0 for i in range(100)]

paths = []
cost_set = []

• 다음과 같이 그래프 관련 자료를 셋팅하고 시작하자

그래프 그리기

• 다음과 같은 테크닉으로 그래프를 그렸다.

    for c in costs:
        node[c[0]][edge[c[0]]] = c[1]
        node[c[1]][edge[c[1]]] = c[0]
        val[c[0]][c[1]] = c[2]
        val[c[1]][c[0]] = c[2]
        edge[c[0]] += 1
        edge[c[1]] += 1

DFS 내부

어려운것

DFS 사고과정

현재의 문제

• 크리스컬 알고리즘 -> 사이클이 일어나면 아니 사이클이 일어나지 않도록 해야하기에 더욱 어려움