[PS] 간단한 Graph 개념과 BFS, DFS 템플릿

Graph

그래프는 정점(vertex)과 간선(edge)의 집합이다. G(V,E)로 표현할 수 있다.

그래프의 종류에는 방향 그래프와 무향 그래프(PS에서 가장 많이 등장), 다중 그래프와 단순 그래프, 가중치 그래프(다익스트라) 등이 있다.

그래프는 현실의 문제를 해결하기 위한 도구로 많이 쓰이기 때문에 문제로 많이 출제된다.

그래프의 예로, 도시들을 연결하는 도로망 (정점 - 도시, 간선 - 도로), 지하철 노선도 (정점 - 정거장, 간선 - 노선), 컴퓨터 네트워크 (정점 - 컴퓨터와 라우터, 간선 - 연결 관계) 등이 있다.

 

그래프의 표현 방법으로 인접 행렬, 인접 리스트, 암시적 그래프가 있다. 

인접 행렬은 모든 연결 관계를 나타낸 것이다. 메모리가 많이 들어 비효율적이다.

인접 리스트는 연결된 정점들만 표시한 것이다. 필요한 것만 표시했기 때문에 메모리적으로 효율적이다. 다만 표시할 정보가 많다면 인접 행렬로 표현하는 게 더 직관적이고 낫다.

암시적 그래프는 연결 관계를 표시하지 않고, 전체 맵을 그린 것으로 문제 중에서 미로 찾기 등이 있다.

 

나타낼 그래프

좌측부터 인접 행렬, 인접 리스트

암시적 그래프

 

Graph 탐색 방법 : BFS와 DFS

그래프의 탐색 방법으로 BFS와 DFS가 있다. 이 템플릿은 그냥 외워버리는 게 응용에도 좋다. 30초 안에 칠 수 있을 정도로 외우자.

밑의 graph를 바탕으로 BFS와 DFS를 알아보자.

let graph = ["A": ["B","D","E"],
             "B": ["A","C","E"],
             "C": ["B"],
             "D": ["A","B"],
             "E": ["A"]]

 

BFS

흐름 by 큐

 1. 방문한 배열 visited와 큐 queue가 필요하다. 이 둘을 선언할 때 시작 노드인 start를 넣어서 선언해버린다.

 2. queue가 빌 때까지 while문을 돌리는데, 어떤 내용으로 돌리냐면

 3. queue에서 맨 앞에 있는 값을 빼고, current 상수에 담아서 현재 노드라고 표시한다.

 4. current와 연결된 노드들 중에서 아직 방문하지 않은 노드들은 queue에 넣는다.

 5. 또한, 방문했다는 visited 배열에도 넣는다.

 6. 3,4,5를 while문을 통해 반복한다.

 7. visited를 출력한다.

 

코드

func bfs(_ graph: [String:[String]], _ start: String) -> [String] {
    var visited = [start]
    var queue = [start]
    
    while !queue.isEmpty {
        let current = queue.removeFirst()
        
        for node in graph[current] ?? [] {
            if !visited.contains(node) {
                queue.append(node)
                visited.append(node)
            }
        }
    }
    
    return visited
}

print(bfs(graph, "A"))
// ["A", "B", "D", "E", "C"]

 

 

DFS

흐름 by 재귀

 1. dfs 함수 밖에서 전역 변수로 visited라는 빈 배열을 선언해준다. 왜냐면, 재귀를 이용할 것이기 때문에, 전역 변수가 필요하다.

 2. dfs 함수 전달 인자는 현재 노드 하나다. visited에 현재 노드를 추가하고 방문했다는 표시를 한다.

 3. 현재 노드에 연결된 노드 중, 아직 방문하지 않은 노드가 있다면 재귀를 통해 방문한다. (for문으로 탐색)

 4. 함수가 끝나고, visited 배열을 출력해본다.

 

코드

var visited = [String]()

func dfs(_ current: String) {
    visited.append(current)
    for node in graph[current] ?? [] {
        if !visited.contains(node) {
            dfs(node)
        }
    }
}

dfs("A")
// ["A", "B", "C", "E", "D"]

재귀를 곁들인 dfs(_ current: String) 함수의 의미 : current에 연결된 노드를 탐색한다.

dfs 내부에서 dfs를 재귀적으로 호출한다?! -> 얘 node야, 너한테 연결된 애들 너가 알아서 탐색해와. 난 기다리고 있을게. (위임!)

 

 

출처 : 개발남노씨