스위프트 코딩테스트 강좌, 그래프의 표현

1. 서론

소프트웨어 개발 분야에서 알고리즘 및 자료구조에 대한 이해는 매우 중요합니다. 특히 코딩 테스트에서 자주 등장하는 문제 중 하나가 바로 그래프 관련 문제입니다. 그래프는 노드(정점)와 엣지(간선)로 구성된 자료구조로, 다양한 형태로 데이터를 표현할 수 있습니다. 이 강좌에서는 그래프의 표현 방식과 관련된 알고리즘 문제를 통해 더 깊이 있게 이해할 수 있도록 하겠습니다.

2. 그래프의 표현

그래프를 표현하는 방법은 주로 두 가지 방식으로 나뉩니다.

  • 인접 행렬(Adjacency Matrix): 그래프의 모든 정점에 대해 2차원 배열을 사용하여 간선의 유무를 표현합니다. 이 방식은 정점의 개수가 적을 때 유용합니다. 배열의 크기는 O(V^2)입니다.
  • 인접 리스트(Adjacency List): 각 정점에 대해 연결된 정점을 리스트로 저장하는 방식입니다. 메모리 효율이 좋으며, 간선의 개수가 적은 그래프에 적합합니다. 이 방식의 시간 복잡도는 O(V + E)입니다.

3. 문제 설명

다음 문제를 통해 그래프의 표현 방식을 실제로 적용해보겠습니다.

문제: 친구 네트워크

당신은 N명의 친구가 있는 네트워크를 관리하고 있습니다. 친구 관계는 양방향이며, 두 친구가 직접적으로 연결되어 있다면 그들은 서로의 친구입니다. 친구 관계를 그래프로 표현하고, 특정 두 친구가 같은 친구 그룹에 속하는지 확인하는 프로그램을 작성하세요. 친구 그룹은 간접적으로 연결된 모든 친구를 포함합니다.

입력 형식:

N (친구의 수)
M (친구 관계의 수)
M개의 줄에 걸쳐 두 친구 A와 B (1 ≤ A, B ≤ N)가 주어집니다.

출력 형식:

A와 B가 같은 친구 그룹에 속하면 "YES"를, 그렇지 않으면 "NO"를 출력합니다.

4. 문제 풀이 과정

4.1. 그래프 생성

먼저, 입력으로 주어진 친구 관계를 바탕으로 그래프를 생성해야 합니다. 우리는 인접 리스트를 사용하여 이를 구현하겠습니다. 다음은 그래프 생성을 위한 간단한 스위프트 코드입니다.


import Foundation

// 그래프를 표현하기 위한 인접 리스트
var graph: [Int: [Int]] = [:]

// 친구 관계를 추가하는 함수
func addFriendRelation(friendA: Int, friendB: Int) {
    graph[friendA, default: []].append(friendB)
    graph[friendB, default: []].append(friendA)
}

// 그래프 생성 함수
func createGraph(N: Int, relations: [(Int, Int)]) {
    for (A, B) in relations {
        addFriendRelation(friendA: A, friendB: B)
    }
}

위 코드는 각 친구를 키로 하고 연결된 친구들의 리스트를 값으로 가지는 딕셔너리를 만들어 그래프를 생성합니다.

4.2. 친구 그룹 찾기

이제 두 친구가 같은 그룹에 속하는지 확인하기 위해 그래프 탐색 알고리즘 중 하나를 사용할 수 있습니다. 깊이 우선 탐색(DFS) 또는 너비 우선 탐색(BFS)를 사용할 수 있는데, 여기서는 DFS를 선택하겠습니다. DFS를 통해 연관된 친구들을 모두 탐색할 수 있습니다.


func dfs(start: Int, visited: inout Set) {
    visited.insert(start)
    for friend in graph[start, default: []] {
        if !visited.contains(friend) {
            dfs(start: friend, visited: &visited)
        }
    }
}

// 두 친구가 같은 그룹에 속하는지 확인하는 함수
func areInSameGroup(friendA: Int, friendB: Int) -> Bool {
    var visited = Set()
    dfs(start: friendA, visited: &visited)
    return visited.contains(friendB)
}

4.3. 전체 프로세스

이제 전체 과정을 통합하여 문제를 해결해보겠습니다. 입력을 받고, 그래프를 생성하고, 두 친구의 관계를 확인하는 코드입니다.


let N = Int(readLine()!)! // 친구의 수
let M = Int(readLine()!)! // 친구 관계의 수

var relations = [(Int, Int)]()

for _ in 0..

위 코드는 전체 흐름을 통해 친구 관계를 표현하고 검사하는 로직을 구현한 것입니다.

5. 결론

이번 강좌를 통해 그래프의 표현 방법과 기본적인 DFS 알고리즘을 활용하여 문제를 해결하는 방법에 대해 살펴보았습니다. 그래프는 다양한 문제에 적용될 수 있는 유용한 자료구조로, 충분한 연습을 통해 숙지할 필요가 있습니다. 코딩 테스트에서도 이러한 문제가 종종 출제되므로, 문제를 여러 번 풀어보며 실력을 향상시키길 바랍니다.

© 2023 스위프트 코딩테스트 강좌. All Rights Reserved.