[python] 프로그래머스 - 양과 늑대

파이썬 [프로그래머스] - 양과 늑대

문제 설명

"양과 늑대" 문제는 트리 형태로 구성된 노드에서 양과 늑대가 존재하는 상황에서, 루트 노드부터 시작해 이동하면서
최대한 많은 양을 구하는 문제입니다. 각 노드는 0(양)과 1(늑대)로 표시되며, 이동 중 언제나 양의 수가 늑대의 수보다 많아야 합니다.
문제의 목표는 가능한 경로들 중, 조건을 만족하면서 최대한 많은 양을 모으는 경우의 양의 수를 구하는 것입니다.

---

문제 접근 방식

1. DFS(깊이 우선 탐색) 활용
   • 노드들을 깊이 우선 탐색하면서 현재까지 모은 양(sheeps)과 늑대(wolves)의 수를 관리합니다.
2. 방문 배열 사용
   • 각 노드의 방문 여부를 추적하여 중복 방문을 방지하고, 다른 경로 탐색을 위해 방문 상태를 초기화합니다.
3. 조건 검사
   • DFS 내에서 매번 sheeps > wolves 조건을 확인하여, 조건을 만족할 때만 경로를 확장합니다.
4. 간선 탐색
   • 이미 방문한 부모 노드와 연결된 아직 방문하지 않은 자식 노드를 대상으로 DFS를 수행합니다.
5. 결과 저장 및 반환
   • 탐색 과정 중 가능한 모든 경로의 양의 수를 기록한 후, 그 중 최댓값을 반환합니다.

---

문제 풀이

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

    def dfs(sheeps, wolves):
        # 현재까지 모은 양이 늑대보다 많으면 경로 유지, 그렇지 않으면 탐색 중단
        if sheeps > wolves:
            answer.append(sheeps)
        else:
            return

        # 모든 간선을 순회하며 이동 가능한 경로 탐색
        for p, c in edges:
            # 부모 노드 p는 방문했으나, 자식 노드 c는 아직 방문하지 않은 경우에만 진행
            if visited[p] and not visited[c]:
                visited[c] = True
                if info[c] == 0:  # 양인 경우
                    dfs(sheeps + 1, wolves)
                else:           # 늑대인 경우
                    dfs(sheeps, wolves + 1)
                # 다른 경로 탐색을 위해 방문 상태 초기화
                visited[c] = False

    # 루트 노드(0번)는 시작점이므로 방문 처리
    visited[0] = True
    dfs(1, 0)

    return max(answer)

구현 시 주의사항 및 팁

• 방문 배열 관리:
  DFS 탐색 중에 노드를 방문한 후, 다른 경로를 탐색할 수 있도록 재귀 호출이 끝난 후 방문 상태를 False로 되돌리는 것이 중요합니다.
• 조건 검사:
  각 DFS 호출에서 현재까지 모은 양이 늑대보다 많아야만 탐색을 이어갑니다.
  조건을 만족하지 못하면 더 이상 진행하지 않고 탐색을 종료합니다.
• 간선 탐색:
  모든 간선을 순회하여, 부모 노드가 방문된 상태에서 자식 노드가 아직 방문되지 않은 경우에만 DFS를 진행합니다.
• 결과 저장:
  각 경로마다 모을 수 있는 양의 수를 answer 리스트에 기록하고, 최종적으로 이 중 최댓값을 반환합니다.