[프로그래머스 lv3] 양과 늑대, 백트래킹(Backtracking)과 DFS

프로그래머스

Backtracking(백트래킹)

백트래킹 알고리즘은 조건을 만족하는 아웃풋을 찾기 위해서 brute force approach를 사용하는 문제 해결 알고리즘이다.

Brute force approach: 가능한 모든 해결 방법을 시도해보고 best 해결 방법을 탐색하는 방식

모든 가능성은 하나의 트리처럼(State Space Tree) 구성할 수 있으며, 가지 중에 해결책이 있다. 트리를 검사하기 위해 DFS(Depth First Search)를 사용한다. 기본 흐름은 다음과 같다.

• 오답을 만나면 이전 분기점으로 돌아간다.
• 시도해보지 않은 다른 해결 방법이 있으면 시도한다.
• 해결 방법이 더 없으면 더 이전의 분기점으로 돌아간다.
• 모든 트리의 노드를 검사해도 답을 못 찾을 경우, 이 문제의 해결책은 없는 것이다.

현재 해결법이 적합하지 않다면 이전으로 돌아가기 때문에 재귀함수로 구현되며, DFS와 비슷하지만 메모리는 덜 차지한다.

State Space Tree

Space state tree는 문제 풀이를 할 수 있는 모든 경우를 나타낸 트리로, 트리의 루트 노드는 초기 상태이고, 리프(leaf)는 종료 상태이다.

https://www.programiz.com/dsa/backtracking-algorithm

Backtracking Algorithm

Backtrack(x)
    if x is not a solution
        return false
    if x is a new solution
        add to list of solutions
    backtrack(expand x)

Solution이 아니라면 false를 return해서 다음 풀이를 진행하고, solution이라면 해결법으로 추가한다.

 

 

 

DFS

깊이 우선 탐색. BFS에서 방문 할 노드를 큐에 저장했다면, 큐를 스택으로 바꿔주면 DFS 알고리즘이 된다.

[python] 프로그래머스 lv3: 가장 먼 노드(그래프, bfs, bfs depth)

--> BFS 코드

 

 

 

문제 풀이 코드

def solution(info, edges):
    global max_sheep
    max_sheep = 0
    #graph 생성
    nodes = len(info)
    graph = [[] for _ in range(nodes)]
    for p, c in edges:
        graph[p].append(c)
    
    def dfs(now, nxt, sheep, wolf):
        global max_sheep
        #양/늑대 카운트 및 유효검사
        if info[now]:
            wolf += 1
        else:
            sheep += 1
            max_sheep = max(sheep, max_sheep)
        if sheep <= wolf:
            return 0
        
        #다음 루트 탐색 및 찾은 루트로 dfs 재귀
        for i in nxt:
            for node in graph[i]:
                if node not in nxt:
                    nxt.append(node)
                    # dfs 재귀
                    dfs(node, nxt, sheep, wolf) #아래로 아래로..
                    nxt.pop()
                    
    dfs(0, [0], 0, 0)

    return max_sheep

공백, 주석 제외 25줄

 

 

Reference

https://ko.wikipedia.org/wiki/%ED%87%B4%EA%B0%81%EA%B2%80%EC%83%89

https://ko.wikipedia.org/wiki/%EA%B9%8A%EC%9D%B4_%EC%9A%B0%EC%84%A0_%ED%83%90%EC%83%89

https://www.programiz.com/dsa/backtracking-algorithm