[코테] 99클럽 코테 스터디 24일차 TIL - 그래프

Question1 - [미들러] 가장 먼 노드

 

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

 

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

 

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

 

제한사항

노드의 개수 n은 2 이상 20,000 이하입니다.

간선은 양방향이며 총 1개 이상 50,000개 이하의 간선이 있습니다.

vertex 배열 각 행 [a, b]는 a번 노드와 b번 노드 사이에 간선이 있다는 의미입니다.

 

입출력 예

n vertex return

6 [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]] 3

 

예제의 그래프를 표현하면 아래 그림과 같고, 1번 노드에서 가장 멀리 떨어진 노드는 4,5,6번 노드입니다.

 

---

문제풀이

 

*** 그래프

 

문제를 풀기 전에 우선 그래프가 어떤 유형의 알고리즘인지 살펴보자.

그래프는 노드 node/ vertex 와 엣지edge 로 구성된 자료 구조이며,

그래프로 노드간의 '관계'를 비선형적으로 표현하는 것이 가능해진다.

 

아래 그림에서 볼 수 있다시피, 화살표로 방향이 정해지는 방향 directed 그래프인지 여부, 노드간 거리에 가중치가 부여되는 weighted 그래프인지 여부에 따라 그 종류가 다양하다.

 

그래프 알고리즘은 도로 정보 표현 (최단경로 탐색), 소셜 네트워크 관계망 (관계 분석), 인터넷 네트워크망 (전송 속도 계산) 등에서 활용될 수 있는데, 이 외에도 매우 다양한 그래프 유형과 활용 상황들이 있다. 

그 중 대표적인 것이 너비우선탐색 (BFS), 깊이우선탐색 (DFS)를 활용하는 탐색 알고리즘라고 보면 됨.

...
1. 탐색 알고리즘
    너비 우선 탐색(BFS, Breadth-First Search)
    깊이 우선 탐색(DFS, Depth-First Search)
2. 최단 경로 알고리즘
  1) 단일 출발지 최단 경로 알고리즘
    다익스트라 알고리즘(Dijkstra Algorithm)
    벨만-포드 알고리즘(Bellman-Ford Algorithm)
  2) 모든 쌍 최단 경로 알고리즘
    플로이드-워셜 알고리즘(Floyd-Warshall Algorithm)
    존슨 알고리즘(Johnson Algorithm)
3. 최소 신장 트리 알고리즘 (MST, Minimum Spanning Tree)
    크루스칼 알고리즘(Kruskal Algorithm)
    프림 알고리즘(Prim Algorithm)
    보로우카 알고리즘(Borůvka Algorithm)
4. 네트워크 플로우 알고리즘
  1) 최대 유량 문제(Maximum Flow)
    에드몬드-카프 알고리즘(Edmonds-Karp Algorithm)
    푸시-렐라벨 알고리즘(Push-Relabel Algorithm)
    디니츠 알고리즘(Dinic Algorithm)
  2) 최소 비용 최대 유량(Minimum Cost Maximum Flow)
    네트워크 심플렉스 알고리즘(Network Simplex Algorithm)
    존슨 알고리즘을 활용한 최소 비용 유량 알고리즘
5. 위상 정렬(Topological Sorting)
    칸 알고리즘(Kahn Algorithm)
	DFS 기반 위상 정렬
6. 강결합 요소 알고리즘 (Strongly Connected Components, SCC)
    코사라주 알고리즘(Kosaraju Algorithm)
    타잔 알고리즘(Tarjan Algorithm)
7. 이분 그래프 알고리즘 (Bipartite Graph Algorithms)
    이분 매칭 알고리즘(Bipartite Matching)
    호프크로프트-카프 알고리즘(Hopcroft-Karp Algorithm)
    이분 그래프 판별 알고리즘
8. 그래프 색칠 알고리즘 (Graph Coloring)
    그래프 색칠 문제(Graph Coloring Problem)
    크로스컬 알고리즘(Greedy Coloring Algorithm)
9. 경로 찾기 알고리즘 (Pathfinding Algorithms)
    A 알고리즘(A Algorithm)**
    다익스트라 알고리즘(Dijkstra Algorithm)
    DFS 및 BFS 기반 경로 찾기
