[Python][Graph] 양과 늑대 - 프로그래머스

[문제]

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

프로그래머스

 

[느낀점 / 깨달은 점]

• 못 풀었다.. 방문한 노드는 또 갈 수 있는 것을 깨닫고 코드를 고쳤지만, recursion maximum length 초과로 실패
• 검색하여 코드 참조하였을 때, 대단한 코드 발견 
  • 노드를 지날 때마다 현재의 양의 개수를 저장함.
  • 방문할 노드는 부모노드가 방문이 되었고, 자식 노드가 방문이 안된 자식노드임.
    • 이 아이디어가 대박이다....
  • 이를 끝내고, 방문할 때마다 저장된 양의 개수 리스트에서 max 값이 정답.
• 함수의 인자를 다른 함수에서 사용하는 방법(프로그래머스는 함수로 주어지기 때문)
  • 함수내의 함수로 작성하기.
  • 따로 함수밖에서 global로 선언하지 않고, 함수 내에서 'global'로만 선언해서 사용하는 방법(한번 test해보기)

 

[멋진 아이디어의 정답 코드] - 방문할 노드를 부모노드가 방문이 되었고, 자식 노드가 방문이 안된 자식노드로 탐색
출처 : https://velog.io/@thguss/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-L3-%EC%96%91%EA%B3%BC-%EB%8A%91%EB%8C%80-python

def solution(info, edges):
    visited = [0] * len(info)
    answer = []
    
    def dfs(sheep, wolf):
        if sheep > wolf:
            answer.append(sheep)
        else:
            return 
        
        for p, c in edges:
            if visited[p] and not visited[c]:
                visited[c] = 1
                if info[c] == 0:
                    dfs(sheep+1, wolf)
                else:
                    dfs(sheep, wolf+1)
                visited[c] = 0

	# 루트 노드부터 시작
	visited[0] = 1
    dfs(1, 0)

    return max(answer)

 

[정답 코드2] - 방문할 노드를 지금까지 방문한 노드들의 자식노드들을 리스트로 저장.
출처:https://alreadyusedadress.tistory.com/325

def dfs(idx, sheep, wolf, possible):
    global g_info, answer, graph
    if g_info[idx] == 0:
        sheep += 1
        answer = max(answer, sheep)
    else:
        wolf += 1
        
    if wolf >= sheep:
        return 
    
    possible.extend(graph[idx])
    for p in possible:
        dfs(p, sheep, wolf, [i for i in possible if i != p])
    
def solution(info, edges):
    global answer, g_info, visited, graph
    answer = 0
    g_info = info
    n = len(info)
    graph = [[] for _ in range(n)]
    
    for a, b in edges:
        graph[a].append(b)
        
    
    dfs(0, 0, 0, [])
    return answer

 

[나의 코드(틀린 코드)]

import copy
def back_tracking(node, num_snw, route, v):
    global answer
    
    is_v = True
    for vv in v:
        if vv==0:
            is_v = False
            break
    if is_v :
        return
        
    route.append(node)
    # print(route)
    
    if info_[node] == 0 and v[node] == 0:
        num_snw[0] +=1
    elif info_[node] == 1 and v[node] == 0 :
        num_snw[1] += 1
    
    v[node] =1
    if answer <= num_snw[0] :
        global route_max
        route_max = route
    answer = max(num_snw[0], answer)
    
    if num_snw[0] <= num_snw[1] :
        return
    
    if node in d :
        
        for next_node in d[node]:
            num_snw_temp = copy.deepcopy(num_snw)
            route_temp = copy.deepcopy(route)
            v_temp = copy.deepcopy(v)
            
            if len(route) >= 3 and route[-1] == route[-3] and next_node == route[-2]:
                continue
                
            back_tracking(next_node, num_snw_temp, route_temp, v_temp)
            
answer = 0
d = {}
info_ = None
route_max= []
def solution(info, edges):
    global answer, info_
    info_ = info
    
    for edge in edges:
        if edge[0] in d :
            d[edge[0]].append(edge[1])
            d[edge[1]] = [edge[0]]
        else :
            d[edge[0]] = [edge[1]]
            d[edge[1]] = [edge[0]]
    
    print(d)
    v = [0 for _ in range(len(info))]
    back_tracking(0, [0, 0], [], v)
    print(route_max)
    print(answer)
    
    return answer