100년 뒤 개발자 한승규입니다.

https://www.acmicpc.net/problem/1167

트리의 지름을 구하는 방법은 우선, 한 노드에서 가장 멀리 있는 노드를 구한다.

그리고 그 노드에서 가장 멀리 있는 길이를 구한다.

그러면 그게 노드의 지름이 된다.

그러면 2번 길이를 구해야 하는 데, 귀찮아서 함수로 만들어버렸다.

우선 각 그래프에 대한 정보를 입력 받은 후 BFS를 진행한다.

처음의 BFS에서는 가장 멀리 있는 노드를 구하고, 그 다음의 BFS에서는 길이를 구한 후 출력한다.

from collections import deque
import sys

V = int(sys.stdin.readline())

graph = [[] for _ in range(V + 1)]

for _ in range(V):
    c = list(map(int, sys.stdin.readline().split()))
    for e in range(1, len(c) - 2, 2):
        graph[c[0]].append((c[e], c[e + 1]))


def bfs(target):
    weight = [-1] * (V + 1)
    weight[target] = 0
    need_visit = deque()
    need_visit.append(target)
    result = [0, 0]

    while need_visit:
        cur = need_visit.popleft()
        for v, w in graph[cur]:
            if weight[v] == -1:
                weight[v] = weight[cur] + w
                need_visit.append(v)
                if result[0] < weight[v]:
                    result = [weight[v], v]

    return result


print(bfs(bfs(1)[1])[0])

https://www.acmicpc.net/problem/1946

문제를 이해하는 시간만 한시간 정도 걸렸던 것 같다.

당연히 점수인 줄 알았는 데, 너무 이해가 되지 않아 질문게시판 찾아보니까 순위라고 하더라....

무조건 한 명 이상은 뽑을 것이니 처음 result를 1로 해준다.

그러고는 그냥 단순히 앞 순위로 정렬해주고, 반복문으로 순위를 점점 올려가며 가능한 친구들만 받고 result를 +1해준다.

import sys

for i in range(int(sys.stdin.readline().strip())):
    candidate = sorted([list(map(int, sys.stdin.readline().split())) for _ in range(int(sys.stdin.readline().strip()))])
    top = 0
    result = 1

    for t in range(1, len(candidate)):
        if candidate[t][1] < candidate[top][1]:
            top = t
            result += 1

    print(result)