アルゴリズムパターン

質問する

最も遠いノード

from collections import deque
import time

def solution(n, edge):
    # st = time.time()
    grid = [ [] for _ in range(n+1)]
    
    for i in edge:
        grid[i[0]].append(i[1])
        grid[i[1]].append(i[0])
    
    visited = [False for _ in range(n+1)]
    # 노드의 깊이를 저장하는 리스트
    depths = [0 for _ in range(n+1)]
    
    # bfs 시작
    s = 1
    visited[s] = True
    que = deque([s])
    d = 0
    while que:
        a = que.popleft()
        if grid[a]:
            d = depths[a] + 1
            # 그 전 단계의 노드의 depth + 1
            for i in grid[a]:
                if not visited[i]:
                    que.append(i)
                    depths[i] = d
                    visited[i] = True
    cnt = 0
    for i in depths:
        if i == max(depths): 
            cnt += 1
    # depths.sort(reverse=True)
    # cnt = depths.count(depths[0])
    # print(time.time()-st)
    return cnt

グラフに深さを保存する必要があることを考慮して、dfsを使用して深さをパラメータとして再帰関数に入れるべきだと思います.
しかしdfsで解くと,dfsはグラフを1層ずつ剥がすので深さを測定するのは難しい.

なのでbfsで解くべきだと思いますが、最初は1段階に2つ以上のノードがある場合、測定深さは2番目のノードから葛藤すると思います.

def bfs(s):
    visited[s] = True
    que = deque([s])
    d = 0
    while que:
        a = que.popleft()
        print(a)
        if grid[a]:
            d += 1
            for i in grid[a]:
                if not visited[i]:
                    que.append(i)
                    depths[i] = d
                    visited[i] = True

は,前段階のノード深さに+1を加えたコードを思いついた.

最後に,最大depthを有するノードの個数を計算するために最も効率的なコードとは何かを見てみよう.

    cnt = 0
    for i in depths:
        if i == max(depths): 
            cnt += 1

->1.740秒

depths.sort(reverse=True)
cnt = depths.count(depths[0])

->1.478秒

cnt = depths.count(max(depths))

->1.430秒
回答時間:1時間50分