Seungil Kim
All tags

Posts tagged "union-find"

  • 백준 25402번 트리와 쿼리
    #union-find #cpp #ps #tree
    백준 25402번 트리와 쿼리 풀이. 쿼리마다 선택된 노드끼리만 유니온하며 연결된 컴포넌트 크기로 가능한 쌍의 수를 계산한다.
  • 백준 10775번 공항
    #union-find #cpp #ps
    백준 10775번 공항 풀이. 도킹 가능한 가장 큰 게이트를 유니온 파인드로 추적해 비행기를 최대한 많이 배치한다.
  • 백준 17398번 통신망 분할
    #union-find #cpp #ps
    백준 17398번 통신망 분할 풀이. 제거되지 않는 간선을 먼저 합치고, 끊은 간선을 역순으로 복구하며 분할 비용을 누적한다.
  • 백준 9938번 방 청소
    #union-find #cpp #ps #python
    백준 9938번 방 청소 풀이. 연결된 서랍 집합의 남은 공간 수를 루트에 저장해 각 술병을 보관할 수 있는지 빠르게 판단한다.
  • 백준 11085번 군사 이동
    #union-find #cpp #ps
    백준 11085번 군사 이동 풀이. 간선을 수용량 내림차순으로 연결하며 출발지와 도착지가 이어지는 순간의 최소 수용량을 찾는다.
  • 백준 14868번 문명
    #graph #union-find #cpp #ps
    백준 14868번 문명 풀이. BFS로 문명을 확장하고 인접한 문명을 유니온 파인드로 합치며 모두 연결되는 해를 찾는다.
  • 백준 3197번 백조의 호수
    #graph #union-find #cpp #ps
    백준 3197번 백조의 호수 풀이. 물 확산을 BFS로 진행하고 녹아 연결된 영역을 유니온 파인드로 묶어 백조가 만나는 날을 구한다.
  • 백준 2162번 선분 그룹
    #union-find #cpp #geometry #ps
    백준 2162번 선분 그룹 풀이. 선분 교차 판정과 유니온 파인드를 결합해 그룹 개수와 가장 큰 그룹 크기를 계산한다.
  • 백준 16562번 친구비
    #union-find #cpp #ps
    백준 16562번 친구비 풀이. 친구 관계를 유니온 파인드로 묶고 각 집합의 최소 친구비를 합산해 예산 가능 여부를 판단한다.
  • 백준 1717번 집합의 표현
    #union-find #cpp #ps
    백준 1717번 집합의 표현 풀이. 경로 압축을 사용하는 유니온 파인드의 union과 find 연산을 구현해 집합 포함 여부를 판정한다.
  • 백준 4195번 친구 네트워크
    #union-find #cpp #ps
    백준 4195번 친구 네트워크 풀이. 이름을 인덱스로 매핑하고 루트에 집합 크기를 저장하는 유니온 파인드로 네트워크 크기를 출력한다.