📖Problems

코딩테스트 연습 > 고득점 kit > 그래프 > 가장 먼 노드 Level 3문제입니다.

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번 노드입니다.

🔍Institution

그래프 알고리즘은 무엇이고 어떻게 푸는지를 chatGPT에 물어본 후 정리해보았다.

그래프 알고리즘

그래프 데이터 구조를 사용해 문제를 해결하는 알고리즘
node와 이를 연결하는 edge로 구성
다양한 유형이 있고, 각각 특정 문제를 해결하기 위해 설계됨

일반적인 방법

문제를 그래프로 나타내기
그래프 알고리즘을 이용해 문제를 해결하기 위해선 먼저 문제를 그래프로 표현해야 한다.
문제의 정점과 그들간의 관계를 찾은 후, 이를 노드와 엣지로 나타낸다.
적절한 알고리즘 선택하기
다양한 유형 존재하며 특정 문제를 해결하기 위해 설계되었기 때문에 가장 적합한 알고리즘 선택하기
그래프 탐색
알고리즘 규칙에 따라 그래프를 탐색한다. 대체로 그래프의 각 노드를 특정 순서로 방문하고, 노드를 방문할 때 필요한 연산을 수행한다.
solution 업데이트
그래프를 다 탐색했다면, 그래프를 이동하면서 수집한 정보를 기반으로 문제에 대한 솔루션을 업데이트한다.
해결하는 문제에 따라 솔루션은 단일값일 수도 있고 더 복잡한 데이터 구조일수도 있다.
복잡도(Complexity) 분석
마지막으로 알고리즘의 시간 복잡도와 공간복잡도를 분석한다.

그래프 알고리즘의 유형

Breadth-first search (BFS)
Depth-first search (DFS)
Dijkstra’s algorithm : 가중 그래프에서 두 꼭짓점 사이의 최단경로 찾기
Bellman-Ford algorithm : 그래프에서 음의 가중치가 포함된 경우, 가중치 그래프에서 두 꼭짓점 사이의 최단경로 찾기
Prim’s algorithm : 가중 무방향 그래프의 최소 스패닝 트리 찾기
Kruskal’s algorithm : 가중 무방향 그래프의 최소 스패닝 트리 찾기

이 문제는 어떤 알고리즘 유형을 해야 하는지 분석해보자. 우선 가중 그래프가 아니기 때문에 다익스트라, 밸먼포드, 프림, 크루스칼은 사용하지 않는다는 것을 알 것이다.

DFS는 모든 경로를 다 탐색한다면, BFS는 최단거리를 구할 때 주로 사용한다. 이 문제는 터미널 노드 중에서 최단 경로로 접근할 수 있는 터미널 노드의 개수를 구하는 것이므로 BFS로 푸는 것이 유리하다.

추가적으로, DFS로는 풀면 안 되는 이유는 아래와 같다.

문제 관련 이슈(스포: DFS를 사용하면 통과가 안되는 이유) - https://programmers.co.kr/questions/12681

DFS의 경우 깊이가 깊어지는 간선을 먼저 탐색하기 때문에, (1, 2) , (1, 3), (2, 3) 이렇게 연결되있을 때 3번 노드는 1번 노드로부터 1의 깊이를 가지지만 DFS로 탐색할 경우 1->2->3 순으로 탐색하기 때문에 3번 노드가 1번 노드로부터 2의 깊이를 가지게 되서 모순이 발생

BFS 구현 방식은 아래와 같다.

  
from collections import deque

def BFS_with_adj_list(graph, root):
    visited = []
    queue = deque([root])

    while queue:
        n = queue.popleft()
        if n not in visited:
            visited.append(n)
            queue += graph[n] - set(visited)
    return visited
  
print(BFS_with_adj_list(graph_list, root_node))

🔍Approach

로직은 아래와 같다.

출처 : https://arinnh.tistory.com/40

graph[] : 그래프로 만들어주기 위한 리스트/딕셔너리
visited[] : 방문여부 확인할 리스트
queue[] : 노드 확인용 / 그래프 탐색할 때 사용되는 큐
nodes : 연결된 노드 확인 / return할 값

FLOW

