지하철 최단경로 알고리즘 - jihacheol choedangyeonglo algolijeum

최단 경로 알고리즘을 공부하다가 유튜브에서 좀 재밌게 만들어놓은 자료를 보고
이거 좀 재밌겠다 싶어서 찾아보았다

목차 Show

• 다익스트라 알고리즘
• 🚅 지하철 길찾기!!
• 변수 선언
• 함수 선언
• ✅결과!!
• +나중에 추가 할 부분!!

다익스트라 알고리즘

지하철 길찾기를 소개하기 전, 간단하게 내가 공부한 내용을 바탕으로 서론처럼 조금 끄적이자면...

다익스트라 알고리즘이란!!

한 꼭짓점으로부터 그래프의 다른 모든 꼭짓점까지의 최단경로를 찾는 알고리즘

출발 노드를 하나 정해놓고 그 노드로부터 다른 모든 노드들까지 최단경로를 찾는 알고리즘으로 최단 경로 트리를 만드는 것이다.

🚅 지하철 길찾기!!

암튼 이 다익스트라 알고리즘을 응용한 지하철에서 최단 경로를 나타내주는 프로그램을 간단하게 제작해보았다.

실제로 이렇게 다익스트라 알고리즘을 사용하여 동작하는 건지 궁금하기도해서 바로 따라해봤다

변수 선언

#노선 dict형으로 정리
line = {
    '1호선':1,
    '2호선':2,
    '3호선':3,
    '4호선':4,
    '5호선':5,
    '6호선':6,
    '7호선':7,
    '8호선':8,
    '9호선':9,
    '인천1호선':11,
    '인천2호선':12,
    '수인선':32,
    '서해선':31,
}

1호선부터 서해선까지 dict형으로 정리해놓는다

station = {
    '계양': [
        10000, 
        #출발지에서 계양에 도착까지 걸린 시간
        [
            ['부평구청', line['인천1호선'], 17]    
            #역 이름, 노선번호, 소요시간 
        ]
    ],
    '부평구청': [
        10000,
        [
            ['부평', line['인천1호선'], 3],
            ['온수', line['7호선'], 18],
            ['계양', line['인천1호선'], 17]
        ]
    ],
    '구로': [
        10000,
        [
            ['온수', line['1호선'], 10],
            ['가산디지털단지', line['1호선'], 5]
        ]
    ],
    .
    .
    .

너무 많아서 우선 3개만 예시로...ㅎ
station은 연결된 역을 저장해놓은 dict이다.

• `'계양': => dict에서 key를 표시
• 10000은 방문 여부를 표시해 줄 출발지에서 해당 역에 도착한 시간!!
• ['부평구청', line['인천1호선'], 17]는 각각 역 이름, 노선 번호, 이동 소요 시간을 나타낸다

이렇게 준비를 끝내놓고 search 알고리즘을 보자!!

함수 선언

def search(dir, stops, end, Line, time=0): 
    if station[stops][0] > time: 
        station[stops][0] = time  
        dir.append(stops)
    else:
        return '취소'
    
    if stops == end:
        print(time)
        print(dir)
        return '도착'


    for i in station[stops][1]: 
        trans = 0 if Line == i[1] else 5
        
        search(dir.copy(), i[0], end, i[1], i[2] + trans + time)

정리해보면

def search(dir, stops, end, Line, time=0):

def search ( 현재까지 지나온 경로 list, 현재 경유하고있는 역, 도착지, 현재 경유중인 노선 번호, 지금까지 걸린 시간 ):

이어서...

def search(dir, stops, end, Line, time=0): 

    if station[stops][0] > time: 
        station[stops][0] = time  
        dir.append(stops)
    else:
        return '취소'

if 현재 들어온 시간이 해당 station의 소요 시간보다 작은 경우
=> 해당 station의 소요 시간을 현재 들어온 시간으로 바꿔준다.

    if stops == end:
        print(time)
        print(dir)
        return '도착'

종료 조건 : if 현재 경유하는 역(stops)이 도착 station(end)과 같은 경우!!
=> 걸린 시간(time)과 거쳐온 경로(dir)를 표시해준다.

   
   
   for i in station[stops][1]: 
        trans = 0 if Line == i[1] else 5
        
        search(dir.copy(), i[0], end, i[1], i[2] + trans + time)

ex)
.
.
.
    '부평구청': [
        10000,
        [
          ['부평', line['인천1호선'], 3],
          ['온수', line['7호선'], 18],
          ['계양', line['인천1호선'], 17]
        ]
    ],
.
.
.

trans(환승시간) = 0 if Line == i[1] (같은 노선일 경우) else 5(다른 노선일 경우 환승시간은 5분으로 통일)

이후 재귀를 통해 다음 경로를 탐색한다.

search(중복 방지를 위한 dir.copy(), 경유지('부평'or'온수'or'계양'),도착지, i[2](이동시간) + trans(환승시간) + time(기존시간)

알고리즘의 로직은 이런식으로 돌아가고

실행

search([], '계양', '소사', line['인천1호선'])

✅결과!!

> 36
> ['계양', '부평구청', '부평', '소사']

이렇게 나온다.

유튜버님께서도 말씀하셨다시피 로직 자체는 간단하지만 그 로직을 생각해내기까지가 정말 어려운거같다...

+나중에 추가 할 부분!!

• 각 환승지점마다 환승 소요 시간을 다르게 넣어본다.
• UI까지 제작해서 간단하게 만들어 보변 재밌을 거 같기도 하다.
• 실시간 지하철 Open api를 받아서 동작시켜봐도 재밌을 거 같다.

유튜버 "파이썬클래스"님의 지하철 길찾기를 보면서 진행하였다.