[코딩테스트] 🐑 양과 늑대 - Kakao 2022

문제링크

난이도

레벨 3

유형

DFS, 백트래킹

소요시간

2시간, 초과

회고

엣지 케이스

테스트케이스 3번이 시간 초과로 실패해서 질문 게시판 찾아보니, 질문 게시판에 모든 노드가 양인 경우 따로 처리가 필요하다고 하여 처리함

처음엔 BFS로 풀고 graph destination을 subQueue에 넣어서 처리하고, [head, head -1]과[head-2, head-3]이 같으면 순회하는 경로니 가지치기식으로 푸려고 했는데 실패하였다.

BFS문제만 풀다보니 생각이 갇힌 것 같다. DFS 문제도 풀어야겠다.

코드

func solution(_ info:[Int], _ edges:[[Int]]) -> Int {

    var answer = 0

    var graph = Array(repeating: Array<Int>(), count: info.count)

    edges.enumerated().forEach { i, values in
        let (from, to) = (values[0], values[1])
        graph[from].append(to)
    }

    if info.reduce(0, +) == info.count { return info.count }

    func dfs(_ wolves: Int, _ sheep: Int, _ candidate: [Int]) {
        answer = max(sheep, answer)

        candidate.enumerated().forEach { i, c in
            var ns = sheep
            var nw = wolves
            if info[c] == 0 {
                ns += 1
            } else {
                nw += 1
            }

            if nw >= ns {
                return
            }

            var next = candidate
            next.remove(at: i)
            next = next + graph[c]

            dfs(nw, ns, next)
        }
    }

    dfs(0, 1, graph[0])

    return answer
}