코테 연습) 그래프탐색 알고리즘 : DFS/BFS(DFS)

 

 

그래프탐색 알고리즘 : DFS/BFS
- 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정

5. DFS(Depth-First Search)

- DFS는 깊이 우선 탐색이라고도 부르며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘

 - DFS는 스택 자료구조(혹은 재귀함수)를 이용

    1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.

    2. 스택의 최상단 노드에 방문하지 않은 안전한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리, 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다

    3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복

 

그래프를 준비해보면 (방문기준 : 문제에 따라 다르지만 지금은 문제에서 가장 많이 쓰이는 번호가 낮은 노드부터)

번호가 낮은 1번 노드부터 인접 노드는 2와3과 8이 있다

방문하지 않은 인접 노드 중 번호가 낮은 2번 노드부터

2번의 인접 노드 중 방문하지 않은 인접 노드인 7번노드 방문

7번의 인접 노드 중 방문하지 않은 인접 노드 중 번호가 낮은 노드인 6번 노드로 방문

 

이와같이 깊이 우선으롵 탐색 하기 때문에 그래프에서 가장 깊은부분을 탐색

이렇게 깊게 들어갔다가 더이상 방문하지 않은 노드가 없다면 스택에서 꺼내고 다시 반대방향으로 돌아가 깊게 들어간다

 

돌아온 7번노드에서 방문하지 않은 8번노드로 방문한다

 

위의 노드들을 방문 했을 때 탐색 순서는 그림과 같다

 

DFS 소스코드 예제

 

->입력창

# DFS 메서드 정의
def dfs (graph, v, visited):
    # 현재 노드를 방문 처리
    visited[v] = True
    print(v, end=' ')
    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)
# 각 노드가 연결된 정보를 표현(2차원 리스트)
graph = [
    [],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]

# 각 노드가 방문된 정보를 표현(1차원 리스트)
visited = [False] * 9

# 정의된 DFS 함수 호출
dfs(graph, 1, visited)

 

->출력창

C:\Users\admin\PycharmProjects\ML_EX\venv\Scripts\python.exe C:/Users/admin/PycharmProjects/ML_EX/study05.py
1 2 7 6 8 3 4 5 
종료 코드 0(으)로 완료된 프로세스

 

풀이)

# DFS 메서드 정의
def dfs (graph, v, visited): 

- 그래프와 방문처리 여부 아직 v는 뭔지모름
 

   # 현재 노드를 방문 처리
    visited[v] = True 

- 해당 노드 방문처리

 

    print(v, end=' ') 

- 방문했다는 의미로 해당노드에 번호 출력 end=' '는 개행하지 말고 띄어쓰기 후 다음거 출력

    # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
        if not visited[i]: 

- 만약에 노드가 즉 인접한 노드가 방문되지 않은 상태라면

 

            dfs(graph, i, visited) 

- 재귀함수를 이용해 방문 진행

 

 

# 각 노드가 연결된 정보를 표현(2차원 리스트)
graph = [
    [], # 리스트의 0번 인덱스는 비워둔다 그래프 문제는 보통 1번부터 시작하기 때문
    [2, 3, 8], # 1번 노드와 연결되어 있는 것은 2, 3, 8
    [1, 7], # 2번 노드와 연결되어 있는 것은 1, 7
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
]
- 인접 리스트 방식으로 그래프를 표현

 

# 각 노드가 방문된 정보를 표현(1차원 리스트)
visited = [False] * 9 

- 기본적으로 모든 값은 False값으로 초기화 할 수 있다 모든 노드를 방문하지 않은것 처럼 적용 (* 9는 노드의 개수(0~8노드))

# 정의된 DFS 함수 호출
dfs(graph, 1, visited)

- 1그래프에서 1번 노드부터 인접노드 방문

 

출처 / 유튜브 [동빈나 - (이코테2021) 이것이 취업을 위한 코딩 테스트다 with 파이썬]