문제 링크 (opens new window)

문제 설명

그래프 내에 A->B->C->D->E로 이어지는 서브 그래프가 존재하는지 파악하는 문제이다.

접근 과정

1. DFS로 순회할 때에 함수 호출 depth를 파라미터로 추가하여 현재 depth가 4 이상인 경우 리턴하도록 구현
2. 백트래킹, 원복 필요

풀이

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

위의 예시의 정답은 1인데 백트래킹 없이 단순 DFS로만 풀이하는 경우 0이 결과로 출력된다.

그 이유는 0->1->3->2로 DFS가 진행되었을 때 뎁스가 3이지만, 0->1->4->3->2로 진행되었을 때는 뎁스가 4이기 때문이다. 단순 DFS시 0->1->3->2에서 visited가 각 인덱스에 대해 true 체크가 되어버리기 때문에 원복 및 백트래킹이 필요한 것이다.

문제풀이

import Foundation

let NM = readLine()!.split(separator: " ").map { Int($0)! }; let N = NM[0]; let M = NM[1]
var adj: [[Int]] = .init(repeating: [], count: N)
var visited: [Bool] = .init(repeating: false, count: N)
var flag = false

// DFS 연결된 컴포넌트 수가 4 이상인지
for _ in 0..<M {
    let edge = readLine()!.split(separator: " ").map { Int($0)! }
    adj[edge[0]].append(edge[1])
    adj[edge[1]].append(edge[0])
}

func dfs(_ here: Int, _ depth: Int) {
    visited[here] = true

    for there in adj[here] {
        if visited[there] { continue }

        if depth + 1 >= 4 {
            flag = true
            return
        }

        dfs(there, depth + 1)
        visited[there] = false
    }
}

for i in 0..<N {
    if flag { break }
    visited = .init(repeating: false, count: N)
    dfs(i, 0)
}

print(flag ? 1 : 0)