[백준] (Swift) 1260번 - DFS와 BFS

 

문제 링크

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

1260번: DFS와 BFS

 

문제 풀이

https://didu-story.tistory.com/98

[알고리즘] 탐색 알고리즘 DFS, BFS

• dfs와 bfs 코드를 따로 function으로 구성해서 풀었다.
• visited에 True False 로 노드 방문 여부를 체크했다. 단, DFS먼저 출력하고, BFS를 출력하기 때문에 BFS에서는 방문한노드가 true로 바뀌어져 있기 때문에 이걸 false로 바꾸면서 풀었다.

 

✔️ DFS 구현

func dfs(_ v: Int) {
    visited[v] = true
    print(v, terminator: " ")
    for i in 1..<n+1 {
        if visited[i] == false && matrix[v][i] == 1 {
            dfs(i)
        }
    }
}

• v 는 start 노드이다. 그래서 탐색을 시작하자마자 노드 v 는 바로 방문체크를 해준다. 
• 문제에서는 탐색을 하면서, 방문한 노드들을 순서대로 출력해야한다. 그래서 바로 v를 출력해준다.
• print에서 terminator는 줄바꿈을 하지 않고, "" 안에 있는 문자를 통해 연결시켜서(?) 출력해준다.
• 반복문을 통해서 dfs 재귀를 활용할 것이다. (내가 그래프를 어떻게 그렸느냐에 따라 함수가 달라질 것이다)
  • 1부터 차례대로 방문여부를 판단하면서 반복문을 돌린다.
  • 만약 방문하지 않았고, 근데 그게 시작노드와 연결되어있는 노드라면, dfs에 넣어서 재귀로 돌려준다.

 

✔️ BFS 구현

func bfs(_ v: Int) {
    var queue: [Int] = []
    visited[v] = false // dfs 돌아가면서 true 로 바뀐거 false 로 돌리면서 go
    queue.append(v)
    
    while !queue.isEmpty {
        var newV = queue.removeFirst()
        print(newV, terminator: " ")
        
        for i in 1..<n+1 {
            if visited[i] == true && matrix[newV][i] == 1 {
                queue.append(i)
                visited[i] = false
            }
        }
        
    }
    
}

• 주의 ) 이 함수에서는 방문했다는게 false, 방문하지 않은 노드가 true 
• 먼저 queue를 구성해주었다. queue는 원래 파이썬에서 dequeue로 만들어주면서,  pop 하면서 쉽게 데이터를 뽑을 수 있는데, 스위프트는 dequeue 기능과 pop 기능이 따로 없어서, removeFirst() 로 해야한다. 
  • 하지만 removeFirst는 O(n) 시간복잡도를 가진다. 그래서 시간초과가 나올 수도 있다. (해당 문제에서는 발생하지 않았지만, 시간복잡도가 꽤나 크기 때문에 조심해서 사용해야한다.)
• 방문하지 않은 노드이면서, 지금 쳐다보고있는 노드와 연결되어있는 노드라면 탐색 대상이기 때문에 queue에 넣어준다.
• 그리고 방문체크를 다시 해주고,,, 반복한다.

 

💻 전체코드

https://github.com/deslog/Algorithm/blob/main/Algorithm/Boj/1260_DFS%EC%99%80%20BFS/main.swift

GitHub - deslog/Algorithm

var nmv = readLine()!.split(separator: " ").map { Int(String($0))! }
let n = nmv[0]
let m = nmv[1]
let v = nmv[2]

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

for i in 0..<m {
    let nums = readLine()!.split(separator: " ").map{ Int(String($0))! }
    matrix[nums[0]][nums[1]] = 1
    matrix[nums[1]][nums[0]] = 1
}

func dfs(_ v: Int) {
    visited[v] = true
    print(v, terminator: " ")
    for i in 1..<n+1 {
        if visited[i] == false && matrix[v][i] == 1 {
            dfs(i)
        }
    }
}


func bfs(_ v: Int) {
    var queue: [Int] = []
    visited[v] = false // dfs 돌아가면서 true 로 바뀐거 false 로 돌리면서 go
    queue.append(v)
    
    while !queue.isEmpty {
        var newV = queue.removeFirst()
        print(newV, terminator: " ")
        
        for i in 1..<n+1 {
            if visited[i] == true && matrix[newV][i] == 1 {
                queue.append(i)
                visited[i] = false
            }
        }
        
    }
    
}

dfs(v)
print("")
bfs(v)