Skip to content

README.md

Latest commit

 

History

History
208 lines (156 loc) · 10.9 KB

README.md

File metadata and controls

208 lines (156 loc) · 10.9 KB

그래프 탐색 : graph traversal

  • 하나의 정점에서 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것

💠 그래프 문제 풀이 LOG

그래프 문제 풀이법 요약

유형 번호 문제 유형 핵심 질문 대표 알고리즘 대표 예시 문제 또는 상황
1️⃣ 경로 탐색 / 존재 여부 "갈 수 있나?", "경로가 존재하나?" DFS, BFS 둘 다 가능 미로 탈출 여부, 모든 경로 탐색, 싸이클 판별
2️⃣ 최단 거리 / 최소 비용 "가장 빠르게 / 싸게 가는 방법은?" BFS (무가중치), 다익스트라, 벨만포드, 플로이드-워셜 미로 최소 칸 수, 도로 이동 최소 시간, 환율 사기 탐지
3️⃣ 조건을 만족하는 모든 경로 찾기 "몇 가지 방법이 있나?", "경로 수는?" DFS + DP (Top-down), 위상정렬 + DP, 백트래킹 내리막길, 파이프 옮기기, DAG 경로 수 구하기
4️⃣ 구조 구성 / 연결성 판별 "이 구조가 가능한가?", "어떻게 구성할까?" 유니온 파인드, MST(크루스칼/프림), 위상정렬, 이분 매칭 친구 네트워크, 작업 순서, 팀 구성, 이분 그래프 확인

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

visited 리스트를 통해 방문한 노드 확인하기!

재귀 함수는 종료 조건이 가장 중요!!

  • 루트 노드에서 시작하여 다음 노드로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법

  • 넓게 탐색하기 전에 깊게 탐색하는 것

  • 모든 노드를 방문하고자 할 때 사용하는 방법

  • 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다. 안하면 무한루프에 빠질 수 있다.

  • 구현 방법

    • 재귀 (자기자신 호출, 순환 알고리즘)
    • 스택

  • 시간복잡도

    • DFS는 그래프(정점의 수: N, 간선의 수: E)의 모든 간선을 조회한다.
    • 인접 리스트로 표현된 그래프: O(N+E)
    • 인접 행렬로 표현된 그래프: O(N^2)

  • 예제 코드

# ↑, ←, →, ↓ 방향으로 이동하기 위한 y, x 변화값
dy = [-1, 0, 0, 1]
dx = [0, -1, 1, 0]


# DFS 함수: 현재 위치 (y, x)에서 시작해서 도착지 (R-1, C-1)에 도달할 수 있는지 확인
def dfs(grid, y, x, visited):
    if (y, x) == (R - 1, C - 1):  # 도착 지점에 도달하면 True 반환
        return True

    visited[x][y] = True  # 현재 위치를 방문 처리 (※ x, y 순서 주의)

    for i in range(4):  # 상하좌우 4방향으로 이동 시도
        ny, nx = y + dy[i], x + dx[i]  # 다음 위치 계산
        if 0 <= ny < R and 0 <= nx < C:  # 범위 내에 있고
            if not visited[ny][nx] and grid[ny][nx] == 0:  # 방문하지 않았고 이동 가능한 곳(0이면 길)
                if dfs(grid, ny, nx, visited):  # 다음 위치에서 도달 가능하다면 True 반환
                    return True
    return False  # 모든 경로를 다 가봤는데도 도달할 수 없으면 False


