# [ 최단경로 찾기 ] by Python

 스타크래프트를 하다가 유닛이 어떻게 장애물을 피해 최단경로를 찾아서 갈까 궁금해 하다가 최단경로 찾는 방법을 검색하던 중 가중치 그래프를 이용한 다익스트라 알고리즘을 설명하는 글을 보고 그대로 한번 파이썬으로 짜봤다.

다익스트라(Dijkstra) 알고리즘

① 지도상의 모든 건물들과 집에서 각 건물들까지의 최단 거리를 나타내는 표를 만든다.
② 집과 직접 길로 이어진 건물들까지의 최단 거리는 지도에 표시된 값으로 적고 그렇지 않은 건물들은 빈 칸으로 놓아둔다. 여기서 빈 칸의 값은 무한대를 뜻한다.
③ 거리가 가장 짧은 건물부터 긴 건물 순으로 방문하고 방문한 건물은 색깔로 칠해 구별한다. 이때 방문한 경로도 색칠한다. 
④ 새로운 건물을 방문하면 그 건물과 이어진 건물들까지의 거리를 새로 바꾼다. 단, 이전에 이미 최단 거리가 구해졌었다면 거리를 서로 비교해 작은 것으로 바꾸거나 유지한다.
⑤ 그래프의 모든 건물들을 방문할 때까지 ③,④의 과정을 반복한다.

출처 : http://playsw.naver.com/repo/cast/105

#대략적인 알고리즘 과정

#자세한 알고리즘 설명(영어)

+)설명추가

#최단경로 알고리즘
#reference : http://navercast.naver.com/contents.nhn?rid=2871&contents_id=85293
import copy

#목적지와 도착지를 설정해준다
departure = 'home'
destination = 'school'
print "-----------[", departure, "->", destination,"]----------"


#① 지도상의 모든 건물들과 집에서 각 건물들까지의 최단 거리를 나타내는 표를 만든다.

landscape = {
    'home':             {'hairShop':5, 'superMarket':10, 'EnglishAcademy':9},
    'hairShop' :        {'home':5 ,'superMarket':3, 'bank':11},
    'superMarket' :     {'hairShop':3, 'home':10, 'EnglishAcademy':7, 'restourant':3},
    'EnglishAcademy':   {'home':9, 'superMarket':7, 'school':12},
    'restourant' :      {'superMarket':3, 'bank':4},
    'bank' :            {'hairShop':11, 'restourant':4, 'EnglishAcademy':7, 'school':2},
    'school' :          {'bank':2, 'EnglishAcademy':12}
    }

routing = {}
for place in landscape.keys():
    routing[place]={'shortestDist':0, 'route':[], 'visited':0}

#④

def visitPlace(visit):
    routing[visit]['visited'] = 1
    for toGo, betweenDist in landscape[visit].items():
        toDist = routing[visit]['shortestDist'] + betweenDist
        if (routing[toGo]['shortestDist'] >= toDist) or  not routing[toGo]['route']:
            routing[toGo]['shortestDist'] = toDist
            routing[toGo]['route'] = copy.deepcopy(routing[visit]['route'])
            routing[toGo]['route'].append(visit)
            

#② 집과 직접 길로 이어진 건물들까지의 최단 거리는 지도에 표시된 값으로 적고 그렇지 않은 건물들은 빈 칸으로 놓아둔다. 여기서 빈 칸의 값은 무한대를 뜻한다.
            
visitPlace(departure)

"""
③ 거리가 가장 짧은 건물부터 긴 건물 순으로 방문하고 방문한 건물은 색깔로 칠해 구별한다. 이때 방문한 경로도 색칠한다. 
④ 새로운 건물을 방문하면 그 건물과 이어진 건물들까지의 거리를 새로 바꾼다. 단, 이전에 이미 최단 거리가 구해졌었다면 거리를 서로 비교해 작은 것으로 바꾸거나 유지한다.
⑤ 그래프의 모든 건물들을 방문할 때까지 ③,④의 과정을 반복한다.
"""
while 1 :
    #③
    minDist = max(routing.values(), key=lambda x:x['shortestDist'])['shortestDist']
    toVisit = ''
    for name, search in routing.items():
        if 0 < search['shortestDist'] <= minDist and not search['visited']:
            minDist = search['shortestDist']
            toVisit = name
    #⑤
    if toVisit == '':
        break
    #④
    visitPlace(toVisit)

    print "["+toVisit+"]"
    print "Dist :", minDist

print "\n", "[", departure, "->", destination,"]"
print "Route : ", routing[destination]['route']
print "ShortestDistance : ", routing[destination]['shortestDist']

맵은 한 곳에서 갈 수 있는 모든 지점과 거리를 dict로 나태냄.

# 실행결과

-INPUT

위 그림에서 집에서부터 학교까지의 최단거리를 구하는 것.

출발점 - 집

도착점 - 학교

departure = 'home'

destination = 'school'

-OUTPUT

