# week14_04_chap09_05.py
class Graph:
    def __init__(self, size):
        self.SIZE = size
        self.graph = [[0 for _ in range(size)] for _ in range(size)]


def print_graph(g):
    print('   ', end=' ')
    for v in range(g.SIZE):
        print(nameAry[v], end=' ')
    print()
    for row in range(g.SIZE):
        print(nameAry[row], end=' ')
        for col in range(g.SIZE):
            #print("%2d" % g.graph[row][col], end=' ')
            print(f"{g.graph[row][col]:4d}", end='')
        print()
    print()


def find_vertex(g, find_vtx)->bool:
    stack = []
    visited_ary = []	 # 방문한 노드

    current = 0	 # 시작 정점
    stack.append(current)
    visited_ary.append(current)

    while len(stack) != 0:
        next = None
        for vertex in range(G1.SIZE):
            if g.graph[current][vertex] != 0:
                if vertex in visited_ary:  # 방문한 적이 있는 정점이면 탈락
                    pass
                else:			# 방문한 적이 없으면 다음 정점으로 지정
                    next = vertex
                    break

        if next is not None:				# 다음에 방문할 정점이 있는 경우
            current = next
            stack.append(current)
            visited_ary.append(current)
        else:					# 다음에 방문할 정점이 없는 경우
            current = stack.pop()

    if find_vtx in visited_ary:
        return True
    else:
        return False


G1 = None
nameAry = ['춘천', '서울', '속초', '대전', '광주', '부산' ]
cc, sl, sc, dj, kw, bs = 0, 1, 2, 3, 4, 5


G1 = Graph(6)
G1.graph[cc][sl] = 10; G1.graph[cc][sc] = 15
G1.graph[sl][cc] = 10; G1.graph[sl][sc] = 40; G1.graph[sl][dj] = 11; G1.graph[sl][kw] = 50
G1.graph[sc][cc] = 15; G1.graph[sc][sl] = 40; G1.graph[sc][dj] = 12
G1.graph[dj][sl] = 11; G1.graph[dj][sc] = 12; G1.graph[dj][kw] = 20; G1.graph[dj][bs] = 30
G1.graph[kw][sl] = 50; G1.graph[kw][dj] = 20; G1.graph[kw][bs] = 25
G1.graph[bs][dj] = 30; G1.graph[bs][kw] = 25

print('## 자전거 도로 건설을 위한 전체 연결도 ##')
print_graph(G1)

# 가중치 간선 목록
edge_ary = []
for i in range(G1.SIZE):
    for k in range(G1.SIZE):
        if G1.graph[i][k] != 0:
            edge_ary.append([G1.graph[i][k], i, k])

from operator import itemgetter
# 간선 정렬, 기준은 weight로 내림차순
edge_ary = sorted(edge_ary, key=itemgetter(0), reverse=True)

new_ary = []
for i in range(0, len(edge_ary), 2):
    new_ary.append(edge_ary[i])

index = 0
while len(new_ary) > G1.SIZE - 1:  # 간선의 개수가 '정점 개수-1'일 때까지 반복
    start = new_ary[index][1]  # 서울
    end = new_ary[index][2]  # 광주
    saveCost = new_ary[index][0]  # 50

    G1.graph[start][end] = 0  # 50 -> 0
    G1.graph[end][start] = 0  # 50 -> 0

    startYN = find_vertex(G1, start)  # True
    endYN = find_vertex(G1, end)  # True

    if startYN and endYN:
        del new_ary[index]  # 서울-광주 구간 간선 제거
    else:
        G1.graph[start][end] = saveCost
        G1.graph[end][start] = saveCost
        index += 1

print('## 최소 비용의 자전거 도로 연결도 ##')
print_graph(G1)