백준 1260 - Swift

백준 1260 - Swift

https://www.acmicpc.net/problem/1260

 

 

DFS, BFS의 기본 문제로 개념을 알고있다면 쉽게 구현이 가능한 문제입니다!

 

 

그런 기념으로 간단하게 정리해보는 DFS, BFS

 

1) DFS - Depth First Search (깊이우선탐색)

• 완전 탐색 기법 중 하나로써
  그래프의 시작노드부터 한쪽 분기의 최대 깊이까지 탐색 후 다른쪽 분기로 이동하여 모두 탐색을 완료하는 기법
• 노드의 개수를 V, 에지의 개수를 E라고 했을 때, 시간 복잡도는 O(V+E)
• 재귀 함수, 스택으로 구현함
• 스택으로 구현하는 이유는, "그래프의 시작노드부터 한쪽 분기의 최대 깊이까지 탐색 후"에 따라 결정되는 방법임
• 깊이로 탐색하는 것을 이미지로 그려보면 마지막까지 들어갔다가 그 위부터 pop되는 형식이기 때문에
  자료구조에서 pop, push에서 동일한 구현을 가진 스택을 사용하는 것!
• ⭐️ 주의사항 ⭐️ : 한번 방문한 노드를 다시 방문하면 안되기 때문에, 노드 방문 여부를 체크할 배열을 활용해야함! (인접 리스트 사용)

=> 구현 시 스택에 노드를 삽입할 때 방문 배열을 체크하고,

      스택에서 노드를 뺄때 탐색 순서에 기록하며 인접 노드를 방문 배열과 대조해야함!

 

 

2) BFS - Breath First Search (너비우선탐색)

• 완전 탐색 기법 중 하나로써 시작 노드를 기준으로 가까운 노드를 방문하면서 탐색하는 알고리즘
• 가까운 노드를 방문하고 나서야 다음 인접 노드를 탐색하기 때문에 FIFO 성질을 갖고 있음
• 자료구조 중 FIFO인 Queue를 이용하여 구현 가능
• DFS와 동일한 시간 복잡도 O(V+E)
• ⭐️ 주의사항 ⭐️ : 한번 방문한 노드를 다시 방문하면 안되기 때문에, 노드 방문 여부를 체크할 배열을 활용해야함! (인접 리스트 사용)

=> 구현 시 큐에 들어간느 순간 방문 배열에 추가하여 구현하면 쉽다!

 

 

 

---

 

 

 

DFS 를 Swift로 구현하기 (Stack의 성질 + 재귀함수)

import Foundation

let input = readLine()!.split(separator: " ").map { Int($0)! }
let n = input[0] // 정점의 개수
let m = input[1] // 간선의 개수
let start = input[2] // 탐색을 시작할 정점의 번호

// 그래프의 리스트화를 위한 2차원 배열 생성 (노트는 1부터 카운팅 되기 때문에 n+1)
var arrayList = [[Int]](repeating: [Int](), count: n + 1)
// DFS 탐색경로를 담을 배열 == 즉, 정답
var sortedDFS = [Int]()
// BFS 탐색 경로를 담을 배열
var sortedBFS = [Int]()

// 엣지 크기만큼 반복하면서 그래프를 리스트화하기
for _ in 0..<m {
    let value = readLine()!.split(separator: " ").map { Int($0)! }
    let s = value[0]
    let e = value[1]
    arrayList[s].append(e)
    arrayList[e].append(s)
}

// 문제 조건에 맞도록 오름차순으로 정렬하기
for i in 0...n {
    arrayList[i].sort()
}

func excuteDFS(_ node: Int) {
    // 방문한 값 체킹하는 배열
    var visitedValue = Array(repeating: false, count: n+1)
    // DFS 함수 실행
    DFS(start, &visitedValue)
}

func DFS(_ node: Int, _ visitedValue: inout [Bool]) {
    visitedValue[node] = true // 방문한 노트 체킹
    sortedDFS.append(node) // 팀색 경로
    // 방문한 노드의 인접 노드 확인
    for i in arrayList[node] {
        if !visitedValue[i] {
            DFS(i, &visitedValue)
        }
    }
}

 

 

BFS 를 Swift로 구현하기 (Queue의 성질 + 재귀함수)

(위에서 사용한 N,M,Start 동일하게 사용!)

func BFS(_ node: Int) {
    // 방문한 값 체킹하는 배열
    var visited = Array(repeating: false, count: n+1)

    // BFS를 위한 큐 생성
    var queue = [Int]()
    queue.append(node)
    
    // 큐에 들어가는 순간 visited 배열 값 true
    visited[node] = true
    
    // queue에 값이 없을 때까지
    while !queue.isEmpty {
        let currentNode = queue.removeFirst()
        sortedBFS.append(currentNode) // pop된 노드는 탐색이 완료된 노드
        visited[node] = true
        
        for i in arrayList[currentNode] {
            if !visited[i] {
                visited[i] = true
                queue.append(i)
            }
        }
    }
}

 

 

출력

excuteDFS(start)
BFS(start)

print(sortedDFS.map({ String($0) }).joined(separator: " "))
print(sortedBFS.map({ String($0) }).joined(separator: " "))