DFS 관련 연산 문제

DFS 관련 연산 문제

---

DFS

def dfs(파라미터 값):
	if 종료조건:
    	출력해야할 파라미터값(없으면 생략)
        return
        
	# 계속 탐색
	else:
    	dfs(파라미터값)

 

📝 파라미터 값

• 현재 탐색위치
• 탐색 조건
• 탐색 후, 출력해야 하는 결과값
• 탐색 대상

 

📝 종료 조건

매우 중요한 설정! 언제까지 탐색할 껀지!!

---

📝 프로그래머스, 타겟넘버

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

프로그래머스

# -------------------- dfs 풀이 ----------------------------

# 전달해야하는 파라미터
# 1. 현재까지의 합, cur_sum
# 2. 현재 탐색 순서, cur_idx
# 3. 탐색 대상 numbers 리스트

numbers = [4, 1, 2, 1]
target = 4
sums = []

def dfs(numbers, cur_idx, cur_sum):
    # 종료 조건
    if cur_idx == len(numbers):
        sums.append(cur_sum)
        return sums.count(target)

    dfs(numbers, cur_idx+1, cur_sum + numbers[cur_idx])
    dfs(numbers, cur_idx+1, cur_sum - numbers[cur_idx])

dfs(numbers, 0, 0)
print(sums.count(target))

---

📝 백준 14888번

# 계속 탐색해야 하는 조건
# add, sub, mul, div 값이 모두 0이 될때 까지, 이 값도 계속 변함.
# cur_idx가 numbers 길이와 일치할때 까지

# 출력해야하는 값
# 연산 결과값. result가 계속 변하니깐 param값에 들어가야 겠지!
# 연산 결과값읠 최대(max_result), 최소(min_result)

import sys

n = int(sys.stdin.readline().rstrip())
numbers = list(map(int, sys.stdin.readline().rstrip().split()))
add, sub, mul, div = map(int, sys.stdin.readline().rstrip().split())

# print(n)
# print(numbers)
# print(add, sub, mul, div)

max_result = float('-inf')
min_result = float('inf')

def dfs(numbers, add, sub, mul, div, cur_result, cur_idx):
    global max_result, min_result

    # 종료 조건 numbers 다 탐색했을 때
    if cur_idx == len(numbers): # cur_idx == n
        max_result = max(max_result, cur_result)
        min_result = min(min_result, cur_result)
        return 
    # 탐색 조건
    else:
        if add:
            dfs(numbers, add-1, sub, mul, div, cur_result+numbers[cur_idx], cur_idx+1)
        if sub:
            dfs(numbers, add, sub-1, mul, div, cur_result-numbers[cur_idx], cur_idx+1)
        if mul:
            dfs(numbers, add, sub, mul-1, div, cur_result*numbers[cur_idx], cur_idx+1)
        if div:
            dfs(numbers, add, sub, mul, div-1, int(cur_result/numbers[cur_idx]), cur_idx+1)

# 처음 시작할때 cur_result값에는 numbers[0] 값을 넣어주고 시작
# 현재 인덱스 값으로는 1을 넣어줘야 numbers[0] (연산) numbers[1]이 되니깐 계속 탐색!!! 
dfs(numbers, add, sub, mul, div, numbers[0], 1)

print(max_result)
print(min_result)

 

타겟넘버 코드와 비슷하게 구성하고 싶으면,

리스트 result를 만들고 모든 탐색이 끝나고 탈출하면서 result.append(cur_result)를 넣어준뒤,

출력을 max(result), min(result)하면 될듯하다.

하지만, target넘버와는 다른게 모든 탐색의 연산값을 저장해둘 필요가 없으므로 max, min값만 저장되도록 하는게 더 효율적이라 생각한다.

---

📝 앞으로 공부 방향

 

reference code(검색해서 나온 결과중, 내가 이해 가능한 코드)를 참고해 문제를 이해하고 아예 안보고 짜본 코드이다.

dfs(재귀함수)를 완벽하게 이해한 뒤, bfs도 구현해 보는걸 목표로 하고 공부해야 겠다.

 

dfs는 탈출조건설정과 param값(탐색하는 과정에서 변하는 값)들 설정이 매우 중요한 것 같다.

이 값들에 집중해서 refernce code를 이해한 뒤, 안보고 구현해보는 연습을 해야겠다.