[Swift] 백준 1260 DFS와 BFS 코드 및 해설

 

  문제  

1260번: DFS와 BFS

---

  DFS와 BFS  

[Algorithm] DFS / BFS 탐색 알고리즘

단순한 DFS / BFS를 구현하는 문제여서 설명은 SKIP!

---

  나의 코드  

// n, m, v 입력받기
var info: [Int] = readLine()!.split(separator: " ").map{Int(String($0))!}

// 방문여부 저장
var visited_dfs = [Bool](repeating: false, count: info[0]+1)

// 방문여부 저장(하단에 설명 써 놓을게요)
var visited_bfs = visited_dfs

 // 그래프 초기화
var graph = [[Int]](repeating: [], count: info[0]+1)

//그래프 입력받기
for _ in 1...info[1]{
    let node:[Int] = readLine()!.split(separator: " ").map{Int(String($0))!}
    
    // 간선은 양방향이므로, 다음과 같이 저장해야합니다. 
    graph[node[0]].append(node[1])
    graph[node[1]].append(node[0])
}

func dfs(v: Int){
    visited_dfs[v] = true
    // 개행문자 대신 " "로 출력한다.
    print(v, terminator: " ")
    
    // 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문 
    // (문제조건) -> sorted로 작은 것 먼저 탐색
    for i in graph[v].sorted(){
        if !visited_dfs[i]{
            dfs(v:i)
        }
    }
}

func bfs(v: Int){
    visited_bfs[v] = true
    var queue:[Int] = [v]
    while queue.count != 0{
        let v = queue.removeFirst()
        print(v, terminator: " ")
        
        // 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문 
    	// (문제조건) -> sorted로 작은 것 먼저 탐색
        for i in graph[v].sorted(){
            if !visited_bfs[i]{
                queue.append(i)
                visited_bfs[i] = true
            }
        }
    }
}

// 시작노드를 삽입하여 탐색 시작
dfs(v:info[2])
// dfs 결과와 bfs 결과를 개행문자로 분리한다. (없으면 한줄에 다 출력돼요)
print()
bfs(v:info[2])

---

  Key point!  

📍2차원배열 초기화하는 방법

var graph = [[Int]](repeating: [], count: info[0]+1)

// [[Int]] : 2차원 배열
// count만큼 반복하여 빈 배열을 삽입하여 2차원배열 초기화

---

📍개행문자 없이 출력하기

print(v, terminator: " ")
// python의 end와 동일한 역할

---

📍Swift의 배열 복사

var visited_bfs = visited_dfs

    - 보통 다른 언어에서는 얕은 복사로 간주되어, visited_bfs 값이 변경되면 visited_dfs도 변경된다.

    - 하지만 swift의 경우, 처음에는 얕은 복사가 수행되지만, 배열의 값이 변경되면 깊은 복사가 자동으로 이루어진다.(신기)

---