[99클럽 코테 스터디 24일차 TIL] 프로그래머스 | 가장 먼 노드

24일차 graph

Problem

그래프 / 가장 먼 노드

프로그래머스

 

 

Sol

1번 노드에서 가장 멀리 떨어진 노드의 개수를 구하는 문제

 

🌱 참고

그래프를 적절한 형태의 자료구조로 변환하고 생각해야 했던 문제였습니다.  아래 도서를 참고하여 공부했습니다.

 

Do it! 알고리즘 코딩 테스트: 파이썬 편

“코딩 테스트를 제대로 준비하려면 어떤 문제를 얼마나 풀어야 할까?” 곧 코딩 테스트를 앞둔 취업 또는 이직 준비생이라면 누구나 이런 고민을 할 것이다. 《Do it! 알고리즘 코딩 테스트 - 파이썬 편》에 그 답이 있다. 네이버, 카카오, 삼성, 라인 등 주요 IT 기업의 시험에 나오는 알고리즘 내용이 모두 담겨 있어 책 한 권만으로 코딩 테스트 합격에 필요한 지식을 충분히 공부할 수 있다. 책에 수록된 알고리즘 문제 100개는 모두 최신 기출 유형을 반영하고 있어서 이 책의 문제만 다 풀면 당장 코딩 테스트를 볼 수 있는 수준까지 실력을 갖출 수 있다. 모든 문제는 ‘분석, 전략, 슈도코드, 코드 구현’까지 총 4단계를 거쳐 푸는데, 이렇게 문제를 푸는 습관까지 자기 것으로 만든다면 진짜 시험에서 어떤 문제를 만나든 실수 없이 해결할 수 있을 것이다.

저자

김종관

출판

이지스퍼블리싱

출판일

2022.08.16

 

 

 

해결 방법

👀 그래프를 인접 리스트로 표현하고, BFS를 사용해 그래프를 탐색하였습니다. 탐색이 완료되면 node간 거리 distances중에서 제일 먼 거리를 가진 노드를 count할 수 있습니다. 그래프 생성 ➡️ BFS 탐색 ➡️ 최대 거리 계산

1. 그래프 -> 인접 리스트(adjacency list)
 - n번 노드와 연결되어 있는 노드를 리스트(graph)의 index n에 append 하는 방식
 - edge 'a', 'b' 양방향 연결

2. BFS 위한 거리 리스트(distances), queue 초기화
 - distances : 각 노드의 거리 저장
 - 방문하지 않은 노드의 distances를 -1 로 설정
 - 1번 노드에서 출발하기 때문에 1번 거리 = 0
 - queue에 1번 노드 넣은 상태로 BFS 시작

3. BFS 탐색 : 1번 노드로부터 모든 노드까지의 최단 거리 계산
 - 너비 우선 탐색 - 가장 먼저 queue에 들어온 노드부터 탐색
 - queue에서 노드를 하나씩 꺼낸 후 인접한 이웃(neighbor) 노드 탐색
 - 방문되지 않았을 경우(-1) : 현재 노드의 거리 + 1 하고 queue에 추가

4. 가장 멀리 떨어진 노드 개수 count
 - max_distance(저장된 distances) 중 최대값 을 count

 

시간복잡도 O(V+E)

• Vertex(그래프 노드수), Edge(간선 수)
• O(V) : 그래프의 모든 노드 방문, queue에 빼고 넣는 과정이 O(1)이기 때문에 가능
• O(E) : 모든 간선 검사, 인접 간선을 모두 검사하는데 드는 시간이 간선의 총 개수에 비례

---

✔ Answer

from collections import deque

def solution(n, edge):
    # 1번 노드에서 가장 멀리 떨어진 노드의 개수
    answer = 0
    
    # 1. 그래프 -> 인접 리스트로
    graph = [[] for _ in range(n+1)]
    for a, b in edge:
        graph[a].append(b)
        graph[b].append(a)
        
    # 2. BFS 위한 거리 리스트, 큐 초기화
    distances = [-1] * (n + 1) # not visited 상태
    distances[1] = 0 # 1번 노드
    queue = deque([1])
    
    while queue:
        current = queue.popleft()
        for neighbor in graph[current]:
            if distances[neighbor] == -1: # not visited 노드
                distances[neighbor] = distances[current] + 1
                queue.append(neighbor)
                
    # 3. 가장 멀리 떨어진 노드 개수
    max_distance = max(distances)
    answer = distances.count(max_distance)
    
    return answer

---

💬 소감

문제가 갑자기 너무 어려워진 느낌이었습니다. 공부를 더 해야겠구나 다시 한번 느꼈습니다...