[파이썬 python 3] 카카오 코딩테스트 - 프로그래머 스 양과 늑대

2022 카카오 코딩 테스트에  출제된 양과 늑대 문제를 python 3으로 풀어보겠습니다.

 

1. 문제 링크

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

2. 문제 요약

2진 트리 모양 초원의 루트 노드에서 출발하여 각 노드를 돌아다니면서 양을 모으려 한다. 각 노드를 방문할 때 마다 해당 노드에 있던 양과 늑대가 당신을 따라오게 된다. 당신이 모은 양의 수보다 늑대의 수가 같거나 더 많아지면 모든 양을 잡아먹어 버린다. 각 노드를 방문하면서 모을 수 있는 양은 최대 몇 마리인가?

3. 아이디어 정리

• DFS, 백트래킹 → 가능한 경우의 수를 전부 탐색하면서 모을 수 있는 최대 양의 수 찾기
• 0 -> 1로 가는 경우에 2로 갈 수도 있고, 4로 갈 수도 있고, 8로 갈 수 있음에 유의

   양 > 늑대 일 때, 백트래킹 진행

         1. 양의 최대값 갱신

         2. 현재 조회 가능한 노드를 하나씩 꺼내 현재 노드에서 다음 노드로 진행 가능한 dfs진행

         3. 다음 접근 가능한 노드는 내 동료 노드 & 내 자식 노드

 

4. 풀이

from collections import defaultdict

answer = 0
def solution(info, edges):

    def dfs(sheep, wolf, next_list):
        global answer
        if sheep <= wolf:
            return
        else:
            answer = max(answer, sheep)
            for next in next_list:  # 다음 가능한 노드를 돌리기
                # 다음에 가능한 리스트 넣기 & 자기 자신 빼기
                child = graph[next]
                next_list |= child
                next_list -= set([next])
                if info[next] == 0:
                    sheep += 1
                else:
                    wolf += 1
                dfs(sheep, wolf, next_list)
                # 원래대로 복원
                next_list |= set([next])
                next_list -= child
                if info[next] == 0:
                    sheep -= 1
                else:
                    wolf -= 1

    graph = defaultdict(set)
    for u, v in edges:
        graph[u].add(v)

    dfs(1, 0, graph[0])

    return answer

 

5. 배울점

• defaultdict 은 사전형 + set형태로 set의 특징을 이용할 수 있다. 
• set은 중복값을 허용하지 않는다. 
• |= 연산으로 쉽게 원소들을 합칠 수 있다.
• -=연산으로 쉽게 원소들을 삭제할 수 있다. 

6. 다른 풀이

이 문제는 백트래킹으로 풀면 비효율적이라는 바킹독님의 글을 보았습니다.

비트마스킹을 이용한 바킹독님의 풀이도 참고하시길 바라겠습니다.

바킹독 양과 늑대라고 검색하시면 나옵니다.

 

+2021 카카오 코딩테스트 광고 삽입 문제도 있습니다.

2022.03.14 - [알고리즘 TIL] - [파이썬 python 3] 카카오 코딩 테스트 - 프로그래머 스 광고 삽입

[파이썬 python 3] 카카오 코딩 테스트 - 프로그래머 스 광고 삽입