[Swift] 백준 13023 - ABCDE

문제 바로가기

문제에서 말하는 친구관계가 살짝 이해가 안됐는데
그림으로 그려보니 흔히 말하는 한 붓그리기였다.
문제의 관계에서는 A->B->C->D->E가 성립해야하므로,
한 붓그리기의 깊이가 4가 가능하면 1을 출력하고, 아니면 0을 출력하면 된다!

계속 자식노드를 타고 따라가는 깊이우선탐색 dfs 문제이다.

- func dfs()

현재 위치(now)와 깊이(level)을 매개변수로 가지는
재귀함수 dfs를 구현할 것이다.
level == 4 이면, 함수를 종료하고 1을 출력한다.

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

전체 풀이 코드

import Foundation
let line = readLine()!.split(separator: " ").map { Int(String($0))!}
var friendGraph: [[Int]] = Array(repeating: [], count: line[0])

for _ in 0..<line[1] {
    let relation = readLine()!.split(separator: " ").map {Int(String($0))!}
    friendGraph[relation[0]].append(relation[1])
    friendGraph[relation[1]].append(relation[0])
}

var check: [Bool] = Array(repeating: false, count: line[0])
var isAvailable = false

func dfs(_ now: Int, _ level: Int) {
    if level == 4 {
        isAvailable = true
        return
    }
    check[now] = true
    for i in friendGraph[now] {
        if !check[i] {
            dfs(i,level+1)
        }
    }
    check[now] = false
}


for i in 0..<line[0] {
    dfs(i, 0)
    if isAvailable {
        break
    }
}

isAvailable ? print(1) : print(0)