노드를 연결할 graph[], 방문여부를 확인할 visited[], 노드를 확인할 queue를 선언하고 초기화한다. 또한 노드의 연결 수를 확인한 nodes변수도 초기화한다.
for문을 이용해서 graph로 연결한다. (각 노드별로 연결된 노드를 append한다.
queue의 1번 노드와 1번 노드에 대한 방문여부를 1로 설정한다.
queue가 없을 때까지 아래 내용을 반복한다.
4-1. nodes는 큐의 길이를 저장하는 변수이다. 큐가 다 비기 전에, 모든 노드(1~6)까지 다 들어갔을 때의 큐의 길이를 return해야 하기 때문에 가장 위로 배치한다.
4-2. 첫 번째 for문은 nodes안에서 작동한다.
첫 반복은 1만큼 두 번째는 2만큼 세번째는 3만큼 반복한다.
4-3. 그 다음 popleft()한 값을 가지고 그에 해당하는 그래프 안에서, 방문여부를 확인한다.
4-3-1. 방문하지 않았다면
방문한 것으로 표시하고, queue에 추가한다.
nodes를 return한다.

🚩My submission

  
from collections import deque

def solution(n, edge):
    graph = [[] for _ in range(n+1) ]
    visited = [0] * (n+1)
    queue = deque()
    queue.append(1)
    visited[1] = 1
    nodes = 0
    
    for a, b in edge:
        graph[a].append(b)
        graph[b].append(a)
    
    while queue:
        nodes = len(queue)
        for i in range(nodes):
            cur_n = queue.popleft()
            for c in graph[cur_n]:
                if visited[c] == 0:
                    visited[c] = 1
                    queue.append(c)
        
    return nodes

🚩Others submission

deque 형식

✔ JB선배

  
from collections import deque
def solution(n, edge):
    queue = deque([[1,0]])
    # 그래프 생성
    dic = {}
    for i, j in edge:
        if i in dic: dic[i].append(j)
        else: dic[i] = [j]
        if j in dic: dic[j].append(i)
        else: dic[j] = [i]

    visited = [False] * (n + 1)
    visited[1] = True
    temp = []
    # BFS
    while queue:
        node, distance = queue.popleft()
        count = 0
        # 인접노드중 방문하지 않은 노드를 queue에 추가
        for near in dic[node]:
            if not visited[near]:
                queue.append([near, distance+1])
                visited[near] = True
        # temp에 성분이 있다면 distance에 따라 초가화하거나 append
        # temp가 없다면 초기화
        if temp:
            if temp[0][1] < distance:
                temp = [[node, distance]]
            elif temp[0][1] == distance:
                temp.append([node, distance])
        else:
            temp = [[node, distance]]

    return len(temp)

✔가장 먼 노드의 최댓값을 구하는 방법

  
from collections import deque
def solution(n, edge):
    graph = dict()
    visited = [0] * (n+1)
   
    for i in range(1, n+1): # 빈 딕셔너리 생성 {노드 번호: [연결노드]}
        graph[i] = []
   
    for i in edge:  # 딕셔너리 키 - 값 할당
        graph[i[0]].append(i[1])
        graph[i[1]].append(i[0])

    return bfs(graph, n, visited)

def bfs(graph, n, visited):
    queue = deque([1])  # 큐에 시작 노드 1 삽입
    visited[1] = 1
   
    while queue:
        v = queue.popleft()
       
        for i in graph[v]:
            if visited[i] == 0:
                visited[i] = visited[v] + 1
                queue.append(i)
    return visited.count(max(visited))

💡TIL

그래프 문제에 약한 편이라서 그래프를 어떻게 접근해야 하는지 어떤 종류가 있는지 어떤 식으로 하면 될지 천천히 접근하다보니까 얻어가는 게 많았던 문제였다.
혼자 힘으로 문제를 풀지 못해서 다른 사람이 푼 풀이를 해석해가고, 혼자 그림 그려보면서 풀이를 마무리했다. 그래프 문제에 대한 공포증이 있었는데 어느정도 덜어낼 수 있는 것 같고, 이를 토대로 그래프의 다른 문제를 풀 때에도 잘 할 수 있으

프로그래머스 - 그래프_가장 먼 노드(Mj)

📖Problems

🔍Institution

🔍Approach

🚩My submission

🚩Others submission

💡TIL

Further Reading

프로그래머스 - 그래프_순위 (MJ)

프로그래머스 - 폰켓몬 (MJ)

프로그래머스 - 완주하지 못한 선수 (MJ)