# DFS 탐색 시작 함수 (초기 세팅용)
def start_dfs(grid):
    visited = [[False] * C for _ in range(R)]  # 방문 여부를 저장할 2차원 배열
    return dfs(grid, 0, 0, visited)  # (0, 0)에서 시작

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

  • 루트 노드에서 시작하여 인접한 노드를 먼저 탐색하는 방법 (인접한 노드를 모두 방문한 후 )

  • 깊게 탐색하기 전에 넓게 탐색하는 것

  • DFS보다 좀 더 복잡

  • 두 노드 사이의 최단 경로 or 임의의 경로를 찾고 싶을 때 사용하는 방법

    • 최단 경로 : 그래프 리스트에 해당 목적지까지 도달하는데 걸린 횟수를 저장 -> 그 중 최댓값 == 최단 경로

  • 어떤 노드를 방문했었는지 여부를 반드시 검사해야 한다. 안하면 무한루프에 빠질 수 있다.

  • 구현 방법

    • 큐

  • 시간복잡도

    • 인접 리스트로 표현된 그래프: O(N+E)
    • 인접 행렬로 표현된 그래프: O(N^2)
    • 적은 수의 간선만 가지는 희소 그래프 (sparse graph)의 경우 인접 행렬보다 인접 리스트를 사용하는 것이 유리하다.

  • 예제 코드

from collections import deque  # BFS 구현을 위한 deque 사용

# ↑, ←, →, ↓ 방향으로 이동하기 위한 y, x 변화값
dy = [-1, 0, 0, 1]
dx = [0, -1, 1, 0]


# BFS 함수: (0, 0)에서 시작하여 (R-1, C-1)까지 도달 가능한지 여부 반환
def bfs(grid):
    visited = [[False] * C for _ in range(R)]  # 방문 여부를 저장하는 2차원 배열
    queue = deque()  # BFS 탐색용 큐
    queue.append((0, 0))  # 시작점 (0, 0) 삽입
    visited[0][0] = True  # 시작점 방문 처리

    while queue:
        y, x = queue.popleft()  # 현재 위치를 큐에서 꺼냄
        if (y, x) == (R - 1, C - 1):  # 도착지에 도달했으면 True 반환
            return True

        for i in range(4):  # 상하좌우 4방향 탐색
            ny, nx = y + dy[i], x + dx[i]  # 다음 위치 계산
            if 0 <= ny < R and 0 <= nx < C:  # 격자 범위 체크
                if not visited[ny][nx] and grid[ny][nx] == 0:  # 아직 방문하지 않았고 길(0)인 경우
                    visited[ny][nx] = True  # 방문 처리
                    queue.append((ny, nx))  # 다음 위치를 큐에 추가

    return False  # 큐가 빌 때까지 도달하지 못하면 False 반환 (도달 불가)

DFS 🆚 BFS

  • DFS가 BFS보다 좀 더 간단하다
  • 검색 속도 : DFS > BFS (DFS가 더 느리다)

DFS + DP (Top-down)

DFS+DP 적용 조건 설명
탐색 경로가 많다 모든 경로를 다 보면 지수 시간 소요
동일한 상태로 여러 번 도달 가능 예: (x, y) 위치에서 도달하는 경우가 중복됨
결과를 저장하고 재활용할 수 있다 상태를 식별할 수 있는 dp[x][y] 같은 DP 테이블이 존재해야 함 
# 방향 벡터: 상, 하, 좌, 우
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

dp = [[-1 for _ in range(C)] for _ in range(R)]


