티스토리 뷰
https://www.acmicpc.net/problem/1240
1240번: 노드사이의 거리
N(2≤N≤1,000)개의 노드로 이루어진 트리가 주어지고 M(M≤1,000)개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라.
www.acmicpc.net
트리라는 것은 사이클이 없기 때문에 두 노드 사이의 경로는 유일하다.
착각하고 플로이드 와샬로 풀었는데 맞았다..?
노드의 최대 갯수가 1000개라서 시간초과 나올줄 알았는데 통과되버렸다.
문제의 테스트케이스가 잘못됐거나 내가 모르는 플로이드 와샬에서 시간이 단축되는 경우가 있는것 같은데..아마 전자같다.
플로이드 와샬로 풀지 않는다면 그냥 bfs 나 dfs 로 일일히 세어보면 될것이다.
'PS' 카테고리의 다른 글
| 백준 2696. 중앙값 구하기 (0) | 2023.03.16 |
|---|---|
| 백준 16120. PPAP (0) | 2023.03.16 |
| 백준 3067. Coins (0) | 2023.02.28 |
| 백준 16398. 행성 연결 (0) | 2023.02.28 |
| 백준 4256. 트리 (0) | 2023.02.28 |
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- Kruskal
- dfs
- C++
- CSS
- DP
- Implementation
- Unity
- permutation
- 재귀
- recursion
- back tracking
- binary search
- 자료구조
- two pointer
- Python
- BFS
- 이분탐색
- priority queue
- Brute Force
- Spring
- Stack
- Tree
- C
- MVC
- floyd warshall
- graph
- 조합
- db
- greedy
- Dijkstra
| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 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 |
글 보관함