★★양과 늑대★★

★다시 풀어봐야할 문제★ (혼자 힘으로 못풀었음)

접근 방법 [필수 작성]

제한 조건 확인

• 양의 수보다 늑대의 수가 같거나 더 많아지면 바로 모든 양을 잡아먹어 버립니다.
• 이진트리

• 노드는 최대 17개
• 엣지는 최대 16개

아이디어

시간제한 넉넉한데 완전탐색을 고려해볼 순 없을까?

→ 근데 무조건 깊이 들어가는게 아니고, 판단하에 빠져나와야하기 때문에 완전탐색을 구현하는것도 쉽지 않음

그럼 어떻게 빠져나올지 말지에 대한 근거를 찾지?

이진트리의 특성을 활용하는 문제일 것 같음

이진트리의 특성? → 자식의 수는 최대 2개

깊이의 개념으로 접근할 수는 없을까?
깊이1까지 최대 양의 갯수와 최소 늑대의 갯수

뭐 이런식으로 더해나가면 되지 않을까?

만약 다음 깊이까지 최소늑대 갯수가 최대 양의 갯수보다 작으면 더 깊은 곳까지 탐색가능

그게 아니고. 최소늑대의 갯수가 최대 양의 갯수보다 같아지거나 더 커지는 순간의 직전 양의 갯수가 최대 모을 수 있는 양의 갯수가 될 것이다.

edges 를 통해 인접리스트를 만들어서 루트노드부터 순차적으로 어디를 탐색해야하는지 알 수 있음

다음 노드에서 양이 발견되면

현재 노드값 + 1 이 다음 노드 값이 되고,

내가 양인데, 부모노드보다 크면, 현재까지 연결된 모든 노드 중 내보다 depth 높은 것들 모두 +1

→ 역전파

다음 노드에서 늑대가 발견되면

다음 노드 값은 현재 노드값 - - 1 이다

이진트리가 대소관계를 가지고 있지 않아서, 이진트리의 인덱스 특징을 활용할 수 없기 때문에 단순한 그래프로 해석해야한다. 즉, 그냥 일반적인 그래프라고 생각하고 BFS 단위로 깊이가 몇인지 파악하여 연결리스트로 풀어야한다.

누적합 느낌으로 풀려고 했는데 예외케이스가 자꾸만 생겨서

도저히 아이디어가 안떠올라서 해설영상 봄

해설코드 본 후 아이디어 정리

완전탐색으로 풀어야할 것같다고 생각하긴했는데 구현이 어려웠음

구현 아이디어의 핵심은 부모노드는 방문했는데 자식노드는 방문안한 모든 경우에 대해서 백트래킹 탐색

어떻게 구분해줄 것인가?

현재까지 진행했을때 가지는 양의 최대 갯수와

특정 노드는 리프가 될 수도 있고 루트가 될 수도 있음

어떤 노드가 두개의 리프를 가질 때만 해당 노드는 리프노드리스트에서 제외될 수 있음

즉, 부모노드여도 리프가 하나밖에 없으면 해당 부모노드도 리프로 인식됨

그럼, 연결리스트에서 두개의 엣지가 모두 사용된 경우만 해당 노드를 리프노드리스트에서 제외할 수 있음. 즉, 사용안된 엣지가 하나라도 있으면 탐색해야되는 가짓수로 남아있어야함.

위 생각은 어떤 노드가 리프가 하나만 있거나 없을 수도 있기때문에 다시 최종정리하면, 내가 가진 엣지를 모두 소모했을때 리프노드가 아닌걸로 정리할 수 있다.

전달해야할 argument 는

최대 양의 갯수, 현재 양의 갯수, 현재 늑대의 갯수, 리프노드 리스트, 사용안된 엣지 리스트,

만약 현재 양의 갯수가 현재 늑대의 갯수와 같으면 return False

리프노드리스트에서 스타트한다.

리프노드리스트에서 다음 노드로 이동할 수 있는 경우 해당 이동경로의 엣지를 제거한다.

시간복잡도

제한조건을 보면 시간초과 우려는 없어보임

결국 아이디어의 문제

자료구조

코드 구현 [필수 작성]

1차 시도

코드 굉장히 지저분해서 가독성 굉장히 떨어짐..

remove 남발해서 시간초과 우려했지만, 입력값 자체가 작아서 시간초과는 안났지만, 만점을 못받는 상황.

코너케이스 생각해보면서 디버깅 해야하는 상황이나 문제 너무 어려워서 잠시 보류.

