[백준 1260] DFS와 BFS (Swift)

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

 

DFS & BFS

4 5 1
1 2
1 3
1 4
2 4
3 4

 

노드수, 간선수, 처음 방문해야하는 노드 번호

간선이 잇고 있는 두 노드 (양방향) 리스트가 좍 주어지고

DFS로 방문하는 순서

BFS로 방문하는 순서 를 출력하는 문제

 

접근방법

DFS는 재귀함수를 정의해서, 방문 여부를 확인해가면서 인접 행렬을 통해 현재 노드와 연결되어 있지만, 아직 방문하지 않은 노드들을 차례로 순회하면서 풀이했고,

BFS는 큐와 방문여부를 저장하는 배열을 사용해서, V부터 큐에 넣고, V에 연결되어 있는 노드 중 아직 방문하지 않은 노드를 큐에 넣고,

큐에서 노드를 하나씩 빼면서 순서를 매기는 식으로 큐가 다 빌때까지 진행했다.

 

오답노트

DFS에서 스위프트가 배열을 값 타입으로 참조하는 특징 때문에, inout을 사용하지 않고 풀이하다가 인접한 노드를 순회하며 DFS를 호출하는 과정에서, visit 배열을 수정하면, 같은 자식들 까지는 방문여부 수정한게 전달되지만, 자식의 자식까지 체크하는 DFS 로직상 자식의 자식을 방문하는 것 부터는 반영이 안되어서 이미 방문 했음에도 해당 노드에 대해 dfs함수를 호출하는 문제가 발생했었다.

DFS에서 방문 여부를 저장하는 배열은 참조타입으로 전달해야함을 명심하기

 

소스코드

import Foundation

func solution() -> [[Int]] {
    
    let input = readLine()!.split(separator: " ").map { Int($0)! }
    let N = input[0]
    let M = input[1]
    let V = input[2]
    
    var adj: [[Int]] = Array<Array<Int>>(repeating: [], count: N+1)
    
    for _ in 0..<M {
        let line = readLine()!.split(separator: " ").map { Int($0)! }
        let A = line[0]
        let B = line[1]
        adj[A] += [B]
        adj[B] += [A]
    }
    
    // preprocess
    for i in 1...N {
        adj[i].sort()
    }
        
    //process : DFS
    var result:[[Int]] = []
    var seq:[Int] = []

    func dfs(_ i:Int, _ visit: inout [Bool]) {
        visit[i] = true
        seq.append(i)

        for node in adj[i] {
            if !visit[node] {
                dfs(node, &visit)
            }
        }
    }
    
    var visit = Array<Bool>(repeating: false, count: N+1)
    dfs(V, &visit)
    result.append(seq)

    // process : BFS
    visit = Array<Bool>(repeating: false, count: N+1) //temp
    var q:[Int] = [V]
    visit[V] = true
    seq = []
    
    while !q.isEmpty {
        let now = q[0]
        q.removeFirst()
        seq += [now]
        for node in adj[now] {
            if !visit[node] {
                visit[node] = true
                q.append(node)
            }
        }
    }
    
    result.append(seq)
        
    return result
}

let sol:[[Int]] = solution()

for s in sol {
    print(s.map { String($0) }.joined(separator: " "))
}