2022 KAKAO BLIND RECRUITMENT 양과 늑대 Lv. 3

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

파이썬 소스: https://bit.ly/3JzINcU

 

주어진 양과 늑대에 관한 조건에 따라서, 트리를 탐색하는 문제입니다. 이진 트리 모양이라고 주어졌기 때문에 트리를 탐색할 때, 방문한 노드인지 확인하는 과정이 필요 없으며, 싸이클도 없습니다.

이진 트리를 만들어야 하기 때문에, Node 클래스를 코딩해 보겠습니다.

class Node:     def __init__(self, idx: int, n: int):         self.idx = idx         self.sheep_or_wolf = n         self.children: List[Node] = []

idx 는 노드의 인덱스 값

sheep_or_wolf: 0이면 양, 1이면 늑대

children은 리스트로, 자식 노드를 가리킵니다.

함수 solution의 인자로 주어지는, 리스트 info 값으로, 우선 노드부터 만들 수 있습니다.

nodes: List[Node] = [Node(idx, info[idx]) for idx in range(len(info))]

각 노드의 부모 자식 관계를 맺어 줍니다.

for idx_parent, idx_child in edges:     nodes[idx_parent].children.append(nodes[idx_child])

부모노드의 children에 자식노드를 추가해 줍니다.

문제에서 주어진 이진 트리 모양을 잘 보면, 왼쪽 자식 노드가 인덱스 값이 작습니다. 하지만, edges에 들어 있는 [부모, 자식] 관계는 이를 고려하지 않고 있습니다.

for node in nodes:     node.children.sort(key = lambda n: n.idx)

인덱스 값이 작은 자식노드가 왼쪽에 오도록, sort()를 idx기준으로 해줍니다.

이제 DFS방식으로 트리를 탐색할 dfs()함수를 호출하겠습니다.

answer = dfs(nodes[0].children, 1, 0) return answer

루트노드는 항상 양이기 때문에, 양 1마리, 늑대 0마리입니다. 방문 가능한 노드는 루트노드의 2개의 자식 노드입니다.

입출력 예 #1을 예를 들어 설명하면, 루트노드 0번을 하고, 노드 1, 8번을 방문할 수 있습니다.

먼저 1번을 방문했다고 가정하면, 다음번에 방문가능한 노드는 2, 4, 8번이 됩니다.

다음에 2번을 방문했다고 하면, 방문 가능한 노드는 4, 8 번이 되구요.

4번을 방문했다면, 방문 가능한 노드는 2, 3, 6, 8번이 됩니다.

문제에서는 양의 수가 늑대의 숫자보다 큰 상태로 트리를 탐색하기 때문에 방문 순서가 매우 중요합니다.

0, 1 번을 방문하여 양이 2마리인 상태로 8번을 방문할 수 있습니다.

0, 1 2번을 방문하여, 양이 2마리, 늑대 1마리인 상태면 8번을 방문할 수 없습니다.

이처럼 양과 늑대의 숫자를 고려하여 dfs() 함수를 코딩해야 합니다.

def dfs(reachable: List[Node], cnt_sheep, cnt_wolf):     max_sheep = cnt_sheep     if cnt_sheep <= cnt_wolf:         return -1

리스트 reachable은 방문가능한 노드의 리스트입니다.

cnt_sheep, cnt_wolf는 각각 양과 늑대의 숫자입니다.

양과 늑대의 수자가 서로 같거나, 양의 숫자가 작으면, return -1을 해서 이후에 추가적으로 노드를 방문하지 않도록 코딩합니다.

for idx in range(len(reachable)):     copy_reachable = copy.deepcopy(reachable)     node = copy_reachable.pop(idx)

현재 방문할 수 있는 노드 리스트 reachable에의 순서대로 방문해 보겠습니다.

리스트 reachable를 복사를 하고, 선택된의 노드를 복사된 copy_reachable에서 꺼냅니다.

if node.sheep_or_wolf:     max_sheep = max(max_sheep, dfs(copy_reachable + node.children, cnt_sheep, cnt_wolf + 1))

꺼낸 노드가 늑대노드이면 cnt_wolf에 +1을 해줍니다.

리스트 copy_reachable에는 선택한 node에서 방문할 수 있는 노드도 추가해줍니다.

else:     max_sheep = max(max_sheep, dfs(copy_reachable + node.children, cnt_sheep + 1, cnt_wolf))

꺼낸 노드가 양 노드이면, cnt_sheep에 +1을 해주고, 마찬가지로, 리스트 copy_reachable에는 선택한 node에서 방문할 수 있는 노드도 추가해줍니다.

함수 max()를 사용해서 양을 최대한 많이 방문한 횟수를 max_sheep에 저장하고, 마지막에 리턴해주면, 이 문제의 답을 구할 수 있습니다.

 

궁금한 문제, 내용은 댓글, 이메일(coding.data.pul@gmail.com)로 보내주세요.

코데풀 유튜브 구독 부탁드립니다.

https://www.youtube.com/@codapul

 

전체 코드는 아래에 있습니다.

import copy from typing import List class Node:     def __init__(self, idx: int, n: int):         self.idx = idx         self.sheep_or_wolf = n         self.children: List[Node] = [] def solution(info: List[int], edges: List[List[int]]):     nodes: List[Node] = [Node(idx, info[idx]) for idx in range(len(info))]     for idx_parent, idx_child in edges:         nodes[idx_parent].children.append(nodes[idx_child])     for node in nodes:         node.children.sort(key = lambda n: n.idx)     answer = dfs(nodes[0].children, 1, 0)     return answer def dfs(reachable: List[Node], cnt_sheep, cnt_wolf):     max_sheep = cnt_sheep     if cnt_sheep <= cnt_wolf:         return -1     for idx in range(len(reachable)):         copy_reachable = copy.deepcopy(reachable)         node = copy_reachable.pop(idx)         if node.sheep_or_wolf:             max_sheep = max(max_sheep, dfs(copy_reachable + node.children, cnt_sheep, cnt_wolf + 1))         else:             max_sheep = max(max_sheep, dfs(copy_reachable + node.children, cnt_sheep + 1, cnt_wolf))     return max_sheep