[백준 5214] 환승
문제 https://www.acmicpc.net/problem/5214 알고리즘 BFS 풀이 역들을 잇는 하이퍼튜브들이 주어질 때, $N$역으로 가기 위해 거쳐야하는 최소 역의 수를 구하는 문제입니다. 하이퍼튜브마다 일일이 역들을 연결하게 되면 메모리초과가 발생합니다. 대신에 하이퍼튜브마다 임의의 정점을 하나씩 만든 후, 각 역과 새로 만든 임의의 정점끼리 연결하여 메모리를 절약하였습니다. 위 그림은 문제에서 주어진 첫번째 예시에서 첫번째 하이퍼튜브와 두번째 하이퍼튜브를 시각화한 것입니다. 저는 튜브마다의 임의의 정점을 100005+$i$로 하였습니다. 검은 실선을 가중치 1로 설정하여 풀고난 후, 마지막에 반을 나누어 실제로 거친 역의 수를 구했습니다. 코드 #include #define rep(i, ..
Algorithm
2021. 6. 25. 16:48
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- dfs
- dijkstra
- 정렬
- string
- Segment tree
- spring
- kmp
- 펜윅트리
- Oracle
- SCC
- 이분매칭
- knapsack
- Fenwick
- 좌표압축
- 스위핑
- Suffix Array
- spring boot
- DP
- bfs
- 트라이
- 이분탐색
- hld
- sweeping
- 2-SAT
- union find
- implementation
- greedy
- 동적계획법
- 세그먼트트리
- sorting
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
글 보관함