반드시 알아야하는 알고리즘 top 8 - 7. 최단거리 알고리즘

반드시 알아야 하는 알고리즘 top 8

• 재귀 알고리즘 

• 이진 탐색 

• 순차 탐색

• 버블 정렬

• 삽입 정렬

• 탐욕 알고리즘

• 최단거리 알고리즘

• 몬테 카를로 알고리즘

최단거리 알고리즘 

• 최단거리 알고리즘은 한 지점에서 다른 지점까지의 최단거리를 구할때 사용하는 알고리즘 입니다. 이 알고리즘은 가장 적은 비용으로 해답에 도달하는 경로를 찾아내는 대부분의 문제에 응용될 수 있습니다. 때문에 실생활에도 깊게 녹아있습니다. 예들 들면 네비게이션이나, 큐브를 푸는 문제, 미로탐색 등 실용성이 매우 높은 알고리즘 이라고 할 수 있습니다. 영상을 보며 기본적인 알고리즘을 살펴보겠습니다.

최단거리 알고리즘 예제 

• 문제 : 집에서 학교까지 최단 거리는 얼마 일까요?

• 각 실선에 있는 숫자는 연결되어 있는 곳 간의 거리를 의미합니다.

• 거리 참고

• ['0.집','1.미용실','2.슈퍼마켓','3.영어학원','4.레스토랑','5.은행','6.학교']

• 집 - [0,5,10,9,999,999,999] 

• 미용실 - [5,0,3,999,999,11,999] 

• 슈퍼 - [10,3,0,7,3,10,999] 

• 학원 - [9,999,7,0,999,7,12]

• 레스토랑 - [999,999,3,999,0,4,999] 

• 은행 - [999,11,10,7,4,0,2] 

• 학교 - [999,999,999,12,999,2,0] 

최단거리 알고리즘 코드 : Python 

# 거리를 short 라는 list 에 삽입하는 부분

short = []

index = ['0.집','1.미용실','2.슈퍼마켓','3.영어학원','4.레스토랑','5.은행','6.학교']

short.append( [0,5,10,9,999,999,999] )

short.append( [5,0,3,999,999,11,999] )

short.append( [10,3,0,7,3,10,999] )

short.append( [9,999,7,0,999,7,12] )

short.append( [999,999,3,999,0,4,999] )

short.append( [999,11,10,7,4,0,2] )

short.append( [999,999,999,12,999,2,0] )

# 출발지, 도착지를 받았을 때 

         계산하기 쉽게 테이블을 변환하는 함수

def convert_table(short, n):

    for i in range(len(short)):

        short[i].insert(0,short[i].pop(n[0]))

        short[i].insert(len(short)-1, short[i].pop(n[1]))

    short.insert(0,short.pop(n[0]))

    short.insert(len(short)-1, short.pop(n[1]))    

    return short

# 변환된 테이블에서 최단거리를 계산하는 함수

def calc_table(short):

    for n in range(2,len(short)):

        for i in range(len(short)-n):

            temp = []

            for j in range(n):

                if j == (n-1):

                    temp.append(short[i+j+1][i])

                else:

                    temp.append(short[i+j+1][i]+short[i+n][i+j+1])

            short[i+n][i] = min(temp)        

            del temp        

    return short

# 시작점과 도착점 입력 받기 위한 텍스트 출력 부분

print(index)

print('시작점과 도착점을 공백으로 구분해서 입력해주세요. : ')

print('ex) 1 3')

# 시작점과 도착점 입력 받을 때 값 검사하는 부분

while True:

    try:

        i = sorted(list(map(int,input().split())))

        if i[0] < 0 or i[1] >= len(short) :

            raise ValueError

        break

    except ValueError:

        print('위치 인덱스를 잘못 입력했습니다. ')

# 실행부 - 시작점과 도착점이 같을 때 거리는 0, 다른 경우 계산

if index[i[0]] == index[i[1]]:

    distance = 0

else:

    short = convert_table(short, i)

    short = calc_table(short)

    [print(short[i]) for i in range(len(short))]

    distance = short[len(short)-1][0]

    

print('{} 과 {} 의 최단거리는 {} 입니다.'.format(index[i[0]], index[i[1]], distance))

• 위 코드의 실행 결과는 다음과 같습니다.

• 동영상과 코드 중 calc_table 함수를 비교해가며 살펴보며 차근차근 진행해나가면 쉽게 이해할 수 있습니다.

---

부족한 블로그에 방문해 주셔서 감사합니다.

잘못된 부분이나 질문이 있으시면 

댓글로 말씀해주세요.

금방 확인하고 피드백 드리겠습니다.

좋은 하루 되세요. ^^