알고리즘(Python)_그래프

문제

가장 먼 노드

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

1. 그래프를 돌면서 깊이를 저장해야할 것 같다는 생각에 dfs를 써서 재귀함수에 depth를 인자로 넣어야하나 생각했다.
   근데 dfs로 풀기에는 dfs는 그래프를 한꺼풀씩 벗기면서 순회하는 게 아니라서 depth를 재기가 힘들었다.

2. 그래서 bfs로 풀어야겠다고 생각했으나 처음에는 아래와 같이 생각해서 한 단계에서 두 개 이상의 노드가 있을때 depth를 재는 게 두번째 노드부터는 엉키게 된다.

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

3. 그래서 전 단계의 노드의 depth에 +1을 하는 코드를 생각했다.

마지막에 max 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분