728x90 BFS50 [Python] 백준 1967 트리의 지름 https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 문제 해결 - 간선에 가중치(거리)가 있다. - 부모 자식 관계는 중요하지 않다. 그냥 노드와 노드사이의 가중치 합이 큰 것을 찾아야 한다. - 제일 위에 있는 1에서 시작해서 가장 멀리 있는 것을 찾아본다. 이거는 BFS나 DFS 둘다 가능할 것이다. - 가장 멀리 있는 인덱스에서 다시 시작해서 가장 멀리 있는 노드까지 가중치(거리) 합을 구한다. 이 것이 정답. - 유사문제.. 2022. 12. 10. [Python]백준 1167 트리의 지름 https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 문제 해결 - graph 리스트를 통해 연결되어있는 점들의 정보를 저장한다. - visited[i] = value : 1점에서 i점까지 거리가 value인 것을 나타낸다. - 어느 점에서 시작하든 반대쪽 리프(맨 밑에 있는점)까지가 가장 멀기 때문에 한 점에서 가장 멀리 떨어져 있는 점을 구한다. visited.index(max(visited))를 통해 구한다. - 1점에서 반대쪽.. 2022. 12. 10. 이전 1 ··· 10 11 12 13 다음 728x90