일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- 파괴되지않은건물
- 큐
- 징검다리건너기
- 알고리즘
- 파이썬
- 거리두기확인하기
- 도넛과막대그래프
- 자물쇠와열쇠
- [1차]캐시
- 17404
- 섬연결하기
- 사이클게임
- 최단경로
- 구현
- 다익스트라
- RGB거리2
- 그래프탐색
- 이모티콘할인행사
- 프림알고리즘
- 두큐합같게만들기
- 벽부수고이동하기
- 백준
- 프로그래머스
- BFS
- 트리의지름
- 최소스패닝트리
- DP
- DFS
- javascript
- 위상정렬
- Today
- Total
블로그 이름 뭐로 하지
[알고리즘] 백준 1167 - 트리의 지름 본문
문제
https://www.acmicpc.net/problem/1167
1167번: 트리의 지름
트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지
www.acmicpc.net
풀이
트리니까 그래프 문제라고 생각했고 각 정점간의 최단거리를 찾는 다익스트라 알고리즘을 활용해서 각 정점에서 가장 먼 지점을 찾고, 그 먼 지점들 중 가장 먼 지점을 찾는 식으로 풀이를 했다. 그치만.. 시간 초과가 나더라 ㅎ
시간초과 풀이
from collections import deque
v = int(input())
answer = 0
graph = [[] for _ in range(v+1)]
for _ in range(v):
arr = list(map(int,input().split()))
v_num = arr[0]
new_arr = arr[1:-1]
for i in range(0,len(new_arr),2):
graph[v_num].append((new_arr[i],new_arr[i+1]))
def find_max(i):
global answer
visited = [0 for _ in range(v+1)]
q = deque()
for a in graph[i]:
q.append(a)
while q:
v_,c_ = q.pop()
if v_ != i and visited[v_] == 0 and c_ > max(visited):
visited[v_] = c_
for a in graph[v_]:
q.append((a[0],a[1]+c_))
answer = max(answer,max(visited))
for i in range(1,v+1):
find_max(i)
print(answer)
도저히 시간초과를 해결할 수 없을 것 같아서 풀이를 검색해봤는데 다들 똑같이 하는 말이
1. 임의의 노드에서 가장 먼 노드를 찾는다.
2. 1에서 찾은 노드에서 가장 먼 노드를 찾는다.
3. 그 때의 비용을 출력한다.
이렇게 하더라... 쩝 근데 나는 어떻게 임의의 노드에서 시작해서 또 다시 가장 먼 노드를 찾는 저 해답이 어떻게 가장 먼 노드를 찾을 수 있는건지 이해가 안 됐다.... 그러니까 우리는 어떻게 항상 임의의 노드에서 가장 끝인 노드를 찾을 수 있는건지.. 이해가 안 간거다.
트리의 지름을 검색해보니 이런 글이 있었다.
https://blogshine.tistory.com/111
[알고리즘] 트리의 지름 : Diameter of Tree
트리의 지름 이란? " data-ke-type="html"> HTML 삽입 미리보기할 수 없는 소스 트리의 지름은 두개의 말단노드간의 최장거리를 의미한다. 각각의 정점을 u, v 라고 한다면 이들간의 거리는 d(u, v) 라고 함
blogshine.tistory.com
설명을 정말 잘 적어두신 것 같다. 역이 모순임을 증명해서 우리가 항상 지름을 구할 수 있는지를 적어두셨는데, 저 일련의 과정은 이해가 갔지만 사실 내가 '트리의 지름'이라는 개념을 모르는 상태에서 이번 1167번 문제같은걸 마주했을 때 내가 스스로 고민하고 생각해서 바로 저 dfs 두번 돌리기 라는 해답을 낼 수 있을지는 모르겠다. ㅠ 음 내가 아직 잘 이해를 못한건지..
정답 코드
https://fre2-dom.tistory.com/233
[baekjoon] 백준 1167번(파이썬): 트리의 지름
문제 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다.
fre2-dom.tistory.com
import sys
sys.setrecursionlimit(10 ** 9)
# dfs 탐색
def dfs(x, y):
# 각 노드와 연결된 노드를 확인
for a, b in graph[x]:
# 탐색하지 않은 노드라면
if visited[a] == -1:
visited[a] = b + y # 탐색하기까지 걸린 간선의 거리로 초기화
dfs(a, b + y) # 재귀적으로 탐색
v = int(sys.stdin.readline())
# 각 노드의 연결된 정보를 트리로 표현
graph = [[] for _ in range(v + 1)]
for _ in range(v):
w = list(map(int, sys.stdin.readline().split()))
for j in range(1, len(w) - 2, 2):
graph[w[0]].append([w[j], w[j + 1]])
visited = [-1] * (v + 1) # 탐색 여부, 간선의 거리
visited[1] = 0
dfs(1, 0) # 1번 노드에서 dfs 탐색
start = visited.index(max(visited)) # 1번 노드에서 제일 먼 노드를 찾는다.
visited = [-1] * (v + 1)
visited[start] = 0
dfs(start, 0) # 1번 노드부터 가장 먼 노드에서 다시 제일 먼 노드를 찾는다.
# 트리의 지름 출력
print(max(visited))
'알고리즘' 카테고리의 다른 글
[알고리즘] 백준 1238 - 파티 (0) | 2024.01.02 |
---|---|
[알고리즘] 프로그래머스 - 기능개발 (0) | 2024.01.01 |
[알고리즘] 프로그래머스 - [1차] 다트 게임 (0) | 2023.12.30 |
[알고리즘] 프로그래머스 - 튜플 (0) | 2023.12.30 |
[알고리즘] 프로그래머스 - [1차] 캐시 (0) | 2023.12.30 |