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


G1 = None
stack = []
visited_ary = []		# 방문한 정점
name_ary = ['문별', '솔라', '휘인', '쯔위', '선미', '화사']
moon, sola, hwee, zzwe, sumi, hwas = 0, 1, 2, 3, 4, 5


G1 = Graph(6)
G1.graph[moon][sola] = 1; G1.graph[moon][hwee] = 1
G1.graph[sola][moon] = 1; G1.graph[sola][zzwe] = 1
G1.graph[hwee][moon] = 1; G1.graph[hwee][zzwe] = 1
G1.graph[zzwe][sola] = 1; G1.graph[zzwe][hwee] = 1; G1.graph[zzwe][sumi] = 1#; G1.graph[zzwe][hwas] = 1
G1.graph[sumi][zzwe] = 1#; G1.graph[sumi][hwas] = 1
#G1.graph[hwas][zzwe] = 1; G1.graph[hwas][sumi] = 1


print('## G1 무방향 그래프 ##')
for row in range(G1.SIZE):
    for col in range(G1.SIZE):
        print(G1.graph[row][col], end=' ')
    print()

current = 0		# 시작 정점 A
stack.append(current)
visited_ary.append(current)
stack_monitor = []
stack_monitor.append(name_ary[current])


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

    if next is not None:			  	   # 다음에 방문할 정점이 있는 경우
        current = next
        stack.append(current)
        visited_ary.append(current)
        # stack_monitor.append(name_ary[current])
        # print(stack_monitor)
    else:            	  	  	  	  # 다음에 방문할 정점이 없는 경우
        current = stack.pop()
        print(name_ary[current], end=' ')


print('\n방문 순서 -->', end='')
for i in visited_ary:
    print(name_ary[i], end='   ')
    #print(i, end='   ')