>>> ================================ RESTART ================================
>>>
-----------[ home -> school ]----------
[hairShop]
Dist : 5
[superMarket]
Dist : 8
[EnglishAcademy]
Dist : 9
[restourant]
Dist : 11
[bank]
Dist : 15
[school]
Dist : 17

[ home -> school ]
Route :  ['home', 'hairShop', 'superMarket', 'restourant', 'bank']
ShortestDistance :  17

최단경로 알고리즘.py

# 과제

# [ CPU Emulator ] by Python

 어셈블리어를 공부하다가 어셈블리어를 외부로부터 읽어서 txt파일로 출력하는 프로그램이다.

import sys
readFile = open('homework_3.s', 'r')
writeFile = open('output.txt', 'w')
orig_stdout = sys.stdout
sys.stdout = writeFile

regi = {'%eax':0, '%ebx':0, '%ecx':0, '%edx':0, '%esi':0, '%edi':0,'%esp':0, '%ebp':0}
stack = []

def argToValue(arg):
    if (arg[0] == '%'):
        for k, v in regi.items():
            if (k == arg):
                return v
    if (arg[0:3] == "$0x"):
        return int(arg[1:],16)
    return int(arg[1:],10)

def movFunc(arg):
    regi[arg[1]] = argToValue(arg[0])
def subFunc(arg):
    regi[arg[1]] -= argToValue(arg[0])
def addFunc(arg):
    regi[arg[1]] += argToValue(arg[0])
def xorFunc(arg):
    regi[arg[1]] = argToValue(arg[0]) ^ argToValue(arg[1])
def pushFunc(arg):
    stack.append({argToValue('%esp'):argToValue(arg[0])})
    regi['%esp'] -= 4
def popFunc(arg):
    regi[arg[0]] = stack.pop().values()[0]
    regi['%esp'] += 4
def nopFunc(arg):
    pass
def retFunc(arg):
    pass

operator = dict( mov = movFunc, sub = subFunc, add = addFunc, xor = xorFunc, push = pushFunc, pop = popFunc, nop = nopFunc, ret = retFunc)

while 1:
    line = readFile.readline().replace(",","").split()
    if not line:
        break
    print "=========input========="
    print line
    operator[line[0]](line[1:])
    print "-------stack info------"
    for x in stack[::-1]:
        print x
    print "-----register info-----"
    for key, value in regi.items():
        print key, value

readFile.close()
writeFile.close()


sys.stdout = orig_stdout

# 실행결과

-INPUT

	mov	$1000, %esp
	push	%ebp
	mov	%esp, %ebp
	mov	$0, %eax
	mov	$0x0, %ebx
	xor	%esi, %esi
	xor	%edi, %edi
	xor	%ecx, %ecx
	mov	%ecx, %edx
        mov     $0x100, %eax
        mov     %eax, %ebx
        sub     $0x10, %ebx
        sub     $10, %ebx
	mov	%ebx, %edx
	push	%edx
	add	%edx, %edx
	push	%edx
	pop	%ebx
	xor	$0x10, %ebx
	mov	$0x200, %edx
	sub	$0x20, %edx
	add	%edx, %edx
	mov	$10, %eax
	sub	%eax, %edx		
	push	%edx
	pop	%ecx
        nop
	pop	%ebp
	ret

-OUTPUT

=========input=========
['mov', '$1000', '%esp']
-------stack info------
-----register info-----
%ebp 0
%eax 0
%edx 0
%edi 0
%esp 1000
%ebx 0
%esi 0
%ecx 0
=========input=========
['push', '%ebp']
-------stack info------
{1000: 0}
-----register info-----
%ebp 0
%eax 0
%edx 0
%edi 0
%esp 996
%ebx 0
%esi 0
%ecx 0
=========input=========
['mov', '%esp', '%ebp']
-------stack info------
{1000: 0}
-----register info-----
%ebp 996
%eax 0
%edx 0
%edi 0
%esp 996
%ebx 0
%esi 0
%ecx 0
=========input=========
['mov', '$0', '%eax']
-------stack info------
{1000: 0}
-----register info-----
%ebp 996
%eax 0
%edx 0
%edi 0
%esp 996
%ebx 0
%esi 0
%ecx 0
=========input=========
['mov', '$0x0', '%ebx']
-------stack info------
{1000: 0}
-----register info-----
%ebp 996
%eax 0
%edx 0
%edi 0
%esp 996
%ebx 0
%esi 0
%ecx 0
=========input=========
['xor', '%esi', '%esi']
-------stack info------
{1000: 0}
-----register info-----
%ebp 996
%eax 0
%edx 0
%edi 0
%esp 996
%ebx 0
%esi 0
%ecx 0
=========input=========
['xor', '%edi', '%edi']
-------stack info------
{1000: 0}
-----register info-----
%ebp 996
%eax 0
%edx 0
%edi 0
%esp 996
%ebx 0
%esi 0
%ecx 0
.........(생략)

cpu emulator.py

homework_3.s

output.txt