[프로그래머스][LV.3] 가장 먼 노드 | python3

문제링크:  가장 먼 노드

---

문제설명

n개의 노드가 있는 그래프가 있습니다. 각 노드는 1부터 n까지 번호가 적혀있습니다. 1번 노드에서 가장 멀리 떨어진 노드의 갯수를 구하려고 합니다. 가장 멀리 떨어진 노드란 최단경로로 이동했을 때 간선의 개수가 가장 많은 노드들을 의미합니다.

노드의 개수 n, 간선에 대한 정보가 담긴 2차원 배열 vertex가 매개변수로 주어질 때, 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 return 하도록 solution 함수를 작성해주세요.

 

제한조건

- 노드의 개수 n은 2 이상 20,000 이하입니다.
- 간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.
- vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.

---

 

문제풀이

def solution(n, edge):
    answer = 0
    dist=[0] * (n+1)
    # edge를 복사하여 방문한 간선을 삭제하는 식으로 가려 했으나 시간이 오래 걸릴 거 같음.
    # cEdge=edge.copy()
    visited=[]
    node=1 # 처음 시작
    while len(visited) != len(edge):
        chk=0
        for i,j in edge:
            
            if (i,j) in visited or i!=node:
                chk+=1
                if chk==len(edge):
                    node+=1
                continue
            # 노드에서 노드로 옮길때마다 1 추가 더이상 갈 곳 없으면 시작 노드 재설정
            dist[j]=dist[i]+1
            visited.append((i,j))
    m=max(dist)
    answer=dist.count(m)
    return answer

 

bfs문제랑 비슷하게 풀면 된다고 생각했다. bfs는 보통 최소거리를 구할때 사용했으니까 응용해서 풀면 될거라고 생각함.

아이디어는 좋았던 거 같은데 내 실력이...ㅠㅜ

1. while len(visited) != len(edge): → 무한 루프 가능성

• visited에 (i, j) 간선이 추가되면서 루프가 끝나야 하는데, 특정 경우에는 visited가 edge와 같은 크기가 되지 않을 수도 있다
• 또한, visited가 모든 edge를 포함해도 여전히 방문하지 못한 노드가 있을 수 있다.

✅ 해결 방법:
BFS(너비 우선 탐색)를 사용해서 모든 노드를 탐색하는 방식으로 변경하는 것이 더 적절함.

---

2. node를 수동으로 증가시키는 방식 (node+=1)의 문제

• node를 증가시키면서 탐색하지만, 이 방식은 그래프가 단절된 경우(즉, 연결되지 않은 노드가 있는 경우)를 제대로 처리하지 못함.
• 또한, node+=1을 하더라도 연결된 노드를 효과적으로 탐색하지 않기 때문에 제대로 된 최단 거리를 찾기 어려움.

✅ 해결 방법:
BFS를 사용하여 연결된 노드를 queue에 추가하면서 탐색하면 노드를 수동으로 변경하지 않아도 됨.

---

3. 방문한 간선((i, j))을 visited.append((i,j))로 저장하는 방식의 문제

• 간선을 기준으로 방문을 체크하면 양방향 그래프일 경우 (i, j)와 (j, i)를 다르게 인식할 수도 있음.
• 하지만 최단 거리를 구할 때는 노드를 방문했는지 체크해야 하지, 간선을 체크하는 방식은 적절하지 않음.

✅ 해결 방법:

• 방문한 노드를 저장하는 set() 사용 (visited를 노드 기준으로 변경)

---

4. dist[j] = dist[i] + 1이 잘못된 이유

• 현재 코드에서는 dist[i] 값이 설정되기 전에 dist[j]를 업데이트할 수 있음.
• 예를 들어, dist[i]가 0인 상태에서 dist[j]를 업데이트하면 올바른 최단 거리가 아니라 엉뚱한 값이 될 수 있음.

✅ 해결 방법:

• BFS를 이용하면 항상 현재 거리(dist[node])에 1을 더한 값이 다음 노드(neighbor‌)에 저장됨.

 

