[프로그래머스] 코딩테스트 연습 : 양과 늑대 - PYTHON[파이썬]

https://programmers.co.kr/learn/courses/30/lessons/92343?language=python3 

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

 

---

⊙ 문제

⊙ 제한사항

⊙ 입출력 예

⊙ 입출력 예 설명

z

 

---

 

⊙ 문제 접근 과정

 

백트래킹으로 풀자!

계속해서 양의 수와 늑대의 수를 비교!

같아지는 순간 return.

 

아니라면 다음 노드를 체킹 하면서 양 최댓값 갱신.

 

---

 

⊙ 문제 풀이

 

def solution(info, edges):
    def nextNodes(v):
        temp = list()
        for e in edges:
            # i는 부모노드, j는 자식노드
            i, j = e
            # 부모노드 번호 비교
            if v == i:
                temp.append(j)
        return temp

    def dfs(sheep, wolf, current, path):
        # 지금 노드 확인, 양 늑대 판별
        if info[current]:
            wolf += 1
        else:
            sheep += 1

        # 늑대가 다 잡아먹음, 무시
        if sheep <= wolf:
            return 0

        # 아니라면 임시 변수에 값 갱신
        maxSheep = sheep

        # 서칭 시작
        for p in path:
            for n in nextNodes(p):
                if n not in path:
                    path.append(n)
                    # 최대 양 판별
                    maxSheep = max(maxSheep, dfs(sheep, wolf, n, path))
                    path.pop()
        return maxSheep

    answer = dfs(0, 0, 0, [0])

    return answer

---

⊙ 마무리

 

 

NONE

 

 

좋아요는 로그인하지 않아도 누를 수 있습니다!