[Swift][DFS] 백준 13023번 (ABCDE)

요구능력 : DFS와 인접리스트에 대한 이해

 

코드설명 : 

 

문제를 읽고 예제를 보면 연속적으로 친구와의 관계가 4번 연결되면 정답이된다.

인접리스트를 구하고 인접리스트를 하나씩 DFS하면 된다.

 

인접리스트와 DFS를 알아야한다.

예제로 인접리스트를 만들어보자.

예제 2번)

5 5

0 1

1 2

2 3

3 0

1 4

 

인접리스트

0 -> 1, 3

1 -> 0, 2, 4

2 -> 3, 1

3-> 0, 2

4-> 1

 

인접리스트를 DFS의 노드방식으로 그리고 깊이우선탐색하면 이해가 갈것이다.

DFS를 사용하는 이유는 친구와의 관계(depth)를 세기위함이다.

 

후기 : 처음에 DFS로 4개연속하면 1출력 아니면 0출력이겠다... 까지는 생각했는데,

문제에 대해 이해를 제대로 못했을 때는 인접리스트 수를 세면 되는게 아닌가 했는데, 관계의 깊이를 세는문제라 DFS를 쓰는거였다..

인접리스트에대한 개념을 모르고있었고 DFS도 조금 모자랐던거 같다.

let arr = readLine()!.split(separator: " ").map{Int(String($0))!}
let n = arr[0]
let m = arr[1]
var depth = 0
var available = false
var visited = Array(repeating: false, count: n)
var friendGraph: [[Int]] = Array(repeating: [], count: n)
for _ in 0..<m {
    let friend = readLine()!.split(separator: " ").map{Int(String($0))!}
    friendGraph[friend[0]].append(friend[1])
    friendGraph[friend[1]].append(friend[0])
}

func dfs(_ now: Int,_ depth: Int ) {
    if depth == 4 {
        available = true
        return
    }
    visited[now] = true
    for i in 0..<friendGraph[now].count {
        let next = friendGraph[now][i]
        if !visited[next] {
            dfs(next,depth + 1)
        }
    }
    visited[now] = false
}

for i in 0..<n {
    dfs(i, depth)
    if available {
        break
    }
}

if available {
    print("1")
}else {
    print("0")
}