목록2022/10/01 (1)

코딩관계론

[프로그래머스] 양과 늑대 풀이(python)

풀이 "당신은 중간에 양이 늑대에게 잡아먹히지 않도록 하면서..." 가장 중요한 점은 방문 순서가 상관이 없다는 점이다. 왜냐하면 방문한 노드의 양과 늑대를 다 더하고 늑대가 많다면 탐색을 잔행 하지 못하기 때문이다. 다시 루트 노드로 돌아오려 합니다." 노드의 재방문을 고민해보면 양방향 간선을 통해서 해결할 수 있다. 이 부분 때문에 2차원 배열의 메모제이션이 필요하다. dp는 cache[node][방문한 노드들] = 양의 최대 수 코드 from collections import defaultdict nodes = [] edges = [] cache = [] def dfs(node, visited): global nodes, edges sheep = 0 wolf = 0 if cache[node][vis..
개발/알고리즘 2022. 10. 1. 15:28
이전 Prev 1 Next 다음