스위프트 코딩테스트 강좌, 경로 찾기

안녕하세요, 이번 강좌에서는 스위프트 언어를 사용하여 경로 찾기 문제를 해결하는 방법에 대해 알아보겠습니다. 경로 찾기는 코딩 테스트에서 자주 등장하는 문제 유형 중 하나로, 주어진 그래프에서 특정 두 노드 간의 경로를 찾는 문제입니다. 이 글에서는 문제를 정의하고, 해결하는 과정에서 필요한 알고리즘과 데이터 구조에 대해 심도 있게 다루겠습니다.

문제 정의

다음과 같은 문제를 고려해보겠습니다:

문제: 주어진 방향 그래프에서 두 노드 A와 B 사이의 경로가 존재하는지 여부를 판별하는 함수를 작성하시오. 그래프는 인접 리스트 형태로 주어지며, 노드와 엣지는 정수로 표현됩니다.

입력:

  • 정수 N: 노드의 수 (1 ≤ N ≤ 1000)
  • 정수 M: 엣지의 수 (1 ≤ M ≤ 10000)
  • 리스트의 길이 M: 각 엣지는 [u, v] 형태로 노드 u에서 노드 v로의 방향을 나타냅니다.
  • 정수 A, B: 경로 여부를 확인할 시작 노드 A와 도착 노드 B.

출력:

  • 노드 A에서 노드 B로의 경로가 존재하면 “YES”를, 존재하지 않으면 “NO”를 출력한다.

문제 분석

이 문제는 그래프 이론에서 ‘경로 탐색’ 문제에 해당하며, 여러 가지 방법으로 해결할 수 있습니다. DFS(깊이 우선 탐색) 또는 BFS(너비 우선 탐색)를 이용하여 경로를 탐색할 수 있으며, 이 두 알고리즘 모두 인접 리스트 형태의 그래프를 효과적으로 탐색할 수 있습니다.

알고리즘 선택

이번 강좌에서는 BFS를 사용하여 그래프를 탐색하겠습니다. BFS는 큐를 활용하여 각 노드를 레벨 순으로 탐색하는 알고리즘으로, 최단 경로를 찾는 데 유리합니다. 그래프 탐색을 통해 도착 노드에 도달할 수 있는지를 확인할 것입니다.

스위프트 코드 구현

이제 실제 스위프트 코드를 작성해 보겠습니다. 아래는 BFS를 사용한 경로 탐색 함수의 예시입니다.

        
        import Foundation

        func canReach(start: Int, end: Int, edges: [[Int]], nodeCount: Int) -> String {
            var adjacencyList = [[Int]](repeating: [Int](), count: nodeCount + 1)
            for edge in edges {
                adjacencyList[edge[0]].append(edge[1])
            }

            var queue = [start]
            var visited = [Bool](repeating: false, count: nodeCount + 1)
            visited[start] = true

            while !queue.isEmpty {
                let current = queue.removeFirst()

                if current == end {
                    return "YES"
                }

                for neighbor in adjacencyList[current] {
                    if !visited[neighbor] {
                        visited[neighbor] = true
                        queue.append(neighbor)
                    }
                }
            }
            return "NO"
        }

        // 예제 입력
        let nodeCount = 6
        let edges = [[1, 2], [1, 3], [2, 4], [4, 5], [3, 6]]
        let start = 1
        let end = 5

        print(canReach(start: start, end: end, edges: edges, nodeCount: nodeCount))

코드 설명

위 코드를 분석해보면 다음과 같은 단계로 구성되어 있습니다:

  1. 인접 리스트 형태의 그래프를 생성합니다. 각 노드에 대해 연결된 노드를 저장합니다.
  2. BFS 탐색을 위한 큐를 초기화하고, 시작 노드를 방문한 것으로 표시합니다.
  3. 큐가 빌 때까지 다음 과정을 반복합니다:
    • 큐의 맨 앞에서 노드를 가져옵니다.
    • 가져온 노드가 목적지 노드와 같다면 “YES”를 반환합니다.
    • 현재 노드의 모든 인접 노드에 대해, 방문하지 않았던 노드는 큐에 추가하고 방문 표시를 합니다.
  4. 큐가 비었지만 끝 노드에 도달하지 못했다면 “NO”를 반환합니다.

복잡도 분석

BFS 알고리즘의 시간 복잡도는 O(V + E)로, V는 노드의 수, E는 엣지의 수입니다. 이 문제에서 주어진 최대 조건을 고려할 때, 매우 효율적입니다. 메모리 복잡도 또한 인접 리스트를 저장하기 위해 O(V + E)가 소요됩니다.

테스트 및 활용

주어진 함수는 여러 다양한 그래프 구조에 대해 적용 가능하며, 각각 테스트할 수 있습니다. 아래 추가 테스트 케이스 몇 가지를 살펴보겠습니다.

        
        // 추가 테스트 케이스
        let additionalEdges1 = [[1, 2], [2, 3], [3, 4], [4, 5]]
        let additionalEdges2 = [[1, 2], [2, 3], [3, 4], [2, 5]]
        
        print(canReach(start: 1, end: 5, edges: additionalEdges1, nodeCount: nodeCount)) // NO
        print(canReach(start: 1, end: 5, edges: additionalEdges2, nodeCount: nodeCount)) // YES

결론

이번 강좌에서는 스위프트를 사용하여 그래프에서 경로를 찾는 문제를 해결하는 방법을 알아보았습니다. BFS 알고리즘을 통해 문제를 효과적으로 해결할 수 있었으며, 이와 같은 알고리즘은 코딩 테스트에서 매우 중요합니다. 실전에서 비슷한 문제를 만났을 때, 이번 강좌에서 배운 내용을 바탕으로 문제를 해결할 수 있을 것입니다.

이제 여러분도 다양한 그래프 문제를 풀어보며 알고리즘 실력을 기를 차례입니다. 계속해서 연습해보세요!