너비 우선 탐색(BFS, Breadth-First Search)
너비 우선 탐색이란
루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법
시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법이다.
즉, 깊게(deep) 탐색하기 전에 넓게(wide) 탐색하는 것이다.
사용하는 경우: 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 이 방법을 선택한다.
Ex) 지구상에 존재하는 모든 친구 관계를 그래프로 표현한 후 Ash와 Vanessa 사이에 존재하는 경로를 찾는 경우
깊이 우선 탐색의 경우 - 모든 친구 관계를 다 살펴봐야 할지도 모른다.
너비 우선 탐색의 경우 - Ash와 가까운 관계부터 탐색
너비 우선 탐색(BFS)이 깊이 우선 탐색(DFS)보다 좀 더 복잡하다.
너비 우선 탐색(BFS)의 특징
직관적이지 않은 면이 있다.
BFS는 시작 노드에서 시작해서 거리에 따라 단계별로 탐색한다고 볼 수 있다.
BFS는 재귀적으로 동작하지 않는다.
이 알고리즘을 구현할 때 가장 큰 차이점은, 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 한다는 것이다.
이를 검사하지 않을 경우 무한루프에 빠질 위험이 있다.
BFS는 방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용한다.
즉, 선입선출(FIFO) 원칙으로 탐색
일반적으로 큐를 이용해서 반복적 형태로 구현하는 것이 가장 잘 동작한다.
‘Prim’, ‘Dijkstra’ 알고리즘과 유사하다.
너비 우선 탐색(BFS)의 과정
깊이가 1인 모든 노드를 방문하고 나서 그 다음에는 깊이가 2인 모든 노드를, 그 다음에는 깊이가 3인 모든 노드를 방문하는 식으로 계속 방문하다가 더 이상 방문할 곳이 없으면 탐색을 마친다.
a 노드(시작 노드)를 방문한다. (방문한 노드 체크)
큐에 방문된 노드를 삽입(enqueue)한다.
초기 상태의 큐에는 시작 노드만이 저장
즉, a 노드의 이웃 노드를 모두 방문한 다음에 이웃의 이웃들을 방문한다.
큐에서 꺼낸 노드과 인접한 노드들을 모두 차례로 방문한다.
큐에서 꺼낸 노드를 방문한다.
큐에서 커낸 노드과 인접한 노드들을 모두 방문한다.
인접한 노드가 없다면 큐의 앞에서 노드를 꺼낸다(dequeue).
큐에 방문된 노드를 삽입(enqueue)한다.
큐가 소진될 때까지 계속한다.
https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html
[알고리즘] 너비 우선 탐색(BFS)이란 - Heee's Development Blog
Step by step goes a long way.
gmlwjd9405.github.io
bfs를 이용하여 부산지하철 노선도를 구현하고 기능을 넣을 것이다.
1. 도착지를 갈 때 얼마나 걸리는지
2. 환승역은 어디인지
3. 도착지 최소 경로
4. 출발지와 도착지의 중간지점
#subway_graph
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
텍스트 파일
부산 지하철 노선도를 각 호선마다 정리하여 txt파일에 저장을 하였다.
그리고 위 subway_ graph 소스코드를 이용하여 일반 텍스트파일을 가지고와서 역과 엣지를 만들어 주었다.
#main
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
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 함수"""
global res_str
res_str = "" # 리턴할 결과 문자열
temp = destination_node # 도착 노드에서 시작 노드까지 찾아가는 데 사용할 변수
# 시작 노드까지 갈 때까지
i = 0 #시간계산을 위한 코드
while temp is not None:
res_str = f"{temp.station_name} {res_str}" # 결과 문자열에 역 이름을 더하고
temp = temp.predecessor # temp를 다음 노드로 바꿔준다
i = i +1 #역을 하나씩 지날 때 마다 i값이 커짐
print("약",i*2,"분 소요예정(총",i,"개 역 경유)") #역 하나당 2분으로 계산
center = int(i/2)+1
global res_str1
res_str1 = "" # 리턴할 결과 문자열
temp = destination_node
for c in range(center):
res_str1 = temp.station_name
temp = temp.predecessor
return res_str
global res_str
global res_str1
res_str1 = '' #선언 및 초기화
res_str = ''
list = ["평강 대저 체육공원","체육공원 대저 평강","동구 대저 체육공원","체육공원 대저 동구","수정 덕천 숙등","숙등 덕천 수정","수정 덕천 구포","구포 덕천 수정","구포 덕천 구명","구명 덕천 구포","구명 덕천 숙등","숙등 덕천 구명","괘법르네시뗴 사상 감전","감전 사상 괘법르네시뗴","덕포 사상 괘법르네시뗴","괘법르네시뗴 사상 덕포","만덕 미남 동래","동래 미남 만덕","사직 미남 동래","동래 미남 사직","종합운동장 거제 교대","교대 거제 종합운동장","교대 거제 연산","연산 거제 교대","연산 거제 거제해맞이","거제해맞이 거제 연산","종합운동장 거제 거제해맞이","거제해맞이 거제 종합운동장","부전 서면 부암","부암 서면 부전","부전 서면 전포","전포 서면 부전","전포 서면 범내골","범내골 서면 전포","범내골 서면 부암","부암 서면 범내골","미남 동래 명륜","명륜 동래 미남","미남 동래 교대","교대 동래 미남","수안 동래 명륜","명륜 동래 수안","수안 동래 교대","교대 동래 수안","거제 교대 동래","동래 교대 거제","연산 교대 거제","거제 교대 연산","동래_동해선 교대 동래","동래 교대 동래_동해선","동래_동해선 교대 연산","연산 교대 동래_동해선","거제 연산 교대","교대 연산 거제","거제 연산 시청","시청 연산 거제","물만골 연산 교대","교대 연산 물만골","물만골 연산 시청","시청 연산 물만골","망미 수영 민락","민락 수영 망미","망미 수영 광안","광안 수영 망미","센텀시티 벡스코 센텀","센텀 벡스코 센텀시티","센텀시티 벡스코 신해운대","신해운대 벡스코 센텀시티","동백 벡스코 센텀","센텀 벡스코 동백","동백 벡스코 신해운대","신해운대 벡스코 동백"]
list_t = [] #환승역 리스트
stations = create_station_graph("./1.txt") # stations.txt 파일로 그래프를 만든다
start = input("출발역을 입력하시오. -> ")
end = input("도착역을 입력하시오. -> ")
while (start not in stations) or (end not in stations):
print("잘못된 값이 입력되었습니다. 다시 입력해 주세요.")
start = input("출발역을 입력하시오. -> ")
end = input("도착역을 입력하시오. -> ")
bfs(stations, stations[start]) # 지하철 그래프에서 start변수를 시작 노드로 bfs 실행
back_track(stations[end])
for i in range(len(list)):
if list[i] in res_str and "서면" in list[i]: #환승경유를 지나고 환승역이 포함
if "서면" not in list_t:
list_t.append("서면")
if list[i] in res_str and "대저" in list[i]:
if "대저" not in list_t:
list_t.append("대저")
if list[i] in res_str and "덕천" in list[i]:
if "덕천" not in list_t:
list_t.append("덕천")
if list[i] in res_str and "사상" in list[i]:
if "사상" not in list_t:
list_t.append("사상")
if list[i] in res_str and "미남" in list[i]:
if "미남" not in list_t:
list_t.append("미남")
if list[i] in res_str and "거제" in list[i]:
if "거제" not in list_t:
list_t.append("거제")
if list[i] in res_str and "동래" in list[i]:
if "동래" not in list_t:
list_t.append("동래")
if list[i] in res_str and "교대" in list[i]:
if "교대" not in list_t:
list_t.append("교대")
if list[i] in res_str and "연산" in list[i]:
if "연산" not in list_t:
list_t.append("연산")
if list[i] in res_str and "수영" in list[i]:
if "수영" not in list_t:
list_t.append("수영")
if list[i] in res_str and "벡스코" in list[i]:
if "벡스코" not in list_t:
list_t.append("벡스코")
print("환승역 =>", list_t)
print("[",start,"] 부터 [",end,"] 까지의 최단경로는 ->",res_str,"<- 입니다.") # start에서 end까지 최단 경로 출력
select = input("C = 중간지점 확인, R = 재시작, X = 종료 -> ")
while (select != 'X' and select != 'x'):
if select == 'r' or select == 'R' :
start = input("출발역을 입력하시오. -> ")
end = input("도착역을 입력하시오. -> ")
while (start not in stations) or (end not in stations):
print("잘못된 값이 입력되었습니다. 다시 입력해 주세요.")
start = input("출발역을 입력하시오. -> ")
end = input("도착역을 입력하시오. -> ")
list_t = [] #재실행 했을 때 다시 선언
bfs(stations, stations[start]) # 지하철 그래프에서 을지로3가역을 시작 노드로 bfs 실행
back_track(stations[end])
for i in range(len(list)):
if list[i] in res_str and "서면" in list[i]:
if "서면" not in list_t:
list_t.append("서면")
if list[i] in res_str and "대저" in list[i]:
if "대저" not in list_t:
list_t.append("대저")
if list[i] in res_str and "덕천" in list[i]:
if "덕천" not in list_t:
list_t.append("덕천")
if list[i] in res_str and "사상" in list[i]:
if "사상" not in list_t:
list_t.append("사상")
if list[i] in res_str and "미남" in list[i]:
if "미남" not in list_t:
list_t.append("미남")
if list[i] in res_str and "거제" in list[i]:
if "거제" not in list_t:
list_t.append("거제")
if list[i] in res_str and "동래" in list[i]:
if "동래" not in list_t:
list_t.append("동래")
if list[i] in res_str and "교대" in list[i]:
if "교대" not in list_t:
list_t.append("교대")
if list[i] in res_str and "연산" in list[i]:
if "연산" not in list_t:
list_t.append("연산")
if list[i] in res_str and "수영" in list[i]:
if "수영" not in list_t:
list_t.append("수영")
if list[i] in res_str and "벡스코" in list[i]:
if "벡스코" not in list_t:
list_t.append("벡스코")
print("환승역 =>", list_t)
print("[",start,"] 부터 [",end,"] 까지의 최단경로는 ->",res_str,"<- 입니다.")
elif select == 'c' or select == 'C':
print(start,"와",end,"사이의 중간지점은",res_str1 )
else :
print("입력이 잘못됨")
select = input("C = 중간지점 확인, R = 재시작, X = 종료 -> ")
print("프로그램 종료!")코드 설명
일단 모든 노드들을 false로 만들어주고 이전 노드도 None을 대입시켜준다.
저희가 출발할려는 노드는 false에서 true로 만들어주고
큐에다가 시작 노드를 추가해준다.
그리고 while문을 돌려서 큐에 노드가 남아있지 않을때까지 반복하는 반복문 하나를 만들었다.
현재 스테이션에다가 큐의 가장 앞 데이터를 뺴주면서 대입해준다. 그리고 현재 스테이션과 인접한 노드들을 방문하면서 방문하지 않은 노드를 만나면 방문 표시를 하고 현재 노드를 이전 노드로 만들어준다. 그리고 만들어둔 큐에다가 넣어준다.
예를 들어 bfs 서면을 하면 서면을 중심으로 모든 그래프가 그려지게 된다.
두 번째 함수에서 일단 도착노드를 정해준다. 그리고 리턴할 결과 문자열 하나와 도착노드에서 시작 노드까지 찾아가는데 사용할 변수 , 시간계산을 위한 변수 하나씩을 정의해준다.
그리고 temp변수가 None이 아닐 때 까지 반복문 하나를 써준다.
문자열 변수에 도착노드를 먼저 더해주고 temp변수에 도착노드의 이전 노드를 대입시켜준다. 이런식으로 반복하다가 시작노드를 만나면 시작노드의 이전노드는 없기 때문에 반복문이 멈춥니다. 그리고 반복될때마다 이전노드들의 문자열을 계속 더해주었기 때문에 도착노드부터 시작노드까지 거꾸러 찾아가는식으로 코드를 짜보았다.
그리고 역 하나씩 지날 때 마다 I 값이 커지고 역 하나당 2분으로 잡아서 총 소요시간을 계산하였다.
그리고 리스트 안에 환승이 가능한 모든경우를 문자열로 넣어두고 백트래킹 함수에서 리턴된 경유지 결과와 대조하여 지나가는 환승역이 있으면 그걸 환승역 리스트에 넣기 위해 빈 리스트 하나를 선언했다.
그리고 환승역 리스트를 출력하여 어디에서 환승이 되는지를 알 수 있게 해주었다.
간단한 반복문을 통해 역을 잘못입력하여 KeyError가 났을때를 대비하려 키 에러에 대한 예외처리를 한것과 같은 효과를 낼수있게 하였고 출발역과 도착역 입력후에 "중간지점 찾기", "재시작 하기", "종료하기" 등의 기능을 선택할 수 있도록 하였다.
함수를 실행시키고 지나가는 환승역을 환승역 리스트안에 추가해주고 출력시켜주게 하였다.
이 밑은 모든 출력이 끝나도 굳이 다시 실행시키지 않고 반복문을 통해 프로그램 종료되도록 해보았다.
#출력결과
