[Programmers, Lv.3] 코딩테스트 고득점 Kit - 그래프 (1), 기본 개념, BFS/DFS + 가장 먼 노드 (Python)

📊 그래프가 뭔데?

---

그래프를 사전적으로 정의하면, "정점(노드)과 간선(엣지)으로 이루어진 자료구조"이다.
이 말을 이해하기 위해서는 정점(노드)은 뭔지, 간선(엣지)은 뭔지를 알아야 할 것이다. 설명해 보겠다.

노드(Node)는 예전 연결 리스트를 다루는 글에서 설명한 적이 있듯이, 하나의 데이터 단위를 나타내는 객체라고 이해하면 된다. 아래와 같이 SNS 구조를 나타내는 그래프가 있다고 했을 때, 영훈, 현승, 동욱과 같이 한 유저가 그래프 구조 안에서 하나의 노드라고 설명할 수 있겠다.

간선(엣지, Edge)는 그래프 내에서 두 노드 간의 연결 관계를 나타내는 데이터를 의미한다. 쉽게 설명해서 연결선.
그래서 두 노드 사이에 엣지가 있으면, 이때는 "두 노드는 인접해 있다."라고 표현하게 된다.
엣지가 갖는 특성에 따라 그래프의 종류가 바뀔 수도 있는데,
방향 없이 단순히 연결 관계만 표현하는 엣지인 경우에는 무방향 그래프 혹은 양방향 그래프, 방향이 있는 엣지가 사용된다면 방향 그래프(directed graph), 엣지에서 연결 관계뿐만 아니라 어떤 정보를 나타내는 수치를 가질 경우에는 가중치 그래프(weighted graph)라고 부르게 된다.

추가적으로, 그래프에서 사용되는 다른 용어들은 아래와 같다.

• 차수 : 하나의 노드에 연결된 엣지의 수 (방향 그래프일 경우에는 출력 차수와 입력 차수를 따로 구분)
• 경로 : 한 노드에서 다른 노드까지 가는 길을 의미 (거리가 가장 짧은 경로를 나타내는 최단 경로와 한 노드에서 시작해 같은 노드로 돌아오는 경로인 사이클이 있다.)

그래프 모습의 예시 (출처: 코드잇 강의)

 

 

🔍 BFS(Breadth First Search, 너비 우선 탐색), DFS (Depth First Search, 깊이 우선탐색)

---

그래프에 대해서 기본적으로 배워봤으니, 이번에는 그래프 탐색의 개념과 종류 두 가지에 대해서 간단하게 이해해 볼 차례이다.
그래프 탐색이란 "하나의 시작점 노드에서 연결된 노드들을 모두 찾는 것"을 말한다. 말이 어렵지, 그냥 노드들을 탐색하는 방법을 의미한다고 이해하면 되겠다.

대신, 노드들을 어떤 방법으로 찾느냐에 따라서 방법이 나뉘게 되는 거다.
이 글에서는 대표적인 탐색 방법 두 가지 BFS (Breadth First Search)와 DFS (Depth First Search) 방법을 배워보도록 하겠다.

