파이썬 코딩테스트 강좌, 그래프의 표현

그래프는 수학적 객체로, 정점(Vertex)와 간선(Edge)로 구성됩니다.
그래프는 데이터 구조에서 핵심적인 역할을 하며, 여러 복잡한 문제를 해결하는 데 효율적인 방식입니다.
이 글에서는 그래프의 기본 개념을 설명하고, 파이썬을 사용하여 그래프를 표현하고 탐색하는 방법을 다룰 것입니다.

1. 그래프의 기본 개념

그래프는 노드와 그 노드를 연결하는 간선으로 이루어져 있습니다. 그래프는 다음과 같은 두 가지 형태로 구분할 수 있습니다:

  • 유향 그래프 (Directed Graph): 간선이 방향성을 가진 그래프입니다. 즉, 간선이 A에서 B로 향할 때, B에서 A로의 간선은 존재하지 않을 수 있습니다.
  • 무향 그래프 (Undirected Graph): 간선이 방향성을 가지지 않는 그래프입니다. A와 B가 연결된 간선은 양방향으로 존재합니다.

2. 그래프의 표현 방법

그래프는 여러 가지 방법으로 표현할 수 있습니다. 가장 일반적인 방법은 다음과 같습니다:

  1. 인접 리스트 (Adjacency List): 각 정점에 연결된 정점의 리스트를 유지하여 그래프를 표현합니다. 이 방법은 메모리 사용이 효율적입니다.
  2. 인접 행렬 (Adjacency Matrix): 그래프의 모든 정점을 행렬 형태로 표현합니다. 행렬의 각 원소는 두 정점 간의 연결 여부를 나타냅니다.

3. 문제 풀이: 그래프의 표현

이제 그래프를 표현하는 실제 문제를 풀어보겠습니다.

문제 설명

정점의 개수와 간선의 정보를 입력받아, 주어진 정보를 바탕으로 그래프를 인접 리스트와 인접 행렬 형태로 표현하는 프로그램을 작성하시오.

입력 형식:

  • 첫 번째 줄에 정점의 개수 N (1 ≤ N ≤ 100)이 주어진다.
  • 두 번째 줄에 간선의 개수 M (1 ≤ M ≤ 1000)이 주어진다.
  • 세 번째 줄부터 M개의 줄에 걸쳐 간선의 정보 (A, B)가 주어진다. A와 B는 1에서 N까지의 정수이며, A와 B가 연결되어 있음을 나타낸다.

출력 형식:

첫 번째 줄에 인접 리스트, 두 번째 줄에 인접 행렬을 출력하시오. 각 정점은 1부터 시작한다.

4. 문제 해결 과정

위 문제를 해결하기 위해 풀어야 할 단계는 다음과 같습니다:

4.1. 입력 처리

먼저, 사용자로부터 정점과 간선 정보를 입력받습니다. 파이썬의 input() 함수를 사용하여 입력을 받고, 이를 적절한 형태로 변환합니다.

4.2. 인접 리스트 생성

인접 리스트는 리스트의 리스트를 사용하여 각 정점에 연결된 정점들을 저장합니다. 이때, 정점의 번호는 1부터 시작하므로 리스트의 인덱스와 맞추기 위해 미리 빈 리스트를 추가합니다.

4.3. 인접 행렬 생성

인접 행렬은 2차원 배열을 사용하여 정점 간의 연결 여부를 저장합니다. 초기값은 0으로 설정하고, 간선이 존재하는 경우에는 1로 설정합니다. 무향 그래프인 경우 A-B의 연결이 있을 때, 행렬의 (A, B)와 (B, A) 모두 업데이트해야 합니다.

4.4. 결과 출력

마지막으로, 생성된 인접 리스트와 인접 행렬을 출력합니다.

5. 코드 구현

def graph_representation():
    # 입력 받기
    N = int(input("정점의 개수를 입력하세요 (1 ≤ N ≤ 100): "))
    M = int(input("간선의 개수를 입력하세요 (1 ≤ M ≤ 1000): "))
    
    # 인접 리스트 초기화
    adj_list = [[] for _ in range(N + 1)]
    
    # 인접 행렬 초기화
    adj_matrix = [[0] * (N + 1) for _ in range(N + 1)]
    
    # 간선 정보 입력
    for _ in range(M):
        A, B = map(int, input("간선 정보를 입력하세요 (A B): ").split())
        adj_list[A].append(B)
        adj_list[B].append(A)  # 무향 그래프
        adj_matrix[A][B] = 1
        adj_matrix[B][A] = 1  # 무향 그래프
    
    # 인접 리스트 출력
    print("인접 리스트:")
    for i in range(1, N + 1):
        print(f"{i}: {adj_list[i]}")
    
    # 인접 행렬 출력
    print("인접 행렬:")
    for i in range(1, N + 1):
        print(" ".join(map(str, adj_matrix[i][1:])))
        
# 함수 호출
graph_representation()

6. 코드 설명

위 Python 코드는 아래의 절차로 구성되어 있습니다:

  • 입력 처리: 정점과 간선의 개수를 입력받고, 각 간선에 대한 정보를 입력받습니다.
  • 인접 리스트 초기화: 정점의 개수 N에 맞춰 빈 리스트를 생성합니다.
  • 인접 행렬 초기화: N x N 크기의 행렬을 0으로 초기화합니다.
  • 간선 정보 입력 및 리스트/행렬 업데이트: 반복문을 통해 입력받은 A, B에 따라 인접 리스트와 행렬을 업데이트합니다.
  • 결과 출력: 인접 리스트와 인접 행렬을 각각 출력합니다.

7. 실행 예시

예를 들어, 5개의 정점과 6개의 간선이 있는 그래프의 경우 입력과 출력은 다음과 같습니다:

정점의 개수를 입력하세요 (1 ≤ N ≤ 100): 5
간선의 개수를 입력하세요 (1 ≤ M ≤ 1000): 6
간선 정보를 입력하세요 (A B): 1 2
간선 정보를 입력하세요 (A B): 1 3
간선 정보를 입력하세요 (A B): 2 4
간선 정보를 입력하세요 (A B): 3 4
간선 정보를 입력하세요 (A B): 4 5
간선 정보를 입력하세요 (A B): 2 5
인접 리스트:
1: [2, 3]
2: [1, 4, 5]
3: [1, 4]
4: [2, 3, 5]
5: [2, 4]
인접 행렬:
0 1 1 0 0
1 0 0 1 1
1 0 0 1 0
0 1 1 0 1
0 1 0 1 0

8. 마무리

이번 강좌에서는 그래프의 개념과 다양한 표현 방법을 알아보았습니다. 문제를 통해 인접 리스트와 인접 행렬을 생성하는 방법도 배웠고, 이를 실제로 구현함으로써 그래프의 기본 구조를 이해할 수 있었습니다. 그래프 탐색(DFS, BFS) 등 더 나아가 해결해야 할 문제들이 많으니, 이를 토대로 다음 단계로 나아가기를 바랍니다.

알고리즘 공부를 하며 다양한 그래프 문제를 풀어보세요. 감사합니다!