10. 근사 알고리즘 (Approximation Algorithms)
    트래블링 세일즈맨 문제(Traveling Salesman Problem, TSP)
    최근접 이웃 알고리즘(Nearest Neighbor Algorithm)
    크리스티안슨-호그린 알고리즘(Christofides Algorithm)
11. 랜덤화 알고리즘 (Randomized Algorithms)
    랜덤 워크 알고리즘(Random Walk Algorithm)
    몬테카를로 알고리즘(Monte Carlo Algorithms)
12. 분할 정복 알고리즘 (Divide and Conquer)
    그래프 분할 알고리즘(Graph Partitioning)
    메티스 알고리즘(METIS Algorithm)
...

 

 

trial1 

 

위 문제에서는, BFS 너비우선탐색을 통한 그래프 알고리즘을 활용해서 문제를 풀 수 있다. 

'1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지' 구하기 위해서는,

우선 1번 노드로부터 각 노드로 가는 최단거리가 얼마인지 구한 후에, 거리들 중 max값이 총 몇개인지를 반환하면 되기 때문이다.

 

1) 그래프를 표현 (인접리스트로 표현) 하고, 

2) BFS 탐색 방식으로 각 노드까지의 최단거리를 구하는 것이 핵심이다.

 

1) 그래프를 인접리스트로 표현

defaultdict를 생성 후 각 요인을 담아 반복문을 돌리면 아래처럼 그래프를 표현해줄 수 있다.

방향이 없으므로 인접한 노드를 모두 상호적으로 표현하는 리스트이다.

edge = [[3, 6], [4, 3], [3, 2], [1, 3], [1, 2], [2, 4], [5, 2]]

graph = defaultdict(list)
for u, v in edge:
    graph[u].append(v)
    graph[v].append(u)

graph

# 출력 
defaultdict(list,
            {3: [6, 4, 2, 1],
             6: [3],
             4: [3, 2],
             2: [3, 1, 4, 5],
             1: [3, 2],
             5: [2]})

 

2) BFS 탐색 방식으로 각 노드까지의 최단거리 구하기 

 

우선 1번 노드에서 출발하여 각 노드까지의 거리를 저장하는 distances 배열이 필요하다.

BFS를 초기화 시켜주기 위해 처음에는 모든 노드를 -1로 초기화하여 방문하지 않았음을 나타내고, 

시작 노드인 1번 노드에서 자기 자신까지의 거리는 0으로 설정한다.

또한 큐에는 현재 방문할 노드를 저장하도록 한다.

 

그다음 BFS를 수행하는데,

큐에 방문할 노드가 있는 동안 반복문을 돌리면서, 인접한 노드를 모두 탐색하면서 거리를 업데이트 해나간다.

 

예를 들어서, 1번 노드에 인접한 2,3번 노드가 있다면 그것을 큐에 추가하고, 둘의 거리를 1로 갱신한다.

그다음 큐에서 2번 노드를 꺼내면, 2번 노드에 인접한 4, 5 번 노드를 똑같이 큐에 추가하고, 이들의 거리를 2로 갱신한다 (1->2->4 or 5) ….

최종 코드는 아래와 같다.

from collections import deque, defaultdict

def solution(n, edge):
    # 그래프를 인접 리스트로 표현
    graph = defaultdict(list)
    for u, v in edge:
        graph[u].append(v)
        graph[v].append(u)
    
    # BFS 초기화 : 각 노드까지의 최단거리 구하기 위해 
    distances = [-1] * (n + 1)  # 1번 노드로부터의 거리, -1은 방문하지 않음을 의미
    distances[1] = 0  # 1번 노드에서 자기 자신까지의 거리는 0
    queue = deque([1])  # BFS 시작 노드는 1번
    
    # BFS 수행
    while queue:
        current_node = queue.popleft()
        current_distance = distances[current_node]
        
        for neighbor in graph[current_node]:
            if distances[neighbor] == -1:  # 방문하지 않은 노드라면
                distances[neighbor] = current_distance + 1
                queue.append(neighbor)
    
    # 최대 거리 계산
    max_distance = max(distances)
    
    # 최대 거리를 가지는 노드의 개수 세기
    answer = distances.count(max_distance)
    
    return answer