[Algorithm] 깊이/너비 우선 탐색 (DFS/BFS)

DFS (Depth First Search) : 깊이 우선 탐색

▽ DFS 알고리즘 (코드블럭을 한글로 표현)

    시작 노드를 옅은 회색 표시 후, 스택에 넣음

    스택에 아무 노드가 없을 때까지:

        스택 가장 위 노드를 꺼낸다

        노드를 방문 (진한 회색) 표시한다

        인접한 노드들을 모두 보면서:

            처음 방문하거나 스택에 없는 노드면:

                옅은 회색 표시를 해준다

                스택에 넣어준다

 

 

▽ DFS로 연결된 역 찾기

from collections import deque


def dfs(graph, start_node):
    """dfs 함수"""
    stack = deque()  # 빈 스택 생성

    # 모든 노드를 처음 보는 노드로 초기화
    for station_node in graph.values():
        station_node.visited = 0

    start_node.visited = 1    # 시작 노드를 스택에 넣는다는 표시(옅은 회색)를 하고
    stack.append(start_node)  # 스택에 넣습니다

    while stack:                        # 스택에 노드가 남아 있을 때까지
        current_node = stack.pop()      # 스택 가장 위(뒤) 데이터를 갖고 온다
        current_node.visited = 2        # 현재 노드를 방문 표시한다
        for neighbor in current_node.adjacent_stations:
            if neighbor.visited == 0:   # 처음 보는 노드들만
                neighbor.visited = 1    # 스택에 넣는다는 표시를 하고
                stack.append(neighbor)  # 스택에 넣습니다

[테스트 코드]

stations = create_station_graph("./new_stations.txt")  # stations.txt 파일로 그래프를 만든다

gangnam_station = stations["강남"]

# 강남역과 경로를 통해 연결된 모든 노드를 탐색
dfs(stations, gangnam_station)

# 강남역과 서울 지하철 역들 연결됐는지 확인
print(stations["강동구청"].visited)
print(stations["평촌"].visited)
print(stations["송도"].visited)
print(stations["개화산"].visited)

# 강남역과 대전 지하철 역들 연결됐는지 확인
print(stations["반석"].visited)
print(stations["지족"].visited)
print(stations["노은"].visited)
print(stations["(대전)신흥"].visited)

 

< subway_graph.py - 공통사용코드 >

class StationNode:
    """간단한 지하철 역 노드 클래스"""
    def __init__(self, station_name):
        self.station_name = station_name
        self.visited = 0  # 한 번도 본적 없을 때: 0, 스택에 있을 때: 1, 발견된 상태: 2
        self.adjacent_stations = []


    def add_connection(self, other_station):
        """지하철 역 노드 사이 엣지 저장하기"""
        self.adjacent_stations.append(other_station)
        other_station.adjacent_stations.append(self)


def create_station_graph(input_file):
    """input_file에서 데이터를 읽어 와서 지하철 그래프 노드들을 리턴하는 함수"""
    stations = {}  # 지하철 역 노드들을 담을 딕셔너리

    # 파라미터로 받은 input_file 파일을 연다
    with open(input_file) as stations_raw_file:
        for line in stations_raw_file:             # 파일을 한 줄씩 받아온다
            previous_station = None                # 엣지를 저장하기 위한 도우미 변수. 현재 보고 있는 역 전 역을 저장한다
            subway_line = line.strip().split("-")  # 앞 뒤 띄어쓰기를 없애고 "-"를 기준점으로 데이터를 나눈다

            for name in subway_line:
                station_name = name.strip()  # 앞 뒤 띄어쓰기 없애기

                # 지하철 역 이름이 이미 저장한 key 인지 확인
                if station_name not in stations:
                    current_station = StationNode(station_name)  # 새로운 인스턴스를 생성하고
                    stations[station_name] = current_station     # dictionary에 역 이름은 key로, 역 인스턴스를 value로 저장한다

                else:
                    current_station = stations[station_name]      # 이미 저장한 역이면 stations에서 역 인스턴스를 갖고 온다

                if previous_station is not None:
                    current_station.add_connection(previous_station)  # 현재 역과 전 역의 엣지를 연결한다

                previous_station = current_station  # 현재 역을 전 역으로 저장

    return stations

 

 

 

BFS (Breadth First Seach) : 너비 우선 탐색

▽ BFS 알고리즘 (코드블럭을 한글로 표현한 순서)

    시작 노드를 방문 표시 후 큐에 넣음

    큐에 아무 노드가 없을 때까지:

        큐 가장 앞 노드를 꺼낸다.

        꺼낸 노드에 인접한 노드들을 모두 보면서:

            처음 방문한 노드면:

                방문한 노드 표시를 해준다

                큐에 넣어준다

 

▽ BFS로 연결된 역 찾기.

def bfs(graph, start_node):
    """시작 노드에서 bfs를 실행하는 함수"""
    queue = deque()  # 빈 큐 생성

    # 모든 노드를 방문하지 않은 노드로 표시
    for station_node in graph.values():
        station_node.visited = False

    # 시작점 노드를 방문 표시한 후 큐에 넣어준다
    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                     # 방문 표시를 하고
                queue.append(neighbor)                      # 큐에 넣는다

[ 테스트 코드 ]

# 강남역과 경로를 통해 연결된 모든 노드를 탐색
bfs(stations, gangnam_station)

# 강남역과 서울 지하철 역들이 연결됐는지 확인
print(stations["강동구청"].visited)
print(stations["평촌"].visited)
print(stations["송도"].visited)
print(stations["개화산"].visited)

# 강남역과 대전 지하철 역들이 연결됐는지 확인
print(stations["반석"].visited)
print(stations["지족"].visited)
print(stations["노은"].visited)
print(stations["(대전)신흥"].visited)

 

 

 

▷ 최단 경로용 BFS

    시작 노드를 방문 표시 후, 큐에 넣음

    큐에 아무 노드가 없을 때까지:

        큐 가장 앞 노드를 꺼낸다

        꺼낸 노드에 인접한 노드들을 모두 보면서:

            처음 방문한 노드면:

                방문한 노드 표시를 해준다

                predecessor 변수를 큐에서 꺼낸 노드로 설정

                큐에 넣어준다

 

 

[ BFS 최단거리용으로 바꾸기]

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 함수"""
    res_str = ""              # 리턴할 결과 문자열
    temp = destination_node   # 도착 노드에서 시작 노드까지 찾아가는 데 사용할 변수

    # 시작 노드까지 갈 때까지
    while temp is not None:
        res_str = f"{temp.station_name} {res_str}"  # 결과 문자열에 역 이름을 더하고
        temp = temp.predecessor                     # temp를 다음 노드로 바꿔준다

    return res_str