왼쪽이 BFS의 탐색 순서, 오른쪽이 DFS의 탐색 순서를 의미한다. (출처: https://m.blog.naver.com/occidere)

 

BFS (Breadth First Search)는 너비 우선 탐색이라는 말에서 알 수 있듯이, 시작 노드에서부터 인접한 노드 (즉, 엣지와 연결된 노드)부터 탐색하는 방식을 말한다.
가까운 노드부터 우선적으로 탐색한다는 BFS의 특징 때문에, 파이썬에서는 선입선출 방식의 큐(Queue) 자료구조를 활용해서 구현하게 된다.

자세한 동작 과정은 아래에서 설명을 해둘 테니 글을 읽으면서 문제에서는 어떻게 코드로 구현할지 직접 생각해 보도록 하자.

1️⃣ 탐색할 노드를 담을 큐(Queue) 자료형과, 각 노드가 방문한 노드인지를 구분할 수 있는 리스트를 만들어둔다.
2️⃣ 탐색 시작 노드(첫 번째 노드)를 큐에 넣어두고, 방문 처리한다.
3️⃣ 큐에서 노드를 꺼내고, 방문하지 않은 인접한 노드들을 큐에 삽입하고, 이 노드들을 방문 처리한다.
4️⃣ 방문하지 않은 노드가 없을 때까지 3️⃣의 과정을 계속 반복한다.

 

DFS (Depth First Search)는 가로를 먼저 훑는 BFS와 반대로, 밑 부분을 먼저 훑는 방식이라고 이해하면 되겠다.
한 분기(branch)의 모든 노드들을 방문하다가 더 이상 다른 노드를 방문할 수 없는 노드에 이르렀을 때, 다시 가장 가까운 갈래길로 돌아가 방문하지 않은 노드 방향으로 탐색을 이어가는 방법이다.

마찬가지로 자세한 동작 과정을 아래에서 설명해 보겠다. 코드로 어떻게 구현할지 고민해 보자.

1️⃣ 탐색할 노드를 담을 스택(Stack) 자료형과, 각 노드가 방문한 노드인지를 구분할 수 있는 리스트를 만들어둔다.
2️⃣ 탐색 시작 노드(첫 번째 노드)를 스택에 넣어두고, 방문 처리한다.
3️⃣ 스택 내 최상단 노드에 방문하지 않은 노드가 있다면, 그 인접 노드를 스택에 삽입하고 방문 처리한다.
4️⃣ 만약, 방문하지 않은 인접 노드가 없다면 스택 내 최상단 노드를 꺼냅니다.
5️⃣ 방문하지 않은 노드가 없을 때까지 3️⃣~4️⃣의 과정을 반복한다.

 

 

📎 문제로 풀어봅시다! 프로그래머스 문제 링크

---

프로그래머스

 

 

🤔 문제설명, 제한사항, 입출력 예

---

n개의 노드가 있는 그래프가 있을 때, 노드의 개수 n, 간선에 대한 정보([a, b]로 구성된 리스트 형태, a노드와 b노드 사이에 간선이 있다는 의미)가 담긴 2차열 배열 vertex가 주어진다. 이때 1번 노드로부터 가장 멀리 떨어진 노드가 몇 개인지를 구하라는 문제이다.

각 노드는 1번부터 n번까지 번호가 적혀있으며, 가장 멀리 떨어진 노드란 "최단경로로 이동했을 때, 간선의 개수가 가장 많은 노드들을 의미"한다. 간선은 양방향으로 이루어진다고 한다. (=무방향 그래프가 사용된다는 의미)

 

 

🤔 내가 생각한 풀이 과정 

---

가장 깊은 노드를 찾아야 하는 문제이므로, BFS (Breadth First Search)의 방식을 사용하는 것이 적당할 것이라고 생각했다.

일단, 노드를 내가 보기 쉽도록 딕셔너리 자료형으로 다시 바꿔줬다.
"1번 노드: [2번 노드, 3번 노드]"의 형태로 구성되어 있으며, Key 노드가 몇 번 노드와 연결되어 있는지를 Value 리스트에 담고 있는 형태이다.

그리고 위에서 설명했던 BFS의 방식대로 탐색을 해줬다.
단, 여기서 각 노드들이 1번 노드와 얼마나 떨어져 있는지를 구해주는 것이 이 문제에 포인트였기 때문에 "거리를 누적"해서 구해줘야 한다.
일단 노드의 개수만큼 0으로 된 distance 리스트를 만들어주고, 반복을 할 때마다 각 노드의 거리를 1씩 더해줄 것이다.
그리고 더 깊이가 깊어질수록, 연결된 노드의 거리(그니까 distance[연결된 노드의 인덱스])를 같이 더하면서 거리가 멀어지는 것을 표현하면 될 것이라 생각했다. (-> 예를 들어, 노드 6은 노드 3보다 하나 더 머니까, 노드 3의 길이 1에다가 1을 더해주는 방식이다.)

마지막에는 전체 distance 리스트에서 최댓값을 구하고, 그 최댓값을 가진 카운트를 구해주면 문제에서 요청하는 반환값을 구해줄 수 있을 것이라 생각했다. 직접 풀어보자!

 

 

🧑🏻‍💻 코드로 확인하기

---

from collections import deque

def solution(n, vertex):
    # 연결된 노드 딕셔너리 형태로 만들기
    graph = {i+1: [] for i in range(n)}
    for v in vertex:
        graph[v[0]].append(v[1])
        graph[v[1]].append(v[0])
    
    # BFS(Breadth-First Search) 활용 탐색하기
    queue = deque([1])                      # 1을 큐에 삽입하고 시작
    distance = [0 for _ in range(n)]        # 노드 1과 얼마나 떨어져 있는지를 구하기 위함
    while queue:
        lq = queue.popleft()                
        for i in graph[lq]:            
            if distance[i-1] == 0:                   # 거리가 0이란 뜻은 아직 방문하지 않았다는 뜻임
                distance[i-1] = distance[lq-1] + 1   # 누적거리를 추가 (예, 노드 6의 경우 노드 3보다 하나 더 멈)
                queue.append(i)
                
    return distance[1:].count(max(distance[1:]))     # 거리가 가장 먼 값들의 카운트