[Swift] 2022 KAKAO BLIND RECRUITMENT 양과 늑대

Problem

 

코딩테스트 연습 - 양과 늑대

---

Solution

해당 문제는 완전탐색과 DFS로 풀어야 하는 문제입니다.

1. edge를 이용해 부모와 자식을 연결해줍니다.

 

func connectEdge(_ edges:[[Int]]) {
	for edge in edges {
    	if pc[edge[0]] == nil {
        	pc[edge[0]] = [edge[1]] 
        }else {
        	pc[edge[0]]!.append(edge[1]) 
        } 
    } 
}

 

2. 늑대와 양의 수를 업데이트 하며 DFS로 방문 가능한 노드들을 재귀해줍니다.

여기서 방문 가능한 노드들은 각 방문한 노드들의 자식들을 추가해준 것입니다.

주의할 점은 이미 방문한 노드는 반드시 삭제해 주어야 무한 루프를 피할 수 있습니다.

매번 양의 최대 수를 업데이트 해줍니다.

양의 수가 늑대의 수 보다 큰 경우에만 dfs로 탐색해줍니다.

 

 maxCount = max(count.0,maxCount) 
 
 for node in visitableNodes {
    var newVisitableNodes = visitableNodes 
    var newCount = count 
    let index = newVisitableNodes.firstIndex(of:node)! 
    newVisitableNodes.remove(at: index) 
    newVisitableNodes.append(contentsOf:pc[node] ?? []) 
    newCount = info[node] == 0 ? (count.0+1,count.1) : (count.0,count.1+1) 
    
    if newCount.0 > newCount.1 {
    	dfs(newCount, newVisitableNodes, info) 
    } 
}

 

3. 가장 큰 양의 수를 반환해줍니다.

 

func solution(_ info:[Int], _ edges:[[Int]]) -> Int {
	connectEdge(edges) dfs((1, 0), pc[0]!, info) 
    return maxCount 
}

---

Source Code