프로그래머스 - 양과 늑대

🔗 프로그래머스 - 양과 늑대 

(카카오)

📌오늘의 학습 키워드

• 백트래킹

✨공부한 내용 본인의 언어로 정리하기

• 백트래킹에서 어떤 조건을 이용해 종료시킬 것인가가 핵심이었다.
• 너무 복잡하게 알고리즘을 구성하다가 파라미터값이 4개에 이르게 되었고, 결국 구글링을 했다...ㅎ
  • 종료조건으로 양과 늑대의 갯수가 아니라 트리의 끝까지 갔는지로 판단하려고 했는데
  • 트리에서 아래 뿐만 아니라 위로도 갈 수 있다 보니까 좋은 종료조건이 아니었다. (위 아래 위 아래 이런 반복이 생기면서 재귀가 끝나지 않았음)

[종료조건] 늑대에게 양이 다 잡아먹히면 끝난다.

- 그렇지 않으면 answer에 현재 양의 갯수를 저장해서 마지막에 최대값을 정답으로 반환한다.

 

[재귀조건] 간선을 기준으로 진행한다. 만약 부모노드를 방문했고, 자식노드를 방문하지 않았으면 탐색 조건을 만족한다.

- 탐색 이후에 방문했다는 표시를 제거하여 다시 방문 가능 하도록 한다. 

 

🤔 visited 를 전체 과정에서 절대 다시 방문하지 않도록 썼던 이전과 달리 한 재귀 과정에서 어디까지 방문했었는 지 나타내는 용도로 사용되었다. 

 

📚오늘의 회고

• 단순히 트리를 전체 탐색하는 것이 아니라 왔던 길을 다시 갈 수 있다는 조건이 생기니까 어려워졌다...

[🤓문제 해결 코드]

def solution(info, edges):
    visited = [0] * len(info)
    answer = []

    def dfs(sheep, wolf):
        if sheep > wolf:
            answer.append(sheep)
        # 다 잡아먹히면 끝남
        else:
            return

        for p, c in edges:
            if visited[p] and not visited[c]:
                visited[c] = 1
                if info[c] == 0:
                    dfs(sheep + 1, wolf)
                else:
                    dfs(sheep, wolf + 1)
                visited[c] = 0

                
    visited[0] = 1
    dfs(1, 0)
    return max(answer)