#5시 10분 시작
def solution(info, edges):
    
    max_sheep = 0
    new_edge_to = [[] for _ in range(len(info))]
    #i번째 노드에서 연결되는 한번도 사용안한 엣지가 들어있는 리스트 모음
    
    for edge in edges:
        root, leaf = edge
        new_edge_to[root].append(leaf)
        
    def can_next_step(curr_sheep, curr_wolf, leaf_node_list, new_edge_to):
        #sheep == 0, wolf == 1
        nonlocal max_sheep
        
        # print("=========function call=========")
        # print("curr_sheep=",curr_sheep)
        # print("curr_wolf=",curr_wolf)
        # print("leaf_node_list=",leaf_node_list)
        # print("new_edge_to=",new_edge_to)
        
        if len(leaf_node_list) == 0: #만약 더이상 뻗어나갈수있는 가지가 없으면 진행 안함
            print("backtrack ending . . .")
            return
        
        for leaf_node in leaf_node_list: #현재 가능한 모든 가지뻗기 경우수 탐색
            for next_node in new_edge_to[leaf_node]: #특정 가지로 뻗어나갔을때
                if info[next_node]:
                    curr_wolf += 1
                    if curr_sheep <= curr_wolf: #늑대가 같거나 더 많아지면 더 진행 안함
                        curr_wolf -= 1
                        continue
                    else:
                        new_edge_to[leaf_node].remove(next_node) #특정 가지 사용 후 제거
                        if len(new_edge_to[leaf_node]) == 0: #해당 노드 가지들 다 썼으면
                            leaf_node_list.remove(leaf_node) #리프노드리스트에서 해당 노드 제거
                        if len(new_edge_to[next_node]) != 0: #새롭게 추가된 노드가 가지가 있으면
                            leaf_node_list.append(next_node) #추가된 노드 리프노드리스트에 추가
                        can_next_step(curr_sheep, curr_wolf, leaf_node_list, new_edge_to)
                        curr_wolf -= 1
                        new_edge_to[leaf_node].append(next_node) #특정 가지 다시 추가
                        if leaf_node not in leaf_node_list: #리프노드리스트에서 해당 노드 제거됐었으면
                            leaf_node_list.append(leaf_node)#다시 리프노드리스트에 리프노드 추가
                        if next_node in leaf_node_list: #새로 추가된 노드가 리프노드리스트에 있으면
                            leaf_node_list.remove(next_node) #추가된 노드 다시 제거
                else: #만약 양이면
                    curr_sheep += 1
                    if curr_sheep > max_sheep:
                        max_sheep = curr_sheep
                    new_edge_to[leaf_node].remove(next_node) #특정 가지 사용 후 제거
                    if len(new_edge_to[leaf_node]) == 0: #해당 노드 가지들 다 썼으면
                            leaf_node_list.remove(leaf_node) #리프노드리스트에서 해당 노드 제거
                    if len(new_edge_to[next_node]) != 0: #새롭게 추가된 노드가 가지가 있으면
                        leaf_node_list.append(next_node) #추가된 노드 리프노드리스트에 추가
                    can_next_step(curr_sheep, curr_wolf, leaf_node_list, new_edge_to)
                    curr_sheep -= 1
                    new_edge_to[leaf_node].append(next_node) #특정 가지 다시 추가
                    if leaf_node not in leaf_node_list: #리프노드리스트에서 해당 노드 제거됐었으면
                        leaf_node_list.append(leaf_node)#다시 리프노드리스트에 리프노드 추가
                    if next_node in leaf_node_list: #새로 추가된 노드가 리프노드리스트에 있으면
                        leaf_node_list.remove(next_node) #추가된 노드 다시 제거
                    
    can_next_step(1,0,[0],new_edge_to)        
    
    return max_sheep

2차 시도

코드 직접 수정

