[TIL] PATCH vs PUT, 0-1 BFS (동작방식 gif 포함!)

in TIL on Til, Algorithm Last modified at:

2025-04-21 TIL

📝 TIL (Today I Learned)
🔗 원본 이슈: #45
📅 작성일: 2025-04-21
🔄 최종 수정: 2025년 05월 02일

🍀 새롭게 배운 것

PUT과 PATCH의 차이

둘 다 리소스를 수정할 때 사용하는 HTTP 메서드이지만 차이점이 있다.

자세한 설명은 깃블로그 정리에 있습니다. (코드 예시, 비유 포함)

✅ 1. 기본 개념

항목PUTPATCH
전체 or 일부전체 대체일부만 수정
누락된 필드삭제될 수 있음무시하고 유지됨
멱등성(Idempotent)있음 (여러 번 해도 같은 결과)보장 X (실행 방식에 따라 달라질 수 있음)
용도새로운 리소스 생성 or 전체 업데이트부분 업데이트에 특화됨

✅ 2. 실무 팁

  • 클라이언트가 전체 데이터를 항상 알고 있고, 전체 리소스를 대체해야 할 경우 → PUT
  • 일부 필드만 수정할 때 → PATCH

0-1 BFS

코딩 테스트 준비를 하다가 0-1 BFS가 기본의 BFS와 어떤 점이 다른지 어떻게 해결해야하는지 잘 모르겠어서 정리를 해보았다.

✅ 1. 기본 개념

  • 0-1 BFS는 간선의 가중치가 0 또는 1인 경우에만 사용할 수 있다.

  • deque를 이용한다.

  • 일반 BFS는 queue를 사용하지만, 0-1 BFS는 deque를 사용
  • 간선의 가중치가 0인 경우 -> 덱의 앞에 넣음
  • 간선의 가중치가 1인 경우 -> 덱의 뒤에 넣음

    이렇게 하면 다익스트라처럼 우선순위를 정하지 않아도 자연스럽게 최단 경로가 먼저 탐색된다.

    항상 현재까지의 최단 거리가 가장 짧은 노드부터 처리된다.

  • 시간 복잡도는 O(V+E)로, 다익스트라 알고리즘(O(ElogV))보다 효율적이다.

✅ 2. 동작 원리

0-1 BFS 알고리즘은 다음과 같은 절차로 동작:

  1. 초기화: 시작 노드의 거리를 0으로, 나머지 노드의 거리를 무한대로 설정합니다. 시작 노드를 덱에 넣습니다.

  2. 반복 단계: 덱이 비어있지 않은 동안 다음을 반복합니다:

    • 덱의 앞에서 노드를 꺼냅니다.
    • 해당 노드의 모든 인접 노드에 대해:
      • 가중치가 0인 간선이면: 인접 노드의 거리를 업데이트하고 덱의 앞에 추가합니다.
      • 가중치가 1인 간선이면: 인접 노드의 거리를 업데이트하고 덱의 뒤에 추가합니다.

  3. 종료: 모든 노드에 대한 최단 거리가 계산됩니다.

✅ 3. 0-1 BFS의 응용 문제

0-1 BFS는 다음과 같은 상황에서 유용하게 사용된다:

  1. 가중치가 0 또는 1인 그래프에서의 최단 경로 찾기
  2. 격자(Grid) 기반 경로 찾기 문제 (특히 일부 이동에 비용이 없는 경우)
  3. 상태 전이 문제 (상태 간 이동 비용이 0 또는 1인 경우)

이 알고리즘을 사용하면 다익스트라 알고리즘보다 더 효율적으로 최단 경로를 찾을 수 있으며, 특히 가중치가 0과 1만 있는 그래프에서 O(V+E) 시간 복잡도로 동작하기 때문에 매우 빠르다.

✅ 4. 대표적인 문제

  • 백준 1261 - 알고스팟
    • 벽을 부수는 비용이 1, 안 부수는 건 0 → 0-1 BFS 사용
  • 백준 13549 - 숨바꼭질 3
    • 순간이동은 시간 0, 걷는 건 시간 1 → 0-1 BFS로 해결
  • LeetCode 847 - Shortest Path Visiting All Nodes (비트마스킹 + 0-1 BFS 가능)

✅ 5. 기본 예시 코드

import java.util.*;

public class ZeroOneBFS {
    static class Edge {
        int to, weight;
        public Edge(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }

    public static int[] zeroOneBFS(List<List<Edge>> graph, int start) {
        int n = graph.size();
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[start] = 0;

        Deque<Integer> deque = new ArrayDeque<>();
        deque.add(start);

        while (!deque.isEmpty()) {
            int node = deque.pollFirst();
            for (Edge edge : graph.get(node)) {
                int neighbor = edge.to;
                int weight = edge.weight;

                if (dist[neighbor] > dist[node] + weight) {
                    dist[neighbor] = dist[node] + weight;
                    if (weight == 0) {
                        deque.addFirst(neighbor);
                    } else {
                        deque.addLast(neighbor);
                    }
                }
            }
        }

        return dist;
    }

    public static void main(String[] args) {
        int n = 4; // 노드 개수
        List<List<Edge>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());

        // 예시 그래프 (0-based index)
        graph.get(0).add(new Edge(1, 0));
        graph.get(0).add(new Edge(3, 1));
        graph.get(1).add(new Edge(2, 1));
        graph.get(3).add(new Edge(2, 0));

        int[] dist = zeroOneBFS(graph, 0);

        System.out.println("최단 거리 배열: " + Arrays.toString(dist));
    }
}