최단 경로용 bfs의 각 단계는 아래와 같다.
큐에 아무 Node도 없을 때까지:
Node를 꺼낸다Node에 인접해 있는 Node들을 돌면서:
Node면:
Node로 표시한다predecessor 변수를 설정한다Node를 큐에 넣는다Node 클래스
class StationNode:
"""지하철 역을 나타내는 역"""
def __init__(self, station_name):
self.station_name = station_name
self.adjacent_stations = []
self.visited = False
self.predecessor = None
def add_connection(self, station):
"""파라미터로 받은 역과 엣지를 만들어주는 메소드"""
self.adjacent_stations.append(station)
station.adjacent_stations.append(self)
탐색용으로 사용할 때랑은 다르게 모든 Node는 이제 predecessor 변수를 저장해야 한다.
함수 bfs는 파라미터로 그래프 graph와 시작 Node, start_node를 받는다.
BFS 알고리즘을 실행하면서 그래프 안에서 시작 Node에서 갈 수 있는 모든 Node들을 방문 표시를 해주고 predecessor 변수를 설정한다.
predecessor는 그 Node를 방문하기 바로 직전의 Node라고 했던 거 기억나나?
bfs를 한 그래프 Node에 backtracking을 하면 최단 경로를 구할 수 있었다.
backtracking 함수도 같이 작성해보자.
함수 back_track은 최단 경로를 알고싶은 Node, 그러니까 최단 경로 상의 마지막 도착 Node destination_node를 파라미터로 받는다. 이 Node에서부터 시작해서, 매 Node의 predecessor 변수를 사용해 backtracking을 한다.
그리고 나서 시작점부터 도착점까지의 최단 경로를 문자열로 리턴한다.
을지로3가 을지로4가 동대문역사문화공원 신당 상왕십리 왕십리 마장 답십리 장한평 군자 아차산 광나루 천호 강동구청
main.py
from collections import deque
from subway_graph import *
# 코드를 추가하세요
def bfs(graph, start_node):
"""최단 경로용 bfs 함수"""
queue = deque() # 빈 큐 생성
# 모든 노드를 방문하지 않은 노드로 표시, 모든 predecessor는 None으로 초기화
for station_node in graph.values():
station_node.visited = False
station_node.predecessor = None
# 시작점 노드를 방문 표시한 후 큐에 넣어준다
start_node.visited = True
start_node.predecessor = None
queue.append(start_node)
while queue: # 큐에 노드가 있을 때까지
current_station = queue.popleft() # 큐의 가장 앞 데이터를 갖고 온다
for neighbor in current_station.adjacent_stations: # 인접한 노드를 돌면서
if not neighbor.visited: # 방문하지 않은 노드면
neighbor.visited = True # 방문 표시를 하고
neighbor.predecessor = current_station
queue.append(neighbor) # 큐에 넣는다
def back_track(destination_node):
"""최단 경로를 찾기 위한 back tracking 함수"""
res_str = "" # 리턴할 결과 문자열
while destination_node:
res_str = f"{destination_node.station_name} {res_str}"
destination_node = destination_node.predecessor
return res_str
stations = create_station_graph("./new_stations.txt") # stations.txt 파일로 그래프를 만든다
bfs(stations, stations["을지로3가"]) # 지하철 그래프에서 을지로3가역을 시작 노드로 bfs 실행
print(back_track(stations["강동구청"])) # 을지로3가에서 강동구청역까지 최단 경로 출력
subway_graph.py
class StationNode:
"""지하철 역을 나타내는 역"""
def __init__(self, station_name):
self.station_name = station_name
self.adjacent_stations = []
self.visited = False
def add_connection(self, station):
"""파라미터로 받은 역과 엣지를 만들어주는 메소드"""
self.adjacent_stations.append(station)
station.adjacent_stations.append(self)
def create_station_graph(input_file):
stations = {}
# 일반 텍스트 파일을 여는 코드
with open(input_file) as stations_raw_file:
for line in stations_raw_file: # 파일을 한 줄씩 받아온다
previous_station = None # 엣지를 저장하기 위한 변수
raw_data = line.strip().split("-")
for name in raw_data:
station_name = name.strip()
if station_name not in stations:
current_station = StationNode(station_name)
stations[station_name] = current_station
else:
current_station = stations[station_name]
if previous_station is not None:
current_station.add_connection(previous_station)
previous_station = current_station
return stations
new_stations.txt
소요산 - 동두천 - 보산 - 동두천중앙 - 지행 - 덕정 - 덕계 - 양주 - 녹양 - 가능 - 의정부 - 회룡 - 망월사 - 도봉산 - 도봉 - 방학 - 창동 - 녹천 - 월계 - 성북 - 석계 - 신이문 - 외대앞 - 회기 - 청량리 - 제기동 - 신설동 - 동묘앞 - 동대문 - 종로5가 - 종로3가 - 종각 - 시청 - 서울역 - 남영 - 용산 - 노량진 - 대방 - 신길 - 영등포 - 신도림 - 구로 - 구일 - 개봉 - 오류동 - 온수 - 역곡 - 소사 - 부천 - 중동 - 송내 - 부개 - 부평 - 백운 - 동암 - 간석 - 주안 - 도화 - 제물포 - 도원 - 동인천 - 인천 - 광명 - 가산디지털단지 - 독산 - 금천구청 - 석수 - 관악 - 안양 - 명학 - 금정 - 군포 - 당정 - 의왕 - 성균관대 - 화서 - 수원 - 세류 - 병점 - 세마 - 오산대 - 오산 - 진위 - 송탄 - 서정리 - 지제 - 평택 - 성환 - 직산 - 두정 - 천안 - 봉명 - 쌍용 - 아산 - 배방 - 온양온천 - 신창 - 서동탄
시청 - 을지로입구 - 을지로3가 - 을지로4가 - 동대문역사문화공원 - 신당 - 상왕십리 - 왕십리 - 한양대 - 뚝섬 - 성수 - 건대입구 - 구의 - 강변 - 잠실나루 - 잠실 - 신천 - 종합운동장 - 삼성 - 선릉 - 역삼 - 강남 - 교대 - 서초 - 방배 - 사당 - 낙성대 - 서울대입구 - 봉천 - 신림 - 신대방 - 구로디지털단지 - 대림 - 신도림 - 문래 - 영등포구청 - 당산 - 합정 - 홍대입구 - 신촌 - 이대 - 아현 - 충정로 - 시청
신도림 - 도림천 - 양천구청 - 신정네거리 - 까치산
신설동 - 용두 - 신답 - 용답 - 성수
대화 - 주엽 - 정발산 - 마두 - 백석 - 대곡 - 화정 - 원당 - 삼송 - 지축 - 구파발 - 연신내 - 불광 - 녹번 - 홍제 - 무악재 - 독립문 - 경복궁 - 안국 - 종로3가 - 을지로3가 - 충무로 - 동대입구 - 약수 - 금호 - 옥수 - 압구정 - 신사 - 잠원 - 고속터미널 - 교대 - 남부터미널 - 양재 - 매봉 - 도곡 - 대치 - 학여울 - 대청 - 일원 - 수서 - 가락시장 - 경찰병원 - 오금
당고개 - 상계 - 노원 - 창동 - 쌍문 - 수유 - 미아 - 미아삼거리 - 길음 - 성신여대입구 - 한성대입구 - 혜화 - 동대문 - 동대문역사문화공원 - 충무로 - 명동 - 회현 - 서울역 - 숙대입구 - 삼각지 - 신용산 - 이촌 - 동작 - 이수 - 사당 - 남태령 - 선바위 - 경마공원 - 대공원 - 과천 - 정부과천청사 - 인덕원 - 평촌 - 범계 - 금정 - 산본 - 수리산 - 대야미 - 반월 - 상록수 - 한대앞 - 중앙 - 고잔 - 공단 - 안산 - 신길온천 - 정왕 - 오이도
방화 - 개화산 - 김포공항 - 송정 - 마곡 - 발산 - 우장산 - 화곡 - 까치산 - 신정 - 목동 - 오목교 - 양평 - 영등포구청 - 영등포시장 - 신길 - 여의도 - 여의나루 - 마포 - 공덕 - 애오개 - 충정로 - 서대문 - 광화문 - 종로3가 - 을지로4가 - 동대문역사문화공원 - 청구 - 신금호 - 행당 - 왕십리 - 마장 - 답십리 - 장한평 - 군자 - 아차산 - 광나루 - 천호 - 강동 - 길동 - 굽은다리 - 명일 - 고덕 - 상일동 - 둔촌동 - 올림픽공원 - 방이 - 오금 - 개롱 - 거여 - 마천
응암 - 역촌 - 불광 - 독바위 - 연신내 - 구산 - 응암 - 새절 - 증산 - 디지털미디어시티 - 월드컵경기장 - 마포구청 - 망원 - 합정 - 상수 - 광흥창 - 대흥 - 공덕 - 효창공원앞 - 삼각지 - 녹사평 - 이태원 - 한강진 - 버티고개 - 약수 - 청구 - 신당 - 동묘앞 - 창신 - 보문 - 안암 - 고려대 - 월곡 - 상월곡 - 돌곶이 - 석계 - 태릉입구 - 화랑대 - 봉화산
장암 - 도봉산 - 수락산 - 마들 - 노원 - 중계 - 하계 - 공릉 - 태릉입구 - 먹골 - 중화 - 상봉 - 면목 - 사가정 - 용마산 - 중곡 - 군자 - 어린이대공원 - 건대입구 - 뚝섬유원지 - 청담 - 강남구청 - 학동 - 논현 - 반포 - 고속터미널 - 내방 - 이수 - 남성 - 숭실대입구 - 상도 - 장승배기 - 신대방삼거리 - 보라매 - 신풍 - 대림 - 남구로 - 가산디지털단지 - 철산 - 광명사거리 - 천왕 - 온수 - 까치울 - 부천종합운동장 - 춘의 - 신중동 - 부천시청 - 상동 - 삼산체육관 - 굴포천 - 부평구청
암사 - 천호 - 강동구청 - 몽촌토성 - 잠실 - 석촌 - 송파 - 가락시장 - 문정 - 장지 - 복정 - 산성 - 남한산성입구 - 단대오거리 - 신흥 - 수진 - 모란
개화 - 김포공항 - 공항시장 - 신방화 - 양천향교 - 가양 - 증미 - 등촌 - 염창 - 신목동 - 선유도 - 당산 - 국회의사당 - 여의도 - 샛강 - 노량진 - 노들 - 흑석 - 동작 - 구반포 - 신반포 - 고속터미널 - 사평 - 신논현 - 언주 - 선정릉 - 삼성중앙 - 봉은사 - 종합운동장
왕십리 - 서울숲 - 압구정로데오 - 강남구청 - 선정릉 - 선릉 - 한티 - 도곡 - 구룡 - 개포동 - 대모산입구 - 수서 - 복정 - 경원대 - 태평 - 모란 - 야탑 - 이매 - 서현 - 수내 - 정자 - 미금 - 오리 - 죽전 - 보정 - 구성 - 신갈 - 기흥 - 상갈 - 청명 - 영통 - 망포
용문 - 원덕 - 양평 - 오빈 - 아신 - 국수 - 신원 - 양수 - 운길산 - 팔당 - 도심 - 덕소 - 양정 - 도농 - 구리 - 양원 - 망우 - 상봉 - 중랑 - 회기 - 청량리 - 왕십리 - 응봉 - 옥수 - 한남 - 서빙고 - 이촌 - 용산 - 서울역 - 신촌 (경의중앙선) - 공덕 - 서강 - 홍대입구 - 가좌 - 디지털미디어시티 - 수색 - 화전 - 행신 - 능곡 - 대곡 - 곡산 - 백마 - 풍산 - 일산 - 탄현 - 운정 - 금릉 - 금촌 - 월롱 - 파주 - 문산
서울역 - 공덕 - 홍대입구 - 디지털미디어시티 - 김포공항 - 계양 - 검암 - 운서 - 공항화물청사 - 인천국제공항
계양 - 귤현 - 박촌 - 임학 - 계산 - 경인교대입구 - 작전 - 갈산 - 부평구청 - 부평시장 - 부평 - 동수 - 부평삼거리 - 간석오거리 - 인천시청 - 예술회관 - 인천터미널 - 문학경기장 - 선학 - 신연수 - 원인재 - 동춘 - 동막 - 캠퍼스타운 - 테크노파크 - 지식정보단지 - 인천대입구 - 센트럴파크 - 국제업무지구
상봉 - 망우 - 갈매 - 별내역 - 퇴계원 - 사릉 - 금곡 - 평내호평 - 마석 - 대성리 - 청평 - 상천 - 가평 - 굴봉산 - 백양리 - 강촌 - 김유정 - 남춘천 - 춘천
오이도 - 월곶 - 소래포구 - 인천논현 - 호구포 - 남동인더스파크 - 원인재 - 연수 - 송도
강남 - 양재 - 양재시민의숲 - 청계산입구 - 판교 - 정자
반석 - 지족 - 노은 - (대전)월드컵경기장 - (대전)현충원 - 구암 - 유성온천 - 갑천 - 월평 - 갈마 - 정부청사 - (대전)시청 - 탄방 - (대전)용문 - 오룡 - 서대전네거리 - 중구청 - 중앙로 - 대전역 - 대동 - (대전)신흥 - 판암