티스토리 뷰
https://www.acmicpc.net/problem/15971
15971번: 두 로봇
2018년 강원도에서 새로운 동굴이 발견되었다. 이 동굴에는 총 N개의 넓은 방이 존재하며 좁은 통로로 서로 연결되어 있는 것으로 밝혀졌다. N개의 방은 1번부터 N번까지의 번호를 붙여 1번 방, 2번
www.acmicpc.net
설명을 보면 주어지는 그래프는 최소 스패닝 트리 (MST) 이다.
그렇다면 하나의 노드에서 다른 노드까지의 경로는 유일하다.
따라서 하나의 로봇에서 다른 로봇까지의 경로를 알아내고, 임의의 통로의 양 끝에 위치한 두 방들도 그 통로 위에 위치해 있다고 간주한다 라고 했으므로 경로중 가장 가중치가 큰 통로의 양끝에서 만나면 된다.
'PS' 카테고리의 다른 글
| 백준 10972. 다음 순열, 10973. 이전 순열 (0) | 2023.03.28 |
|---|---|
| 백준 13975. 파일 합치기 3 (0) | 2023.03.21 |
| 백준 21758. 꿀 따기 (0) | 2023.03.18 |
| 백준 1148. 단어 만들기 (0) | 2023.03.17 |
| 백준 15993. 1, 2, 3 더하기 8 (0) | 2023.03.16 |
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- graph
- C++
- greedy
- priority queue
- Implementation
- Kruskal
- Spring
- BFS
- dfs
- db
- back tracking
- floyd warshall
- Dijkstra
- Unity
- two pointer
- Tree
- Brute Force
- C
- permutation
- 조합
- CSS
- Stack
- 재귀
- Python
- recursion
- MVC
- binary search
- 자료구조
- 이분탐색
- DP
| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 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 |
글 보관함