[2022 KAKAO BLIND RECRUITMENT] 양과 늑대

⭐️ 양과 늑대

heap을 사용해서 양과 늑대의 우선순위 즉 양은 0이므로 앞에 온다. 를 이용해서 빠르게 제출을 할 수 있었다. 27점이나 맞았네..?

 

import heapq

def solution(info, edges):
    graph = [[] for _ in range(len(info))]
    for a,b in edges:
        graph[a].append(b)
        # graph[b].append(a)
    visited = [False] * len(info)

    print(graph)

    def traversing(start, animal: int , sheep, wolf):
        visited[start] = True
        q = []
        heapq.heappush(q, (animal,start))
        # q.append(start)

        while q:
            a, now = heapq.heappop(q)
            print(a, now , "order")

            if a == 0:
                sheep += 1
            else: wolf += 1
            # print(sheep, wolf, "aaaa")
            if sheep <= wolf:
                return sheep, wolf 

            for node in graph[now]:
                # print(info[node], node, "data")
                sheepOrWolf = info[node]
                heapq.heappush(q, (sheepOrWolf, node))


    sheep, wolf  = traversing(0 , 0, 0 ,0 )

    # print(graph)
    print(sheep, wolf)
    return sheep

 

하지만 위 코드에는 치명적인 문제가 있다. 위 코드는 일단 자식노드가 양과 늑대가 둘다 있을 때 효율적인 코드가 된다. 하지만 자식이 늑대만 있고 자식의 자식에 양이있다면? (예제1)

이럴 경우에는 어떻게 해야할까????? 모든 방법으로 순회해서 찾아? 쉽지않다.

결국 어떻게 해야할까.

내 풀이의 문제는 더 밑에 있는 양에 대하여 생각을 못하고 한번 잘못된 계산으로 들어가면 잘못된 답이 나온다는 점. 따라서 복원할 수 있는 계산이 필요하다. 

하지만 모든 경우에 수에 대해 계산을 할 수 있다면 정답은 무조건 찾을 수 있다. 

 

def solution(info, edges):
    answer = 0
    n = len(info)
    graph = [[] for _ in range(n)]
    for edge in edges:
        p,c = edge
        graph[p].append(c)
    stack = [(1,0,[0])] # sheep, wolf, visited
    while stack:
        cur_sheep, cur_wolf, visited = stack.pop()
        answer = max(answer, cur_sheep)
        for cur_node in visited:
            for next_node in graph[cur_node]:
                if next_node not in visited:
                    next_sheep = cur_sheep
                    next_wolf = cur_wolf
                    if info[next_node]:
                        next_wolf += 1
                    else: 
                        next_sheep += 1
                    if next_sheep <= next_wolf:
                        continue
                    stack.append((next_sheep, next_wolf, visited+[next_node]))
    return answer

 

 스택에 양, 늑대, 방문한노드를 저장하는 배열을 넣고 while문에 들어간다.

방문했던 노드들에대해서 첫번째 for문, 한칸 아래층 노드들에 대해서 다음 for문. 그리고 방문했었는지 안했었는지 만약 방문 안했다면 다시체크 (스택을 활용함으로써 다시 체크할 수 있다.)

 

모든 경우의 수에 대해서 체크 할 수 있다. 

 

풀이가 멋있다. 이 문제를 스택의 아름다움? 이라고 해야겠다.

 

DFS로 까지 응용가능 할 것 같은데 일단 머리가 너무아프다. 다음에 또 풀어봐야할 문제 같다.