[Swift][백트래킹][LV_3] 양과 늑대

요구능력 : 2진트리, 백트래킹

 

코드설명 : 

 

처음에 배열로 edges를 연결리스트식으로 만들어서 방문했던곳을 다시 들리는(위로다시올라오는) 대참사가 발생했다.

dictionary로 아래와 같이 넣으면 한방향(본인 위치의 아래방향)으로 방문하기 편하므로 dictionary를 사용했다.

 

백트래킹이라고 생각한이유는 모든경우를 다 세어봐야 하기 때문이다.

 

dfs(현재노드, 다음에 방문할 수 있는 노드, 양의 카운트, 늑대의 카운트)로 구성했다.

이렇게 구성한 이유는 양과 늑대의 카운트같은 경우 dfs()함수가 리턴되면 따로 -처리를 해주지 않아도 되기 때문이고(전역으로 선언 시 따로 -처리를 해줘야함), 현재노드 같은 경우에는 시작노드로 0을 전달해줘야 하는것도있고 굳이 0을 전달 안해주고 0으로 시작하더라도 다음번 dfs()에서 현재 방문하는 노드를 알아야하기 때문이다. 그리고 다음에 방문할 수 있는 노드는 dfs()가 쌓일수록 계속해서 추가되기 때문에 넣어줬다.

 

0번노드에서 탐색을 시작한다.

그럼 처음에 node는 0, 탐색할 수 있는 노드는 [0], 양의 카운트 0, 늑대카운트 0 이다.

탐색할 수 있는 노드가 dict[0]!이 아니고 [0]인 이유는 dfs()내에서 아래와 같이 처리를 해주기 때문이다.

newNextNodes.append(contentsOf: dict[node] ?? [])

안에서 처리를 해주기 때문에 처음에 인수로 넣어줄 필요가 없다.

그리고 주의할 점은 2진트리가 끊기는 부분이면 자식노드가 없기때문에 자식노드가 없으면 빈 배열을 추가해줘야한다.

 

현재노드가 양인지 늑대인지 구분해서 카운팅

if info[node] == 0 {sheepCnt += 1}
        else {wolfCnt += 1}

 

양이 늑대에게 잡아먹히는 순간 우리는 현재 진행중인 이진트리의 경우를 더 이상 볼 필요가 없다.

그래서 더 이상 아래를 가지 않고 return해서 [1, 2, 3]중에 1을 보고있었다면 return하면 다시 dfs()가 있는 for문으로 돌아가서 2를 보게된다. 이렇게 늑대에게 잡아먹히지 않을 때 구할 수 있는 양의 최대값을 구하기 위해 모든 경우의 수를 보는 백트래킹의 핵심부분이다.

 if wolfCnt >= sheepCnt{return}

 

현재방문하고있는 노드를 방문할 수 있는 노드(nextNodes)에서 지워준다.

이진트리를 많이 안풀어봐서 처음에는 왜 지워줘야하는가 싶었는데,

예제 1번을 보면 0 -> 1 -> 8 이런식으로도 갈 수가 있다.

그래서 한번 방문한 곳은 다시 방문할 필요가 없다.

if let idx = newNextNodes.firstIndex(of: node){
            newNextNodes.remove(at: idx)
        }

 

 

후기 : 난이도가 꽤나 있는것 같지만 이진트리를 풀어봤으면 단순하게 넘어갈 만한 문제인것같다.

func solution(_ info:[Int], _ edges:[[Int]]) -> Int {
    
    var dict = [Int : [Int]]()
    for i in edges{
        if dict[i[0]] == nil{
            dict[i[0]] = [i[1]]
        }else{
            dict[i[0]]?.append(i[1])
        }
        
    }
    var result = 0
    func dfs(_ node: Int, _ nextNodes: [Int], _ sheep: Int, _ wolf: Int){
        var newNextNodes = nextNodes
        var sheepCnt = sheep
        var wolfCnt = wolf
        if info[node] == 0 {sheepCnt += 1}
        else {wolfCnt += 1}
        if wolfCnt >= sheepCnt{return} //방문 할 수 있는 노드에서 현재노드를 지우지는 않고 리턴되게됨. 그래서 다음번에 리턴된 현재노드를 또 들리게되서 백트래킹이 완성.
        result = max(result, sheepCnt)
        
        newNextNodes.append(contentsOf: dict[node] ?? [])
        if let idx = newNextNodes.firstIndex(of: node){
            newNextNodes.remove(at: idx)
        }
        for i in newNextNodes{
            dfs(i, newNextNodes, sheepCnt, wolfCnt)
        }
    }
    dfs(0, [0], 0, 0)
    
    
    return result
}