# DFS 함수 정의: (x, y)에서 목적지까지 갈 수 있는 경로 수 반환
def dfs(y, x):
    # 1. 기저 조건 (종료 조건)을 만족하는 경우 재귀 종료 후 반환
    if is_base_case(state):
        return base_value(state)  # 보통 0 또는 1 반환

    # 2. 이미 계산된 경로 수가 있다면 그대로 반환 (메모이제이션, 중복 계산 방지)
    if dp[y][x] != -1:
        return dp[y][x]

    # 3. 처음 계산하는 경우 → 초기화
    dp[y][x] = 0  # 초기화 (아직 경로 없음)

    # 4. 현재 위치에서 이동 가능한 경로 계산 (재귀)
    for i in range(4):  # 4방향 탐색
        ny = y + dy[i]
        nx = x + dx[i]
        if 0 <= ny < R and 0 <= nx < C:
            if (문제에서 지정한 경로의 조건):  # ex. 내리막길일 때만 이동
                # dp 배열 값 변경하기
                # 1. 더하기 (+) – 가능한 경로 수 / 경우의 수 누적 (ex. 몇 가지 방법이 있는지 세는 문제)
                dp[ny][nx] += dfs(ny, nx)
                # 2. 최댓값 / 최솟값 (max, min) – 최적 해 구하기 (ex. 여러 경로 중 최적의 결과를 선택해야 할 때 - 최대 or 최소)
                dp[ny][nx] = max(dp[y][x], dfs(ny, nx))
                # 3. 곱하기 (*) – 독립적인 선택의 경우의 수 조합 (ex. 분할 정복형 문제에서 두 부분이 독립적일 때)
                dp[ny][nx] *= dfs(ny, nx)

    return dp[y][x]  # 현재 위치에서 도달 가능한 전체 경로 수 반환

그래프 최단 경로 알고리즘

: 출발 노드에서 도착 노드까지의 최소 비용을 구하는 알고리즘

  • 다양한 문제 상황
  • 한 지점에서 다른 한 지점까지의 최단 경로
  • 한 지점에서 다른 모든 지점까지의 최단 경로
  • 모든 지점에서 다른 모든 지점까지의 최단 경로

1. 다익스트라 알고리즘

  • 한 노드에서 다른 모든 노드로 가는 최단 경로를 계산하는 알고리즘
  • 음의 간선이 없을 때 정상 동작한다.

탐색 과정

  1. 출발 노드를 설정한다.
  2. 최단 거리 테이블을 초기화한다. (1차원 배열. 출발 노드에서 모든 노드까지 가는데 드는 최소 비용을 저장하는 리스트)
  3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다.
  4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산해 최단 거리 테이블을 업데이트한다.
  5. 3~4번 과정을 반복한다.
  6. 다익스트라 알고리즘을 수행한 뒤에는 최단 거리 테이블에 시작 노드 ~ 각 노드 까지의 최단 거리 정보가 저장된다.
  • 구현 방법
    1. 2차원 배열을 통한 순차 탐색 O(N2)
    2. 우선순위 큐 O(E logV)

2. 벨만-포드 알고리즘

  • 음수 간선이 포함된 상황에서의 최단 거리 문제

3. 플로이드-워셜 알고리즘

  • 모든 노드에서 다른 모든 노드까지의 최단 거리 문제
  • 다익스트라 알고리즘과 마찬가지로 단계별로 거쳐 가는 노드를 기준으로 알고리즘을 수행한다. (+ 매 단계마다 방문하지 않은 노드 중에서 최단 거리를 갖는 노드를 찾는 과정은 필요하지 X )
  • 2차원 테이블에 최단 거리 정보를 저장. → DP

16637 브루트포스로 풀었는데 DFS로도 풀어보기!

  • 1967번 보충 설명

    • 루트 노드에서 가장 멀리 떨어진 노드 = 트리 지름의 끝점 중 하나

    • 나는 '2개의 끝점이 모두 리프 노드이다.' 까지만 생각했지만, '루트 노드에서 멀리 떨어진 노드는 무조건 트리의 지름을 이루는 점 중 하나이다.' 를 간과했다..

      (루트에서 가장 먼 노드를 u라고 하자. 만약 u가 지름의 끝점이 아니라면, 트리의 지름 경로는 u보다 더 멀리 떨어진 다른 노드를 포함해야 한다. 하지만 u는 루트에서 가장 멀리 떨어진 노드이기 때문에 u보다 더 먼 노드는 존재할 수 없다. 따라서 u는 반드시 지름의 끝점 중 하나가 된다.)

    • u에서 가장 멀리 떨어진 노드 = 지름의 다른 끝점

    • bfs가 많이 부족하다. 더 연습해야겠다!