[프로그래머스] 코딩테스트 고득점 Kit - DFS/BFS (파이썬)

💻 타겟 넘버 (level 2)

count = 0
def dfs(idx, value, numbers, target):
    global count
    l = len(numbers)
    
    # 종료조건
    if idx == l:
        if value == target:
            count += 1
        return
    
    dfs(idx+1, value + numbers[idx], numbers, target)
    dfs(idx+1, value - numbers[idx], numbers, target)
    

def solution(numbers, target):
    global count
    dfs(0, 0,numbers, target)	# 초기 value가 0인 이유는 4랑 -4로 나눠져야 하니까
    
    return count

• 이런느낌으로 dfs를 사용
  idx를 1씩 증가시키면서 위 그래프의 모든 경로를 따라 더한다.

---

💻 네트워크 (level 3)

def dfs(n, computers, com, visited):
    visited[com] = True
    for ntw in range(n):
    	# 자기 번호에도 1이 있으므로 그거 제외해야함
        if ntw != com and computers[com][ntw] == 1:
            if not visited[ntw]:
                dfs(n, computers, ntw, visited)

def solution(n, computers):
    count = 0
    visited = [False] * n
    for i in range(n):
        if not visited[i]:
            dfs(n, computers, i, visited)
            count += 1
    return count

• computers list에서 computer 하나하나씩 dfs로 살펴보는 느낌, visited는 공통적으로 하나만 쓴다
• dfs 안에 들어와서는 네트워크를 기준으로 다룬다 (간선)

---