Notice
Recent Posts
Recent Comments
Link
| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 1 | 2 | |||||
| 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 10 | 11 | 12 | 13 | 14 | 15 | 16 |
| 17 | 18 | 19 | 20 | 21 | 22 | 23 |
| 24 | 25 | 26 | 27 | 28 | 29 | 30 |
| 31 |
Tags
- festify
- 레벨 햄버거
- 이미지삭제
- 최소지식원칙
- 삼성b형
- 13905
- 42서울 #개발 #대외활동
- gdg스터디
- 다이나믹 프로그래밍
- 도시 분할 계획
- 16974
- 브루트포스
- 자바
- 파사드패턴
- 삼성전자 dx 알고리즘 특강
- pushswap
- 16719
- 3967
- 이미지저장
- 최소 스패닝 트리
- 9465
- 백준
- 오늘의 문제
- 알고리즘특강
- 삼성전자dx
- 19951
- 분할정복
- 42서울
- 18869
- born2beroot
Archives
- Today
- Total
목록13905 (1)
그거 기능이에요
백준 13905 세부
문제 설명섬과 다리들이 있는 세부에서 숭이는 혜빈이의 위치까지 가려고 한다.각 다리마다 무게제한이 있는데 숭이는 혜빈이까지 최대 얼마의 무게를 지니고 도착할 수 있는지 구하여라문제 링크문제 접근a에서 b까지의 최소한의 간선을 지나는 것이므로 최소 스패닝 트리를 이용한 방식이다.모든 섬이 같은 그룹에 포함되는 순간 멈추는 것이 최소 스패닝 트리이므로, 이후 a에서 b까지 가려면 그 경로를 복원해서 사용하는 방식으로 접근하려고 했다.하지만 a와 b가 같은 그룹이 되는 순간의 간선의 가중치가 바로 최소 가중치가 되므로 그 구간에서 바로 출력 후 종료한다.그렇게 하기 위해 간선 정보를 간선의 가중치를 기준으로 내림차순으로 정렬한 후 유니온 파인드를 진행한다.마지막으로, a와 b가 같은 그룹이 되지 못하는 경우에..
백준/오늘의 문제
2025. 1. 2. 13:52