[Swift 알고리즘] 백준 1260 DFS와 BFS

× 

DFS/BFS 

백준 1260 DFS와 BFS

문제
그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.
입력
첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.
출력
첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

노드들과 간선, 시작 노드가 주어질 때, 서로 연결된 노드들을 파악하여 BFS와 DFS로 구현하는 문제.

DFS BFS 개념만 알고 실제 코드로 구현해보는 건 처음이었다. 

 

1. 그래프 그리기

탐색 구현도 중요하지만 그 전에 노드와 간선들을 어떻게 그릴지가 중요한 것 같다.

0과 1을 이용하여 행렬로 저장해줄 수도 있고

노드 별로 간선을 그대로 저장해서 구현해줄 수도 있다. 

- 행렬

인접행렬 방식으로 행과 열을 통해서 해당 숫자들이 연결되어 있는지 확인할 수 있다. 

인덱스와 노드 값을 일치시키기 위해 n+1 개의 열과 행을 만들어 초기값을 0으로 설정해준다. 

행렬을 표현할 때, 간선의 방향이 양방향이기 떄문에 x,y / y,x 둘 다 1로 바꾸어 준다.   

var matrix = Array(repeating: Array(repeating: 0, count: n+1), count: n+1)

for _ in 0..<m {
    let edge = readLine()!.split(separator: " ").compactMap{ Int($0) }
    matrix[edge[0]][edge[1]] = 1
    matrix[edge[1]][edge[0]] = 1
}

- 그래프 

빈 이차원 배열을 만들어준 후, 입력값을 받아 해당 인덱스 배열에 연결 노드를 append 해준다.  

입력값으로부터 인접리스트 그래프를 만들 때, 들어가는 인자값을 sort 해주어야 정확한 순서로 그래프를 탐색할 수 있다. 

var graph: [[Int]] = Array(repeating: [], count: n+1)

for _ in 0..<m {
    let edge = readLine()!.split(separator: " ").compactMap{ Int($0) }
    graph[edge[0]].append(edge[1])
    graph[edge[1]].append(edge[0])
}

graph = graph.map { $0.sorted() }

2-1. DFS 함수 정의

재귀함수를 이용하여 dfs 함수를 구현해줄 수 있다.

var visited = Array(repeating: false, count: n+1)

func dfs(_ v: Int) {
    visited[v] = true
    print(v, terminator: " ")
    
    for num in graph[v] {
        if !visited[num] {
            dfs(num)
        }
    }
}

2-2. BFS 함수 정의

Queue를 이용하여 bfs 함수를 구현해줄 수 있다. 

var visited = Array(repeating: false, count: n+1)
var queue = [Int]()

func bfs(_ start: Int) {
    queue.append(start)
    visited[start] = true
    
    while !queue.isEmpty {
        let v = queue[0]
        print(v, terminator: " ")
        queue.removeFirst()

        for num in graph[v] {
            if !visited[num] {
                queue.append(num)
                visited[num] = true
            }
        }
    }
}

 

 

https://github.com/hongssup/algorythm/commit/b4abb02d100385ce12bb8b3dd648bcdb833bda30?diff=unified 

Baekjoon 1260 DFS와 BFS · hongssup/algorythm@b4abb02