TIL - DFS, 깊이 우선 탐색

문제

- DFS로 그래프를 탐색합니다.
- 깊이 방향으로 끝까지 탐색합니다.
- 재귀 또는 스택을 사용합니다.

 

 

문제풀이

def dfs(graph, start, visited=None):
    """
    깊이 우선 탐색 (재귀)
    
    Args:
        graph: 그래프 딕셔너리
        start: 현재 정점
        visited: 방문 리스트
    
    Returns:
        방문 순서 리스트
    """
    # 재귀 호출에서 비어있을 때 최초로 초기화 필
    if visited is None:
        visited = []
    
    visited.append(start)
    
    # [시작정점의 연결점 확인]
    for i in graph[start]:
        # [연결점이 방문하지 않았을 때]
        if i not in visited:
            # [재귀호출]
            dfs(graph, i, visited)
    
    return visited

 

 

깊이 우선 탐색 (DFS)

DFS 는 탐색의 방향을 깊이, 세로로 갖는 탐색을 의미한다. LIFO의 특징을 가진 자료구조 Stack을 사용하게 된다. 재귀로도 구현할 수 있다.

1. 시작 노드를 스택에 저장
2. 맨 앞의 값을 꺼냄
3. 꺼낸 값으로 문제에서 요구하는 연산을 수행
4. 인접 노드를 스택에 저장
5. 스택이 빌때까지 반복

 

DFS와 BFS는 서로 대체 가능하다.

TIL - BFS 너비 우선 탐색

 

 

 

 

어려웠던 점

1. 재귀의 리턴에 대해 리턴 값에 대해 논리적으로 사고하는게 어려웠다.
2. 스택으로 구현했을 때 순서가 다르게 나올 것 같았다.
   • 순서가 안 중요한 경우
     • 그래프가 연결되어있는지,
     • 몇 개의 컴포넌트로 나뉘는지,
     • 특정 노드에 도달 가능한지
   • 순서가 중요한 경우
     • 방문 순서를 출력하라,
     • 어떤 경로로 갔다가 되돌아왔는지,
     • 사전순으로 가장 빠른 경로 찾기,
     • 방문 순서에 따라 결과가 달라지는 계산
3. DFS 를 구현할 때 스택과 재귀의 차이점 
   1. 방문 순서
      
      1. 스택은 pop 할때 방문을 확인한다.  가장 마지막에 들어간게 가장 먼저 나옴. 
         1. 중복 방지는 push, pop 둘다에서 가능하다.
      2. 재귀와 순서를 동일하게 하려면 : reversed 사용 
   2. 명시적 스택
      1. 재귀 : 콜 스택을 암묵적으로 사용
      2. 반복 DFS : stack = [] 같은 자료구조를 직접 선언하고, push/pop을 코드로 직접 작성.
      3. 명시적 스택 : 프로그래밍 언어가 함수 호출할 때 자동으로 관리해주는 콜 스택이 아닌, 개발자가 코드에서 직접 만든 스택 자료구조 (리스트, collections.deque 등)
4. Python 에서 == 와 is 의 차이
   • is : 두 변수가 같은 객체를 가리키는지 (identity 비교)
     • 객체가 메모리에 할당될 때 고유한 식별자 값을 가진다.
     • is 는 내부적으로 id(a) == id(b) 와 동치이다. *id()는 객체의 메모리 주소 반환
     • a == b 는 실제로 a.__eq__(b) 를 호출한다. 
     • None, True, False 처럼 싱글턴임이 보장된 객체 비교에만 사용
   • == : 두 객체의 값이 같은지 (equality 비교)
     • 값 비교가 목적이면 사용 
     • Integer Caching
       • Python 에서는 정수가 미리 객체에 할당되어 있다. 
       • 범위 : -5부터 256까지의 정수