🔍 코드에서 논리적으로 문제가 되는 부분 해결 방법

1. visited를 간선((i, j))이 아니라 노드 기준으로 관리해야 함
   • 현재 코드는 visited.append((i, j))로 간선을 방문했다고 체크하는데, 노드를 방문했는지 확인하는 것이 맞음
   • ✅ 해결: visited 리스트를 방문한 노드의 목록으로 변경
2. node를 수동으로 증가시키는 방식이 비효율적이고 논리적으로 맞지 않음
   • chk를 사용해 모든 간선을 확인한 후 node += 1을 하는 방식은 잘못됨
   • ✅ 해결: **BFS(너비 우선 탐색)**을 적용하면 자동으로 방문 순서를 결정할 수 있음
3. dist[j] = dist[i] + 1 로 거리 갱신이 불완전함
   • dist[i]가 아직 갱신되지 않은 상태에서 dist[j]가 업데이트될 수도 있음
   • ✅ 해결: BFS 방식으로 dist[node] + 1을 통해 정확한 최단 거리 계산

 

from collections import deque

def solution(n, edge):
    answer = 0
    dist=[0] * (n+1) # 노드별 거리 저장
    # edge를 복사하여 방문한 간선을 삭제하는 식으로 가려 했으나 시간이 오래 걸릴 거 같음.
    # cEdge=edge.copy()
    visited=set() # 방문한 간선x 노드o
    node=1 # 처음 시작 노드
    queue = deque([node]) # 노드 큐
    
    while queue:
        
        node = queue.popleft()
        
        for i,j in edge:
            
            if i==node and j not in visited:
                dist[j]=dist[node]+1
                visited.add(j)
                queue.append(j) # queue에 추가하여 다음 탐색
            
            # 양방향일때
            elif j==node and i not in visited:
                dist[i]=dist[node]+1
                visited.add(i)
                queue.append(i)
            
            # if (i,j) in visited or i!=node:
            #     chk+=1
            #     if chk==len(edge):
            #         node+=1
            #     continue
            # # 노드에서 노드로 옮길때마다 1 추가 더이상 갈 곳 없으면 시작 노드 재설정
            
    m=max(dist)
    answer=dist.count(m)
    return answer

 

내 코드를 유지해서 풀어보려고 했는데 안됨...gpt도 틀림

걍 다시 풀어야겟다.

 

시작노드를 visited에 추가를 안해줘서 틀렸다. 위 코드도 추가해주면 맞을지도?

 

맞는데 테스트 7,8,9에서 시간초과가 난다.

 

 

=> 1에서부터 각 노드마다의 최소거리를 찾는 것이기 때문에 전형적인 BFS 문제였다.

이런 유형의 문제에 이제는 익숙해져야 하는데

나의코드

from collections import deque

def solution(n, edge):
    # 그래프을 인접 리스트로 변환
    graph = {i: [] for i in range(1,n+1)}
    
    # 양방향 그래프
    for a,b in edge:
        graph[a].append(b)
        graph[b].append(a)
        
    dist=[0]*(n+1) # 거리 저장
    visited = set([1]) # 방문한 노드 (간선x) # 시작노드 추가해줘야함
    queue=deque([1])
    
    while queue:
        node=queue.popleft()
        
        for g in graph[node]:
            if g not in visited:
                visited.add(g)
                dist[g]=dist[node]+1
                queue.append(g)
                
    max_dist=max(dist)
    answer=dist.count(max_dist)
        
    return answer

 

1. BFS를 사용하여 최단 거리 탐색을 정확하게 수행
   → 모든 노드를 한 번씩만 방문하므로 효율적
2. 노드를 방문 체크 (set 대신 dist 배열 사용)
   → dist[i] == -1이면 방문하지 않은 것으로 판단
3. queue를 활용해 자동으로 다음 탐색 노드를 선택
   → node += 1 같은 수동 조작이 필요 없음
4. 최장 거리(max(dist))를 찾아 해당 개수를 반환
   → 가장 먼 거리의 노드 개수를 정확하게 계산

---

 

참고하기