최단거리 경로찾기, 다익스트라 알고리즘

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
·¬
roadMap={¬
····'home':{'hair':5,·'super':10,·'academy':9},¬
····'hair':{'home':5,·'super':3,·'bank':11},¬
····'super':{'home':10,·'hair':3,·'academy':7,·'restourant':3,'bank':10},¬
····'academy':{'home':9,'super':7,'bank':7,'school':12},¬
····'restourant':{'super':3,'bank':4},¬
····'bank':{'hair':11,'restourant':4,'super':10,'academy':7,'school':2},¬
····'school':{'bank':2,'academy':12}¬
}¬
###·fastWay={place:[visit,·lenth,·whereBefore]}¬
fastWay={}¬
for·i·in·roadMap.keys():¬
····fastWay[i]=[0,·99999999,·0]#{home:[1,·0,·home]¬
#print(fastWay)¬
¬
def·findNext():#place명으로·안에서·dic을·가공하는게·나을지도·->·함수·안에서·visit을·1로·하는게·이상적일듯·->·전체경로중·방문하지·않은·가장·작은걸·스캔하는거였음¬
····nextPlace='noWay'¬
····min=99999999¬
····for·i·in·fastWay.keys():¬
········if·fastWay.get(i)[0]==0·and·min·>·fastWay.get(i)[1]:¬
············nextPlace=i¬
············min=fastWay.get(i)[1]¬
····return·nextPlace¬
def·markingPath(place):#내가·어디서·왔는지도·써야하는데..·최초·시작점은·반복문·밖에·before을·0으로·하여·경로추적시·0에서·끝나게¬
····#fastWay.get(place)[2]=before¬
····for·i·in·roadMap.get(place).keys():#방문한곳엔·마킹하면·안됨,·기존에·있던·lenth보다·자기의·lenth+그곳으로·가는·lenth가·낮으면·마킹¬
········if·fastWay.get(i)[0]==0·and·fastWay.get(i)[1]·>·fastWay.get(place)[1]·+·roadMap.get(place).get(i):¬
············fastWay.get(i)[1]·=·fastWay.get(place)[1]·+·roadMap.get(place).get(i)¬
············fastWay.get(i)[2]·=·place¬
¬
#start='home'¬
start=input('시작점을·입력하세요·:·')¬
finish=input('도착점을·입력하세요·:·')¬
fastWay.get(start)[0]=1#최초·시작점·방문처리¬
fastWay.get(start)[1]=0#최초·시작점·거리0¬
fastWay.get(start)[2]='start'¬
markingPath(start)················#print()¬
¬
while·True:·············································#거리·마킹¬
····move·=·findNext()·#·다음·가야할곳은·hair¬
····if·move=='noWay':break¬
····fastWay.get(move)[0]=1#vist¬
····markingPath(move)¬
····#start=move¬
rootWay=[]¬
result=''¬
lenth=fastWay.get(finish)[1]¬
while·True:·············································#경로·작성¬
····if·finish=='start':break¬
····#print(finish)¬
····rootWay.append(finish)¬
····finish=fastWay.get(finish)[2]¬
#시작점에서·marking·path를·하고·전체중에·제일·짧은곳을·scan한다음(findNext)·다시·그곳에서·marking!¬
while·rootWay:¬
····result·+=·rootWay.pop()+'·'¬
¬
print('최단경로는·:·'·+·result·+·'·거리는·:·'·+·str(lenth))¬
print(fastWay)¬
¶
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

 

다익스트라 경로 찾기 알고리즘 장소와 거리가 주어진 트리에서 최단경로를 찾는 알고리즘.

 

처음엔 개념이 잘 이해안되서 다른 사람들이 코딩해놓은거 보다가 더 맨붕.

나중에 다시 볼때 읽기 쉽도록 dict형태 자료형으로 구현함.

 

기본적인 해결순서는 크게 전체 지도 roadMap과 방문정보, 소요거리정보, 이전place정보가 담겨있는 fastWay를 만듬

1.모든 place까지 가는 거리는 9999999(임의의 큰수)로 세팅 (집 -> 미용실 -> ?, 미용실 넘어 지도를 우리 눈으로 확인할 수 있지만 프로그램은 하나씩 탐색해봐야하기 때문에 무한하다고 가정하는것)

2.시작점에 나와있는 정보로 하나씩 방문하여 소요되는 거리를 기록, 시작점은(visit) 방문처리, 소요거리(lenth) 0처리

3.fastWay를 스캔하여(def fintNext) 방문하지 않은 곳(visit==0)중에 최단경로로 새로운 탐색을 시작(def markingPath)

4.반복

5.최종경로는 input받은 목적지를 통하여 역 추적하는 방식으로 구현 참조 : http://navercast.naver.com/contents.nhn?rid=2871&contents_id=85293

 

할일 - 코딩테스트 끝나면 설명 수정하고 그동안 알고리즘 문제 푼것 정리하기.