안녕하세요! 오늘은 코틀린을 사용하여 코딩테스트에서 자주 나오는 그래프의 표현 방법에 대해 자세히 알아보겠습니다. 그래프는 여러 분야에서 꽤 중요한 자료구조로, 다양한 문제를 해결할 때 필수적인 근본기능을 가지고 있습니다. 이번 글에서는 그래프를 어떻게 표현하고, 그 표현을 사용하여 문제를 해결하는 방법을 설명하겠습니다.
그래프란 무엇인가?
그래프는 노드(정점)와 엣지(간선)로 구성된 자료구조입니다. 노드는 객체를 나타내며, 엣지는 노드 간의 관계를 나타냅니다. 그래프는 방향성에 따라 방향 그래프와 무향 그래프로 나눌 수 있으며, 가중치 여부에 따라 가중 그래프와 비가중 그래프로 나눌 수 있습니다.
그래프의 표현 방법
그래프는 다양한 방법으로 표현할 수 있으며, 가장 흔한 두 가지 방법은 인접 행렬(Adjacency Matrix)과 인접 리스트(Adjacency List)가 있습니다.
1. 인접 행렬
인접 행렬은 N x N 크기의 2차원 배열을 사용하여 그래프를 표현하는 방법입니다. N은 그래프의 노드 수이며, 행렬의 각 요소는 노드 간의 연결 여부를 나타냅니다. 예를 들어, 노드 A와 노드 B가 연결되어 있다면, matrix[A][B]는 1이 됩니다.
fun createAdjacencyMatrix(vertices: Int, edges: List>): Array> {
val matrix = Array(vertices) { Array(vertices) { 0 } }
for (edge in edges) {
val (from, to) = edge
matrix[from][to] = 1
matrix[to][from] = 1 // 무향 그래프의 경우
}
return matrix
}
2. 인접 리스트
인접 리스트는 각 노드에 대해 연결된 노드를 저장하는 리스트를 사용하는 방법입니다. 이 방식은 메모리 사용 면에서 효율적이며, 노드 수가 적거나 간선 수가 적은 그래프에서 유리합니다.
fun createAdjacencyList(vertices: Int, edges: List>): List> {
val list = MutableList(vertices) { mutableListOf() }
for (edge in edges) {
val (from, to) = edge
list[from].add(to)
list[to].add(from) // 무향 그래프의 경우
}
return list
}
문제: 친구 관계 네트워크
다음은 친구 관계를 나타내는 그래프의 문제입니다.
문제: N명의 사람과 그들 사이의 친구 관계가 주어질 때, 두 사람 사이의 친구 관계가 존재하는지 확인하는 프로그램을 작성하시오. 친구 관계는 무향 그래프로 표현된다. 단, 두 사람의 번호는 0부터 N-1까지 연속적으로 주어진다.
문제 해결 과정
1. 입력 형식 이해
먼저 주어지는 데이터를 이해해야 합니다. 입력은 다음과 같습니다:
- 첫 번째 줄에 사람의 수 N이 주어진다.
- 두 번째 줄에 친구 관계의 수 M이 주어진다.
- 이후 M개의 줄에 걸쳐 각 친구 관계를 나타내는 두 정수 a, b가 주어진다.
2. 데이터 구조 선택
주어진 친구 관계를 저장하기 위해 인접 리스트를 사용합니다. 이렇게 하면 친구 관계를 쉽게 탐색할 수 있습니다.
3. 그래프 생성
fun main() {
val reader = BufferedReader(InputStreamReader(System.`in`))
val n = reader.readLine().toInt()
val m = reader.readLine().toInt()
val edges = mutableListOf>()
for (i in 0 until m) {
val (a, b) = reader.readLine().split(" ").map { it.toInt() }
edges.add(Pair(a, b))
}
val adjacencyList = createAdjacencyList(n, edges)
}
4. 친구 관계 확인
특정 두 사람의 친구 관계를 확인하는 방법은 DFS(Depth First Search) 또는 BFS(Breadth First Search)를 사용하여 연결 여부를 체크하는 것입니다. 여기서는 DFS를 사용하여 구현해 보겠습니다.
fun isConnected(adjList: List>, start: Int, target: Int, visited: BooleanArray): Boolean {
if (start == target) return true
visited[start] = true
for (neighbor in adjList[start]) {
if (!visited[neighbor]) {
if (isConnected(adjList, neighbor, target, visited)) {
return true
}
}
}
return false
}
fun main() {
// 이전 코드와 이어서
val query = reader.readLine().split(" ").map { it.toInt() }
val (x, y) = query
val visited = BooleanArray(n) { false }
val result = isConnected(adjacencyList, x, y, visited)
println(if (result) "YES" else "NO")
}
결론
이번 강좌에서는 그래프의 기본 개념 및 표현 방법, 그리고 이를 활용하여 친구 관계 네트워크 문제를 해결하는 방법에 대해 알아보았습니다. 그래프는 다양한 문제를 해결하는 데 필수적이며, 알고리즘 테스트에서 이러한 그래프 표현 및 탐색 기술은 매우 유용합니다.
코틀린을 사용하여 예제를 구현해 보았으니, 직접 다양한 그래프 문제를 풀어보며 연습해보시기 바랍니다. 다음 시간에는 BFS와 DFS의 차이점과 이를 활용한 다양한 문제 해결 전략에 대해 다뤄보겠습니다. 여러분의 학습 여정에 도움이 되기를 바랍니다!