[프로그래머스] Level3 : 양과 늑대(파이썬)

백트래킹 문제

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

프로그래머스

 

---

💡 풀이코드1(Python 성공-DFS)

양방향 그래프일 필요 X

단방향 그래프를 통하여, 재귀호출을 구현할 수 있는 방법을 찾을 필요가 존재합니다.
바로 그 답은, 다음 차례에 이동 가능한 정점을 따로 담아서 재귀호출을 하는 것입니다.

def dfs(idx, sheep, wolf, possible):
    global g_info, answer, graph
    print(idx, possible, sheep)
    
    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

 

💡 풀이코드2(Python 성공-DFS)

def solution(info, edges):
    answer = []
    visited = [False] * len(info)
    
    
    def dfs(sheeps, wolves):
        if sheeps > wolves:
            answer.append(sheeps)
        else:
            return
        
        for p, c in edges:
            # 부모는 방문하였지만 자식은 방문 안한 경우만 진행
            if visited[p] and not visited[c]:
                visited[c] = True
                if info[c] == 0:
                    dfs(sheeps + 1, wolves)
                else:
                    dfs(sheeps, wolves + 1)
                # 만약 다른 곳을 들렸다 방문 시 조건에 충족할 수 있어 false 처리
                visited[c] = False
                
    visited[0] = True
    dfs(1, 0)
    
    return max(answer)

---

💡 풀이코드(Python 실패-DFS)

 

def solution(info, edges):
    global sheep, wolf
    answer = 0
    graph = [[] for _ in range(len(info))]
    
    for a,b in edges:
        graph[a].append(b)
        
    
    sheep = 1
    wolf = 0
    def dfs(n, s, w):
        global sheep, wolf
        
        visited[n] = True
        
        if all(visited) or 0 not in info:
            return
        
        for i in graph[n]:
            if info[i] == 0:
                
                if sheep + 1 > w:
                    info[i] = 2 # 데려옴
                    sheep += 1
                    wolf = w
                    dfs(i, s+1, w)
            
            elif info[i] == 2:
                if sheep > w:
                    dfs(i, s, w)
            else:
                if sheep > w + 1:
                    dfs(i, s, w+1)
        return w
                    


    visited = [False for _ in range(len(info))]
    
    while True:
        if all(visited) or 0 not in info:
            break
        
        dfs(0, sheep, wolf)
    
    dfs(0, 1, 0)
    answer = sheep
        
    return answer

 

 

 

---

https://school.programmers.co.kr/questions/25736?question=25736

프로그래머스

 

https://tight-sleep.tistory.com/34

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

 

https://talktato.tistory.com/62

[programmers] 양과 늑대 (python)