#5시 10분 시작
def solution(info, edges):
    
    max_sheep = 0
    new_edge_to = [[] for _ in range(len(info))]
    #i번째 노드에서 연결되는 한번도 사용안한 엣지가 들어있는 리스트 모음
    
    for edge in edges:
        root, leaf = edge
        new_edge_to[root].append(leaf)
        
    def can_next_step(curr_sheep, curr_wolf, leaf_node_list, new_edge_to):
        #sheep == 0, wolf == 1
        nonlocal max_sheep
        
        # print("=========function call=========")
        # print("curr_sheep=",curr_sheep)
        # print("curr_wolf=",curr_wolf)
        # print("leaf_node_list=",leaf_node_list)
        # print("new_edge_to=",new_edge_to)
        if curr_sheep > curr_wolf:
            max_sheep = max(max_sheep, curr_sheep)
        else:
            # print("=========function end==========")
            return
        if len(leaf_node_list) == 0: #만약 더이상 뻗어나갈수있는 가지가 없으면 진행 안함
            #print("backtrack ending . . .")
            return
        
        for leaf_node in leaf_node_list: #현재 가능한 모든 가지뻗기 경우수 탐색
            for next_node in new_edge_to[leaf_node]: #특정 가지로 뻗어나갔을때
                if info[next_node]:
                    curr_wolf += 1
                    new_edge_to[leaf_node].remove(next_node) #특정 가지 사용 후 제거
                    if len(new_edge_to[leaf_node]) == 0: #해당 노드 가지들 다 썼으면
                        leaf_node_list.remove(leaf_node) #리프노드리스트에서 해당 노드 제거
                    if len(new_edge_to[next_node]) != 0: #새롭게 추가된 노드가 가지가 있으면
                        leaf_node_list.append(next_node) #추가된 노드 리프노드리스트에 추가
                    can_next_step(curr_sheep, curr_wolf, leaf_node_list, new_edge_to)
                    curr_wolf -= 1
                    new_edge_to[leaf_node].append(next_node) #특정 가지 다시 추가
                    if leaf_node not in leaf_node_list: #리프노드리스트에서 해당 노드 제거됐었으면
                        leaf_node_list.append(leaf_node)#다시 리프노드리스트에 리프노드 추가
                    if next_node in leaf_node_list: #새로 추가된 노드가 리프노드리스트에 있으면
                        leaf_node_list.remove(next_node) #추가된 노드 다시 제거
                else: #만약 양이면
                    curr_sheep += 1
                    new_edge_to[leaf_node].remove(next_node) #특정 가지 사용 후 제거
                    if len(new_edge_to[leaf_node]) == 0: #해당 노드 가지들 다 썼으면
                            leaf_node_list.remove(leaf_node) #리프노드리스트에서 해당 노드 제거
                    if len(new_edge_to[next_node]) != 0: #새롭게 추가된 노드가 가지가 있으면
                        leaf_node_list.append(next_node) #추가된 노드 리프노드리스트에 추가
                    can_next_step(curr_sheep, curr_wolf, leaf_node_list, new_edge_to)
                    curr_sheep -= 1
                    new_edge_to[leaf_node].append(next_node) #특정 가지 다시 추가
                    if leaf_node not in leaf_node_list: #리프노드리스트에서 해당 노드 제거됐었으면
                        leaf_node_list.append(leaf_node)#다시 리프노드리스트에 리프노드 추가
                    if next_node in leaf_node_list: #새로 추가된 노드가 리프노드리스트에 있으면
                        leaf_node_list.remove(next_node) #추가된 노드 다시 제거
                    
    can_next_step(1,0,[0],new_edge_to)        
    
    return max_sheep

배우게 된 점 [ 필수 X ]

for 문에서 순회중인 리스트의 정보를 변경할때는 주의해야한다!

remove한 후 append하는 과정에서 현재 순회 중인 리스트를 직접적으로 수정하기에 동일한 정보를 반복 순회하는 경우가 발생합니다. remove 하기 전 index를 저장한 후 append가 아닌 insert로 해당 index에 추가해 주면 됩니다.

질문 [ 필수 X ]

Q1.

어떻게 더 개선해야될지 모르겠습니다..

힌트가 있을까요..

코너케이스 생각해보면서 디버깅 해야하는 상황이나 문제 너무 어려워서 잠시 보류.

피드백 [ 코치 작성 ]

수정할 사항은 총 2가지로 보입니다.

1. 늑대가 양보다 많거나 같아 백트래킹이 발생하는 경우, 양이 늑대보다 많아 max_sheep이 갱신되는 경우를 함수의 맨 앞으로 옮겨야 합니다. 위 코드의 경우 info = [0,1,1], edges = [[0,1],[0,2]]와 같이 두 자식 노드가 전부 늑대라면 max_sheep이 갱신되지 못합니다.
2. leaf_node_list, new_edge_to에서 사용이 완료된 정보를 remove한 후 append하는 과정에서 현재 순회 중인 리스트를 직접적으로 수정하기에 동일한 정보를 반복 순회하는 경우가 발생합니다. remove 하기 전 index를 저장한 후 append가 아닌 insert로 해당 index에 추가해 주면 됩니다.