[Programmers] Python 프로그래머스 양과 늑대(92343)

https://school.programmers.co.kr/learn/courses/30/lessons/92343

프로그래머스

 

백트래킹을 좀 특이하게 쓰는 방식의 문제이다.

 

def solution(info, edges):

    graph = [[] for _ in range(len(info))]
    visited = [False] * (len(info))
    max_value = 1

    for s,e in edges:
        graph[s].append(e)

    def dfs(v,sheep, wolf, now_lst):
        nonlocal max_value
        if sheep <= wolf or not now_lst:
            return

        now_lst = graph[v] + now_lst


        for i in now_lst:
            if not visited[i]:
                visited[i] = True
                if info[i] == 0:
                    dfs(i,sheep+1,wolf,now_lst)

                else:
                    dfs(i,sheep,wolf+1,now_lst)
                visited[i] = False

        max_value = max(max_value, sheep)

    visited[0] = True
    dfs(0,1,0,[0])

    return max_value


print(solution([0,1,0,1,1,0,1,0,0,1,0],[[0,1],[0,2],[1,3],[1,4],[2,5],[2,6],[3,7],[4,8],[6,9],[9,10]]))

 

회고.

now_lst = graph[v] + now_lst

이부분 처럼 세계선으로 추가해서 다시금 탐색하지 않은 노드를 탐색하는 방법을 고안하지 못해서 초반 코드가 굉장히 복잡해졌다. 이런식으로 백트래킹의 그래프도 연결하는 방법이 있다는 점을 유의하고 있어야 겠다...

그래도, 새로운 방법을  배워 만족스러운 문제였다.