양과늑대 - 파이썬

문제 링크 https://school.programmers.co.kr/learn/courses/30/lessons/92343

문제 설명

 

2진 트리 모양 초원의 각 노드에 늑대와 양이 한 마리씩 놓여 있습니다. 이 초원의 루트 노드에서 출발하여 각 노드를 돌아다니며 양을 모으려 합니다. 각 노드를 방문할 때 마다 해당 노드에 있던 양과 늑대가 당신을 따라오게 됩니다. 이때, 늑대는 양을 잡아먹을 기회를 노리고 있으며, 당신이 모은 양의 수보다 늑대의 수가 같거나 더 많아지면 바로 모든 양을 잡아먹어 버립니다. 당신은 중간에 양이 늑대에게 잡아먹히지 않도록 하면서 최대한 많은 수의 양을 모아서 다시 루트 노드로 돌아오려 합니다.

문제 설명 예시

예를 들어, 위 그림의 경우(루트 노드에는 항상 양이 있습니다) 0번 노드(루트 노드)에서 출발하면 양을 한마리 모을 수 있습니다. 다음으로 1번 노드로 이동하면 당신이 모은 양은 두 마리가 됩니다. 이때, 바로 4번 노드로 이동하면 늑대 한 마리가 당신을 따라오게 됩니다. 아직은 양 2마리, 늑대 1마리로 양이 잡아먹히지 않지만, 이후에 갈 수 있는 아직 방문하지 않은 모든 노드(2, 3, 6, 8번)에는 늑대가 있습니다. 이어서 늑대가 있는 노드로 이동한다면(예를 들어 바로 6번 노드로 이동한다면) 양 2마리, 늑대 2마리가 되어 양이 모두 잡아먹힙니다. 여기서는 0번, 1번 노드를 방문하여 양을 2마리 모은 후, 8번 노드로 이동한 후(양 2마리 늑대 1마리) 이어서 7번, 9번 노드를 방문하면 양 4마리 늑대 1마리가 됩니다. 이제 4번, 6번 노드로 이동하면 양 4마리, 늑대 3마리가 되며, 이제 5번 노드로 이동할 수 있게 됩니다. 따라서 양을 최대 5마리 모을 수 있습니다.

각 노드에 있는 양 또는 늑대에 대한 정보가 담긴 배열 info, 2진 트리의 각 노드들의 연결 관계를 담은 2차원 배열 edges가 매개변수로 주어질 때, 문제에 제시된 조건에 따라 각 노드를 방문하면서 모을 수 있는 양은 최대 몇 마리인지 return 하도록 solution 함수를 완성해주세요.

---

제한사항

• 2 ≤ info의 길이 ≤ 17
  • info의 원소는 0 또는 1 입니다.
  • info[i]는 i번 노드에 있는 양 또는 늑대를 나타냅니다.
  • 0은 양, 1은 늑대를 의미합니다.
  • info[0]의 값은 항상 0입니다. 즉, 0번 노드(루트 노드)에는 항상 양이 있습니다.
• edges의 세로(행) 길이 = info의 길이 - 1
  • edges의 가로(열) 길이 = 2
  • edges의 각 행은 [부모 노드 번호, 자식 노드 번호] 형태로, 서로 연결된 두 노드를 나타냅니다.
  • 동일한 간선에 대한 정보가 중복해서 주어지지 않습니다.
  • 항상 하나의 이진 트리 형태로 입력이 주어지며, 잘못된 데이터가 주어지는 경우는 없습니다.
  • 0번 노드는 항상 루트 노드입니다.

 

문제 해결 아이디어 

• 사실 이 문제를 풀었을때는 트리로 해결을 해야하나 라는 생각에 방향을 잘못잡고 풀었던 문제입니다.
• 완전탐색+(DFS,BFS)로 문제를 답을 보고 해결을 하였습니다. 
• 해당 문제를 확인하였을때 바로 그래품 탐색이라는것을 알아차리고 어떻게 DFS 돌릴지 고민을 해봐야 합니다. 
• 문제의 핵심은 역류를 하면 안되고 단방향으로 탐색하면서 문제를 풀어가야한다는것입니다. 
• 상식적으로 생각로 생각을 해보면 테스트가 끝날때 까지 어딜가든 양과 늑대는 동일하게 쫓아오기 떄문입니다
• 따로 역류를 해서 초기화하는게 이미 방문한 노드에서는 의미가 크게 없는것입니다 

 

테스트 케이스로 예시 

• 0번 정점과 1,8번 정점은 자식으로 두고 있습니다.즉 이건 1,8번 노드를 방문할때는 0번 노드는 이미 방문한 노드가 됩니다.
• 부모 노드로부터 방문이 되었습니다. 자식 노드들은 언제든지 입장이 가능합니다. 
• 8번 노드를 방문한다면 8번 노드가 방문할수있는 노드는 [1,7,9] 번 노드입니다. 이러한 방법으로 역류를 안하고 단방향으로 방문을 할수있습니다. 8번 노드는 현재 방문 노드여서 제외 
• dfs(현재 정점,양의개수,늑대의개수,이동가능한정점) 으로 함수를 진행 

 

정답 코드 

from collections import defaultdict
answer = -1

def solution(info, edges):
    graph = defaultdict(list)
    # 그래프 세팅 [[1,8],[].......]
    for u, v in edges:
        graph[u].append(v)

    def dfs(cur, sheep, wolf, next_set):
    	# xor 연산 (사실 1이기 때문에 if가 없다) 따로 나중에 써먹어야겠다
        sheep += info[cur] ^ 1
        wolf += info[cur] 
		# 늑대가 양보다 많거나 같을경우 종료 
        if sheep <= wolf:
            return
        # 양이 더 많다면 
        if sheep > wolf:
            global answer
            # 양의 최대값을 answer 에 저장 
            answer = max(answer, sheep)
            # 이동가능한 정점 노드를 순회
            for next_ in next_set:
            	temp = set(graph.get(next_, []))
                next_set |= temp
                next_set -= set([next_])
                dfs(next_, sheep, wolf, next_set)
                next_set |= set([next_])
                next_set -= temp

    dfs(0, 0, 0, set(graph.get(0)))
    print(answer)
    return answer