[프로그래머스 | 파이썬] BFS와 DFS (4)/ 타겟넘버, 네트워크

▶ 타겟 넘버

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

코딩테스트 연습 - 타겟 넘버

 

>dfs 풀이

숫자의 추가가 numbers리스트 길이까지 이뤄지면 재귀함수 호출을 종료한다. 만약 numbers 리스트 길이까지 숫자가 추가되고 이들을 모두 더한 값인 value가 target 수와 같아지면 answer에 1씩 더해준다. 

def dfs(numbers, target, idx, value):
    global answer
    num= len(numbers)
    if idx == num and value ==target:
        answer += 1
        return
    if idx == num:
        return

    dfs(numbers,target, idx+1, value+numbers[idx])
    dfs(numbers,target, idx+1, value-numbers[idx])

def solution(numbers, target):
    global answer
    answer=0
    dfs(numbers, target, 0, 0)
    return answer

만일 numbers가 [1,1,1,1,1]이고 target이 3이라면 해당 코드는 다음과 같이 구현된다. 

idx가 5가 될때까지 계속 그래프를 탐색하면서 노드의 값을 더해주다가 idx가 5에 도달하고 합한 값이 3과 동일한 경우에 answer값을 하나씩 더해줌으로써 답을 구할 수 있다. 

 

 

 

▶ 네트워크

https://programmers.co.kr/learn/courses/30/lessons/43162

코딩테스트 연습 - 네트워크

 

> dfs 풀이

함수 dfs를 통해 특정 노드와 연결된 노드들이 있으면 그 노드들은 모두 visited를 False에서 True로 바꿔줌으로써 방문처리한다. 

solution에서 visited리스트에서 아직 방문하지 않은 것으로 판정된 노드들에 대해서 dfs함수를 수행한다. 더이상 연결 노드가 없고 연결된 노드 중에서 방문하지 않은 노드가 없어 함수를 빠져나왔을 때 answer에 1을 더해준다. 그리고 solution에서 while문에서 방문하지 않은 노드들이 있으면 다시 dfs함수를 수행해준다. 

def dfs(n,v):
    global computer
    global answer
    global visited
    visited[v]=True
    for i in range(len(computer[v])):
        if computer[v][i] ==1 and not visited[i]:
            dfs(n,i)

def solution(n,computers):
    global computer
    global answer
    global visited
    answer=0
    computer= computers
    visited= [False] * n
    i=0
    while False in visited:
        if visited[i]==False:
            dfs(n,i)
            answer+=1
        i+=1
    return answer