트리
-
[백준 BOJ/C++] 1240 노드사이의 거리알고리즘, 코딩테스트/알고리즘 문제풀이 2023. 9. 30. 02:07
1240번: 노드사이의 거리 간선정보를 입력받아 그래프의 최단거리를 구하는 문제다. 아주 기본에 가까운 문제라 최단거리 알고리즘의 기본기를 연습하기 좋은 문제라고 할 수 있다. 시작점과 끝점 여러개를 입력받아 거리를 구해야한다는 점과 문제 설명이 자세하지 않다는 점 정도가 고민해봐야할 부분이다. 문제 설명이 아주 간단한데 말 그대로 주어진 그래프에서 특정 두 노드의 거리를 구해주면 된다. 두 노드 사이의 간선에 방향성이 있는지, 여러개의 간선이 같은 두 노드 사이에 존재할 수 있는지 등 일반적인 그래프 탐색 문제에서 주어지는 설명은 한마디로 압축하고있다. 트리는 두 노드 사이에 간선이 하나만 존재하며 간선에 방향이 존재하지 않는다. 또한 트리는 사이클이 없는 그래프일 뿐이므로 BFS나 DFS와 같은 그래..