얼마만에 코테인지 ㅋ

크리스마스날 뭐하는건지 ㅋㅋㅋㅋ 알고리즘 수업을 이번학기에 듣길 잘한건가 ..  일단 좋은 결과를 기원하며 ㅋㅋㅋㅋ

---

아래 문제내용이? 보이면 일단 머릿속에 떠올려야 하니까 적어본다.

 

• shortest path/distance -> BFS/다익스트라 알고리즘
• minimum steps/moves -> BFS
• maximum/minimum value -> DP나 그리디
• all possible combinations -> DFS/백트래킹
• consecutive/sequential -> 투 포인터/슬라이딩 윈도우
• optimal/maximize/minimize -> DP나 그리디
• grid/matrix/2D array -> BFS/DFS/DP

BFS

• queue를 사용한다. 최단 경로 찾기에 적합하다. 레벨단위로 탐색이 필요할때 적합하다. 주변부터 차례대로 탐색해야 할때 적합하다. 즉 미로찾기에서 최단거리를 찾아야 하면 BFS가 적합하다. (가능한 모든 경로를 찾아야 하면 DFS)

• visted는 무한루프를 방지하기 위해 필요하다. 즉 이전 위치로 다시 돌아갈수도 있기 때문이다. 그래서 같은 위치를 중복해서 방문하지 않아야 무한루프를 방지 할수있다. 

def find_shortest_path(self, grid, start, goal):
    """
    최단경로를 구하는 문제로 BFS
    :param grid:
    :param start:
    :param goal:
    :return:
    """
    if not grid or not grid[0]:
        return -1

    n = len(grid)
    visited = set() ## 방문한 좌표를 저장할 집합
    queue = deque([(start[0], start[1], 0)])  # (행, 열, 거리)를 저장하는 큐

    # 상하좌우 이동을 위한 방향 벡터
    directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
    # 상하좌우 이동을 따로 뺴지 않고 아래처럼 해도 되고
    # for nx, ny in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:

    while queue:
        row, col, dist = queue.popleft()    ## 현재 위치와 이동 거리
        print(f"current = {row}, {col}, {dist}")

        if (row, col) == goal:  ## 목표 지점 도달
            return dist

        for dx, dy in directions:
            new_row, new_col = row + dx, col + dy

            # 1. 그리드 범위 내에 있는지
            # 2. 장애물이 없는지 (값이 0인지)
            # 3. 아직 방문하지 않은 위치인지 확인
            if (0 <= new_row < n and  # 그리드 범위 체크
                    0 <= new_col < n and  # 그리드 범위 체크
                    grid[new_row][new_col] == 0 and  # 장애물 체크
                    (new_row, new_col) not in visited):  # 방문 여부 체크

                visited.add((new_row, new_col))         ## 방문 처리
                moved_dist = dist + 1
                print(f"moved = {new_row}, {new_col}, {moved_dist}")
                queue.append((new_row, new_col, moved_dist))  ## 큐에 새 위치 추가

    return -1       ## 경로를 찾지 못한 경우

다익스트라 알고리즘

• 가중치가 있는 그래프에서 최단 경로를 찾을때 사용한다. BFS와 차이점은 간선의 가중치이다.
• BFS는 모든 간선의 가중치가 1이라고 보면되고, 다익스트라알고리즘은 간선마다 가중치가 다를때라고 생각하면 된다.
• 우선순위큐
  • 현재까지의 비용이 가장 적은 경로부터 먼저 탐색하기 위해서다.
  • 즉 항상 현재까지 발견된 경로 중 비용이 가장 적은 것부터 탐색 하는거다. 최적 경로를 더 빨리 찾을수 있다.
  • 파이썬에 heapq는 최소 힙으로 구현되어 있어서 자동으로 비용이 가장 작은 경로부터 꺼내준다.

