# File Name : ia17.py
import koreanize_matplotlib
import queue                      # 정보를 저장하기 위해 큐를 사용
import matplotlib.pyplot as plt   # 시각적인 표현을 위해 사용

# 지역의 위치 저장
def Pos( ):
  city = {
    '인천': [11, 292], '서울': [100, 257], '광주':[11, 90],
    '춘천': [205, 300], '양평': [195, 232],'대전': [209, 179],'양양': [295, 315],
    '원주': [255, 230], '제천': [265, 185],'대구': [250, 80],
    '강릉항':[332, 252],'묵호항':[319, 215],'후포항': [310, 165],'포항':[290, 100],
    '울릉군': [400, 223], '독도': [450, 200]
  }
  return city

# 지역 간의 연결 관계와 이동 시간을 저장
def mTime():
  graph = {
    '인천': [['서울', 1]],
    '서울': [['인천', 1], ['춘천', 2], ['양평', 1], ['대전', 3], ['광주', 5]],
    '춘천': [['서울', 2], ['양양', 1]],
    '양평': [['서울', 1], ['양양', 2], ['원주', 2]],
    '대전': [['서울', 3], ['원주', 2], ['제천', 2], ['대구', 2]],
    '양양': [['춘천', 1], ['양평', 2], ['강릉항', 1], ['묵호항', 1]],
    '원주': [['양평', 2], ['대전', 2], ['묵호항', 2]],
    '제천': [['대전', 2], ['묵호항', 2], ['후포항', 3]],
    '대구': [['대전', 2], ['포항', 1]],
    '광주': [['서울', 5]],
    '강릉항': [['양양', 1], ['울릉군', 3]],
    '묵호항': [['양양', 1], ['원주', 2],['제천', 2], ['울릉군', 3]],
    '후포항': [['제천', 3], ['울릉군', 2]],
    '포항': [['대구', 1], ['울릉군', 3]],
    '울릉군': [['강릉항', 3], ['묵호항', 3], ['후포항', 2], ['포항', 3],['독도', 2]],
    '독도': [['울릉군', 2]]
    }
  return graph

def H( ):
  hn = {
  '인천': 15, '서울': 13, '광주': 16,
  '춘천': 11, '양평': 10, '대전': 9, '양양': 5,
  '원주': 7, '제천': 5, '대구': 8,
  '강릉항': 3, '묵호항': 2, '후포항': 3, '포항': 4,
  '울릉군': 1, '독도': 0
  }
  return hn

def bestFS(start, hn, graph, goal = '독도'):
  pQueue = queue.PriorityQueue() # 우선순위 큐* 생성
  pQueue.put((hn[start], start, 0)) # 출발지의 이름, 출발지의 휴리스틱 값과 이동 시간을 큐에 추가
  path = [] # 경로를 저장하기 위한 리스트 초기화
  best_time = 0 # 총 이동 시간을 저장하기 위한 변수 초기화
  visited = set() 


  while not pQueue.empty(): # 큐에 데이터가 있는 동안 반복
    current, c_time = pQueue.get()[1:] # 우선순위가 가장 높은 노드를 꺼냄 
    if current in visited: # 현재 노드 visited에 있으면 건너뛰기
      continue
    visited.add(current) # 방문한 현재 노드를 visited 집합에 추가
    path.append(current) # 방문한 현재 노드를 경로 리스트에 추가
    best_time = c_time # 해당 노드까지의 이동 시간을 총 이동 시간에 더함
    if current == goal: # 현재 노드가 목적지일 경우
      break # 반복문 종료
    for next, cost in graph[current]: # 현재 노드와 연결되어 있는 노드 방문
      if next not in visited: # 방문하지 않은 노드만 탐색
        new_cost = c_time + cost # 누적 이동 시간 계산
        pQueue.put((hn[next], next, new_cost)) # 연결된 노드의 정보를 큐에 추가
  return path, best_time # 최종 경로와 총 이동 시간을 반환


def drawMap(city, bestfs, graph): # 최상우선탐색이 적용되는 그래프를 시각화
  for i, j in city.items(): # 모든 지역에 대해 반복
    plt.plot(j[0], j[1], 'ro') # 지역의 위치에 빨간 점으로 표시
    plt.annotate(i, (j[0] + 5, j[1]), fontsize = 13) # 지역의 이름을 표시
    for k in graph[i]:
      n = city[k[0]] # 이웃 지역의 위치를 저장
      plt.plot([j[0], n[0]], [j[1], n[1]], 'gray') # 지역 간의 연결선
      # 지역 간의 거리를 표시
      plt.annotate(str(k[1]), ((j[0] + n[0])/2, (j[1] + n[1])/2),color = 'purple', fontsize = 13)
  for i in range(len(bestfs)-1):
    first = city[bestfs[i]] # 경로의 현재 지역의 위치를 가져옴
    second = city[bestfs[i + 1]] # 경로의 다음 지역의 위치를 가져옴
    plt.plot([first[0], second[0]], [first[1], second[1]], 'yellow') # 최상우선탐색 경로 표시
 

heuristic = H() # 경험정보 함수 실행
graph = mTime() # 지역의 연결 관계 및 이동 시간 정보 함수 실행
city = Pos() # 도시의 좌표 설정
bestfs,best_time = bestFS('서울', heuristic, graph) # 최상우선탐색 실행
drawMap(city, bestfs, graph) # 지도에 시각화
print('AI Search = > ', bestfs, '총 이동 시간: ', best_time) # 탐색 결과 출력


plt.show()