[백준] 1167 트리의 지름

백준 1167 트리의 지름

그래프 / 트리 / 파이썬

 

 

 

ㅠㅠㅠㅠ.. 매우 유사한 '1967번 트리의 지름'문제는 이 문제와 같은 방법으로 풀었는데 이건 도저히 풀리지가 않았다...

몇번이나 고치고 고치고 했는지

풀면서 왜틀리지 했지만 역시 컴퓨터가 옳았다.ㅋㅋ

생각보다 시간제한이 힘들었고 예제가 하나뿐이라 이유를 찾기에 좀 힘들었던 문제다.

 

스터디할때 결국 풀지못했는데 2일이 지난 후 혼자해보다가 풀게되었다.

역시 카페가 공부잘되는 듯ㅎㅎ

 

 

 

 

[문제]

 

 

 

1967번이랑 문제가 같은데 제시된 입력부분이 다름을 확인

알고리즘은 그대로 bfs를 사용함

 

 

 

 

 

 

 

[과정]

 

  1. 입력값 부분을 첫번째 입력값을 기준으로 graph에 추가시켜줌

 

  2. bfs수행

      2-1) 거리(distance)와 방문처리(visited)는 bfs를 돌때마다 초기화

 

  3. 트리의 지름공식

     3-1) 임의의 노드에서 bfs를 돌리고 가장 먼 노드를 또 한번 bfs를 돌리고 나온 거리(dist)값이 정답

 

 

 

 

※ 4%에서 틀렸다고 뜨는 경우

 

우선 이 추가예제를 돌려보자.

답이 틀린게 나왔다면 구현한 알고리즘이 잘못된 것

 

# 추가 예제
4

1 2 5 3 9 -1

2 1 5 -1

3 1 9 4 8 -1

4 3 8 -1

답 : 22

6

1 2 3 -1

2 1 3 5 3 3 5 -1

3 2 5 4 7 -1

4 3 7 -1

5 2 3 6 5 -1

6 5 5 -1

답 : 20

4

1 2 7 3 2 -1

2 1 7 -1

3 1 2 4 3 -1

4 3 3 -1

답 : 12

5

1 2 7 3 2 5 10 -1

2 1 7 -1

3 1 2 4 3 -1

4 3 3 -1

5 1 10 -1

답 : 17

 

예제가 다 맞았는데도 '틀렸습니다.'가 뜬다면 문제에서 입력부분을 다시 천천히 읽어보자.

노드의 번호가 1번부터 차례대로 들어오지 않는다는 것을 확인하자.

즉, 입력부분에서 1~ V+1 정점순으로 입력받는게 아니라는것

 

 

 

※ 시간초과가 나는 경우

 

첫째. visited함수를 선언할 때 set함수를 사용

보통 리스트를 사용해서 참/거짓을 구별하도록 했을것이다.

 

[리스트를 사용해 시간초과난 코드]

 

def bfs(graph, start):
    distance = [0] * (n+1)
    visited = [False] * (n+1)
    max_node = 0
    
    q = deque([start])
    visited[start] = True
    
    while q:
        v = q.popleft()
        for now in graph[v]:
            if not visited[now[0]]:
                q.append(now[0])
                visited[now[0]]=True
                cost = distance[v] + now[1]
                if cost > distance[now[0]]:
                    distance[now[0]] = cost
                    max_node = distance.index(max(distance))
    return max_node , max(distance)

 

나는 false/true로 구별하도록 리스트를 선언했었는데 이렇게 하면 시간초과가 난다.

1967문제에서는 상관이없지만 해당문제에서는 오류가 나는 부분이다.

 

 

 

둘째. 노드와 간선의 정보를 입력받는 부분에서 불필요한 부분을 제거하고 for문 하나만을 사용

 

[입력부분에서 시간초과난 코드]

 

for _ in range(n):
    arr = list(map(int, input().split()))
    node = arr[0]
    del(arr[0])
    for j in range(0, len(arr), 2):
        if arr[j] == -1:
            break
        graph[node].append((arr[j],arr[j+1]))

 

불필요한 삭제연산(del)과 조건문(if)를 사용해 시간초과가 났다.

간결하게 for문 하나로 바꿔주자.

 

 

 

 

[소스코드]

 

# 트리의 지름 1167

from collections import deque
import sys
input = sys.stdin.readline

n = int(input())
graph = [[] for _ in range(n+1)]

for _ in range(n):
    arr = list(map(int, input().split()))
    for i in range(1, len(arr)-1, 2):
        graph[arr[0]].append((arr[i], arr[i+1]))

def bfs(graph, start):
    distance = [0] * (n+1)
    q = deque([start])
    visited.add(start)
    
    while q:
        v = q.popleft()
        for now in graph[v]:
            if not now[0] in visited:
                q.append(now[0])
                visited.add(now[0])
                cost = distance[v] + now[1]
                if cost > distance[now[0]]:
                    distance[now[0]] = cost
    return distance.index(max(distance)) , max(distance)

visited = set()
v1, dist = bfs(graph,1)
visited.clear()
v2, dist = bfs(graph, v1)
print(dist)

 

 

 

---

 

 

[통과]

 

 

 

어후..ㅋㅋㅋㅋㅋ 처참하다.

그래도 이유를 알아서 뿌듯하달까