[프로그래머스] 가장 먼 노드

문제 : https://programmers.co.kr/learn/courses/30/lessons/49189

코딩테스트 연습 - 가장 먼 노드

 

나의 풀이 

- dfs로 탐색해서 노드별로 깊이를 체크하는 리스트를 갱신하는 방식을 생각했는데

tc와 같이 사이클이 존재하는 경우 갱신이 또 되는 현상이 있었다.

-> 수정하면 고칠 수 있을 것 같은데 bfs로 바꾸는게 빠를 것 같아서 변경!!

- 40분 정도 걸린 것 같은데 어떤 탐색법으로 접근할지 초기에 잘 정해야 될 듯...ㅠㅠ

from collections import deque

def bfs(graph,visited,start,min_count):
    queue = deque([start])
    visited[start] = True
  
    while queue:
        v = queue.popleft() 
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i]=True
                min_count[i] = min_count[v] +1

def solution(n, edge):
    answer = 0
    graph=[[] for i in range(n+1)]
    
    for sn, fn in edge:
        graph[sn].append(fn)
        graph[fn].append(sn)
    
    visited = [False] * (n+1)
    min_count = [0] * (n+1)
    
    bfs(graph,visited,1,min_count)
    
    return min_count.count(max(min_count))

주의할 점

- graph 리스트에 출발 노드 인덱스에 도착 노드만 작성해서 2노드에서 5 노드로 탐색이 불가능했던 실수가 있었다.

-> 간선 정보로 연결된 노드 각각 노드 정보 넣기

1로부터 가까운 노드부터 탐색을 진행하므로 앞에 연결된 노드 간선 최소 값에서 +1 해주면 된다.

 

 

다른 코드

- 방법 똑같음

def solution(n, edge):
    graph =[  [] for _ in range(n + 1) ]
    distances = [ 0 for _ in range(n) ]
    is_visit = [False for _ in range(n)]
    queue = [0]
    is_visit[0] = True
    for (a, b) in edge:
        graph[a-1].append(b-1)
        graph[b-1].append(a-1)

    while queue:
        i = queue.pop(0)

        for j in graph[i]:
            if is_visit[j] == False:
                is_visit[j] = True
                queue.append(j)
                distances[j] = distances[i] + 1

    distances.sort(reverse=True)
    answer = distances.count(distances[0])

    return answer