그래프는 수학적 객체로, 정점(Vertex)와 간선(Edge)로 구성됩니다.
그래프는 데이터 구조에서 핵심적인 역할을 하며, 여러 복잡한 문제를 해결하는 데 효율적인 방식입니다.
이 글에서는 그래프의 기본 개념을 설명하고, 파이썬을 사용하여 그래프를 표현하고 탐색하는 방법을 다룰 것입니다.
1. 그래프의 기본 개념
그래프는 노드와 그 노드를 연결하는 간선으로 이루어져 있습니다. 그래프는 다음과 같은 두 가지 형태로 구분할 수 있습니다:
- 유향 그래프 (Directed Graph): 간선이 방향성을 가진 그래프입니다. 즉, 간선이 A에서 B로 향할 때, B에서 A로의 간선은 존재하지 않을 수 있습니다.
- 무향 그래프 (Undirected Graph): 간선이 방향성을 가지지 않는 그래프입니다. A와 B가 연결된 간선은 양방향으로 존재합니다.
2. 그래프의 표현 방법
그래프는 여러 가지 방법으로 표현할 수 있습니다. 가장 일반적인 방법은 다음과 같습니다:
- 인접 리스트 (Adjacency List): 각 정점에 연결된 정점의 리스트를 유지하여 그래프를 표현합니다. 이 방법은 메모리 사용이 효율적입니다.
- 인접 행렬 (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 08. 마무리
이번 강좌에서는 그래프의 개념과 다양한 표현 방법을 알아보았습니다. 문제를 통해 인접 리스트와 인접 행렬을 생성하는 방법도 배웠고, 이를 실제로 구현함으로써 그래프의 기본 구조를 이해할 수 있었습니다. 그래프 탐색(DFS, BFS) 등 더 나아가 해결해야 할 문제들이 많으니, 이를 토대로 다음 단계로 나아가기를 바랍니다.
알고리즘 공부를 하며 다양한 그래프 문제를 풀어보세요. 감사합니다!