def find_min_cost_path(self, grid, start, goal):
    rows, cols = len(grid), len(grid[0])

    # 거리를 무한대로 초기화한다. 이유는 도달 불가능상태로 시작하기 위해서이다.
    distances = [[float('inf')] * cols for _ in range(rows)]
    distances[start[0]][start[1]] = grid[start[0]][start[1]] # 시작점 초기화한다. 시작점의 비용은 그 칸의 값으로 설정한다.

    # (비용, x, y) 형태로 우선순위 큐에 저장
    cost = grid[start[0]][start[1]]
    x_position = start[0]
    y_position = start[1]
    pq = [(cost, x_position, y_position)] # 우선순위 큐 초기화한다.

    while pq:
        current_cost, x, y = heapq.heappop(pq) # 우선순위 큐 heapq가 비용이 가장 적은 경로부터 꺼내준다.

        # 목표 도달
        if (x, y) == goal:
            return current_cost

        # 현재 위치가 이미 알고있는 최단거리보다 크면 스킵
        if current_cost > distances[x][y]:
            continue

        # 상하좌우 탐색
        for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
            nx, ny = x + dx, y + dy

            if 0 <= nx < rows and 0 <= ny < cols:
                # 새로운 비용 = 현재까지의 비용 + 다음 칸의 비용
                new_cost = current_cost + grid[nx][ny]

                # 더 적은 비용으로 갈 수 있다면 업데이트
                if new_cost < distances[nx][ny]:
                    distances[nx][ny] = new_cost
                    heapq.heappush(pq, (new_cost, nx, ny))

    return -1  # 도달 불가능

def test_dijkstra(self):
    """
    [문제] 가중치가 있는 미로에서 최단경로 찾기
    격자의 각 칸에는 이동하는데 필요한 비용이 적혀있습니다.
    시작점에서 목표점까지 가는데 필요한 최소 비용을 구하세요.

    입력:
    grid = [
        [1, 3, 1, 2],
        [2, 1, 4, 1],
        [1, 3, 1, 1],
        [3, 1, 2, 1]
    ]
    start = (0, 0)
    goal = (3, 3)

    출력: 7 (최소 비용)
    :return:
    """
    # 테스트
    grid = [
        [1, 3, 1, 2],
        [2, 1, 4, 1],
        [1, 3, 1, 1],
        [3, 1, 2, 1]
    ]
    start = (0,0)
    goal = (3,3)
    result = self.find_min_cost_path(grid, start, goal)
    print(f"최소 비용: {result}")

---

maximum/minimum value -> DP나 그리디

• DP는 중복되는 부분을 제거할때 = 같은 계산이 여러번 반복될때 즉 피보나치수열을 계산할때 DP알고리즘이 적합하다. 큰 문제의 최적해가 작은 문제의 최적의 해로 구성될때(최단경로문제) 적합하다.
  • BFS도 최소우선순위큐를 이용해 최단경로와 같은 문제를 풀수 있는데 차이점은
    • 모든 간선의 가중치가 동일할때
    • 최소 단계 수를 구할때
    • 시작점에서 목표점까지 가는 최단 횟수 를 구할때 BFS가 적합하다.
  • DP가 적합할때는 --> 그렇다. 다익스트라 알고리즘은 DP의 원리를 활용한 최단 경로 알고리즘이다.
    • 간선의 가중치가 다를때
    • 경로의 비용의 합이 중요할때
    • 최적의 값을 구해야 할때
      • 최적 부분 구조
        • DP의 핵심 특성인 '큰문제의 최적해가 작은 문제의 최적해로 구성됨' 을 만족 한다는 것은 A->C의 최단 경로가 A->B->C라면, A->B 구간도 최단경로여야 한다.
      • 중복되는 부분문제
        • 여러 경로에서 같은 중간 노드를 방문 = 이미 계산한 최단거리를 재활용하는것을 말한다.
  • DP vs 다익스트라
    • DP는 모든 상태를 순차적으로 계산한다.
    • 다익스트라는 최소우선순위큐를 사용해 가장 적은 값을 선택하는 방식이다