[프로그래머스] LV.3 <카카오> 양과 늑대 - python

문제

https://programmers.co.kr/learn/courses/30/lessons/92343

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

 

풀이방법

https://tooo1.tistory.com/579

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

< 아이디어 >

- 경로를 추가해가며 max(maxsheep, dfs())를 계속 비교해간다. == 현재 경로까지의 양의 갯수와 다음 경로까지의 양의갯수를 비교하면서 양<= 늑대가 아닌 경우 경로를 계속 추가해가며 maxsheep을 구한다.

** 꼭 한

 

 

< 배운점 >

- 백트래킹시 재귀함수에 대한 이해도가 올라갔다.

- 여전히 헷갈리고 어렵지만 중심 가닥은 잡을 수 있었다.

 

< 연습 >

def solution(info, edges):
  def nextNodes(v):
    temp = list()
    for i,j in edges:
      if i == v:
        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))
          -------------------------
          [dfs(1, 0, 1, [0,1]) == 0] X
          [max ( maxsheep,dfs(1, 0, 2, [0,2])
          maxsheep = 2
          for ([0,2])
            0 -> 1,2
            [0,2,1]
            max(maxsheep,dfs(1,[0,2,1]))
              [
                max(maxsheep,dfs(3,[0,2,1,3]))
                                    -> maxsheep = 3
                   [max(maxsheep,dfs(4,[0,2,1,3,4]))
                         [max(maxsheep,dfs(5,[0,2,1,3,4,5]) == 0) == 3 X
                          [max(maxsheep,dfs(6,[0,2,1,3,4,6])
                                                 -> maxsheep = 4
                               max(maxsheep,dfs(7,[0,2,1,3,4,6,7])
                                                 -> maxsheep = 5
                                                 -> pop! [0,2,1,3,4,6]
                                                 -> return 5
                               ]
                                           
                                                          
                   ]                 
              ]
          ]
          --------------------------
          path.pop()
    return maxSheep
          
  answer = dfs(0, 0, 0, [0])
  
  return answer