문제 링크
https://www.acmicpc.net/problem/1167
문제 유형
DFS/BFS
🌈 문제
트리의 지름이란, 트리에서 임의의 두 점 사이의 거리 중 가장 긴 것을 말한다. 트리의 지름을 구하는 프로그램을 작성하시오.
입력
트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 매겨져 있다.
먼저 정점 번호가 주어지고, 이어서 연결된 간선의 정보를 의미하는 정수가 두 개씩 주어지는데, 하나는 정점번호, 다른 하나는 그 정점까지의 거리이다. 예를 들어 네 번째 줄의 경우 정점 3은 정점 1과 거리가 2인 간선으로 연결되어 있고, 정점 4와는 거리가 3인 간선으로 연결되어 있는 것을 보여준다. 각 줄의 마지막에는 -1이 입력으로 주어진다. 주어지는 거리는 모두 10,000 이하의 자연수이다.
5
1 3 2 -1
2 4 4 -1
3 1 2 4 3 -1
4 2 4 3 3 5 6 -1
5 4 6 -1출력
첫째 줄에 트리의 지름을 출력한다.
11💡 아이디어
다익스트라 알고리즘을 살짝 변형해서 모든 노드를 탐색해야 하므로 BFS를 약간 섞어서 풀어야 겠다는 생각이 들었다. 가중치가 있는 그래프이므로, 그 가중치에 대한 거리를 기록하는 배열이 하나 필요할 것이라고 생각하여 dist 배열에다가 만들어지고 있는 배열을 저장한다.
그리고 배열의 가장 큰 값이 지름이 될 것이고, 항상 1번 노드부터 검사한다는 보장이 없기 때문에 모든 노드를 시작점으로 한 BFS 함수를 돌려보아야 겠다는 생각을 했다.
질문에 나와 있는 모든 예제 코드는 정답을 맞추었으나 ..
자꾸 시간 초과가 발생했다.
시간 초과 나오는 것도 효율성 테스트에서 통과하지 못하기 때문에 그 원인을 분석하고 나의 코드를 개선해 보자.
👨💻 코드 작성
from collections import deque
V = int(input())
inputlist = []
maxnum = 0
dist = [0] * (V + 1)
adj = [[] for _ in range(V + 1)] #간선 정보 담을 곳
for _ in range(V):
inputlist = list(map(int, input().split()))
for i in range(1, len(inputlist) - 1, 2):
adj[inputlist[0]].append([inputlist[i], inputlist[i + 1]])
def BFS(k):
dist = [0] * (V + 1) #초기화
visited = [False] * (V + 1)
dist[k] = 0 #출발자 0으로 지정
queue = deque([[k, 0]]) #현재 노드 넣기
while queue: #큐가 빌 때까지 넣기
cur, cur_dist = queue.pop()
if visited[cur] == True:
continue
visited[cur] = True
for next, next_dist in adj[cur]:
if visited[next] == True:
continue
dist[next] = cur_dist + next_dist #다음 갱신
queue.append([next, dist[next]])
return dist
#모든 정점 돌면서 최대값 지정
for j in range(1, V + 1):
dist = BFS(j) #시작점 k로 지정
maxnum = max(max(dist), maxnum)
print(maxnum)내가 작성한 코드는 위와 같다. 들어올 수 있는 V의 정점 개수는 최대 100,000개이다. 만약에 V에 100,000개의 수가 들어오게 된다면 BFS 노드도 최대한 따지게 된다면 100,000번의 루프를 돌게 되고 최종적으로 100,000의 제곱의 수를 체크하게 된다.
이렇게 되면 2초라는 시간 초과가 훌쩍 넘어가기 때문에 문제의 의도에 맞는 코드를 작성했다고 할 수 없게 된다.
결론적으로 모든 노드를 하나하나 다 탐색하지 않아도 된다.
만약 BFS를 통하여 가장 멀리 있는 지름이라고 추측되는 노드를 구하게 되었다면, 해당 노드에서 bfs를 한번더 진행하여 검사한다는 느낌으로다가 시간을 훨~씬 단축시킬 수 있다. 결론적으로 모든 노드에 대한 검사는 진행하지 않아도 되는 것.
from collections import deque
V = int(input())
inputlist = []
maxnum = 0
dist = [0] * (V + 1)
adj = [[] for _ in range(V + 1)] #간선 정보 담을 곳
for _ in range(V):
inputlist = list(map(int, input().split()))
for i in range(1, len(inputlist) - 1, 2):
adj[inputlist[0]].append([inputlist[i], inputlist[i + 1]])
def BFS(k):
dist = [0] * (V + 1) #초기화
visited = [False] * (V + 1)
dist[k] = 0 #출발자 0으로 지정
queue = deque([[k, 0]]) #현재 노드 넣기
while queue: #큐가 빌 때까지 넣기
cur, cur_dist = queue.pop()
visited[cur] = True
for next, next_dist in adj[cur]:
if visited[next] == True:
continue
dist[next] = cur_dist + next_dist #다음 갱신
queue.append([next, dist[next]])
maxlist = [dist.index(max(dist)), max(dist)]
return maxlist
maxnode, maxdist = BFS(1) #시작점 k로 지정
maxnode, maxdist = BFS(maxnode)
print(maxdist)조금은 느리긴 하지만 최대라고 파악된 친구만..검사해주는 방식으로 코드를 개선했더니 드디어 맞을 수 있었다.
BFS와 다익스트라에 대한 기본적인 이해와 세팅으로 변형되는 문제 출제 방식을 잘 기억하고 해결해나갈 수 있도록 훈련해야 한다.
