dfs(백트래킹)가 어려운 나를 위해

다음과 같은 템플릿을 따라가라.

대부분은 해결 가능할 것.

def dfs(...):
    if ... :		# 결과 도출 or 함수 종료 조건
        return  
    
    for ... :		# 다음 탐색 노드들
        if ... :		# 볼 필요도 없는 얘들 제거
            dfs(,,,)		# 재귀 호출

 

 

# 예시

def dfs(graph, v, visited):
    visited[v] = True   # 현재 노드를 방문 처리
    print(v, end= ' ')

    for i in graph[v]:  # 현재 노드와 연결된 다른 노드를 재귀적으로 방문
        if not visited[i]:
            dfs(graph, i, visited)

"""
정수 N을 입력받아 1부터 N 까지의 숫자 중에서 합이 10이 되는 조합을 리스트로 반환
"""

def solution(N):
    results = []

    def bt(sum, selected_nums, start):
        if sum == 10:
            results.append(selected_nums)
            return

        for i in range(start, N+1):
            if sum + i <= 10:
                bt(sum+i, selected_nums + [i], i+1)

    bt(0, [], 1)

    return results

def find_solution():
    empty_pos = find_empty_position()

    if not empty_pos:
        return True

    row, col = empty_pos
    for num in range(1, 10):
        if is_valid(num, row, col):
            board[row][col] = num
            if find_solution():
                return True
        board[row][col] = 0

    return False

 

return True 를 할거면, 이렇게 하라. 

if dfs(): return True 

이래야 끝남

def dfs(hp, dgs, visited):
    global answer

    answer = max(answer, len(visited))

    for i in range(len(dgs)):
        a, b = dgs[i]
        if is_valid(hp, dgs[i]):
            dfs(hp-b, dgs, visited | {i})

 

근데 바로 위 dfs() 메서드를 보면, visited 집합이 계속 추가됨

만약 메모리를 계속 먹는게 좀 그렇다 하면은, visited 을 배열로 해가지고 1, 0 처리할 수도 있음

아래처럼

def dfs(hp, dgs, visited):
    global answer
	
    // 정답 도출은 알아서

    for i in range(len(dgs)):
        a, b = dgs[i]
        if is_valid(hp, dgs[i]):
            visited[i] = 1
            dfs(hp-b, dgs, visited)
            visited[i] = 0

 

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

def solution(word):
    answer = -1

    chars = ['A', 'E', 'I', 'O', 'U']

    def dfs(string):
        nonlocal answer
        answer += 1

        if string == word:
            return True

        if len(string) == 5:
            return False

        for c in chars:
            if dfs(string + c):
                return True

    dfs('')

    return answer

 

++

백트래킹 문제에서 combinations 를 쓰는 경우도 많다.

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

프로그래머스

 

중복조합 + Counter