[Algo] BFS/DFS 다시 풀어볼 문제 모음

1. 프로그래머스 - 타겟넘버

소요시간: 1)해결 못함 2) 해결!

def solution(numbers, target):
    parent = [0]
    for num in numbers:
        child = []
        for n in parent:
            child.extend([n + num, n + num * -1])
        parent = child
    return parent.count(target)

2. 프로그래머스 - 네트워크

소요시간: 1)해결못함

def DFS(x, n, computers,visited):
    visited[x] = 1
    for k in range(n): 
        if computers[x][k] == 1 and visited[k] == 0:
            visited[k] = 1
            DFS(k, n, computers,visited) 
            
def solution(n, computers): 
    cnt = 0
    visited = [0] * n
    for i in range(n): 
        if visited[i] == 0:
            DFS(i, n, computers,visited) 
            cnt += 1
    return cnt

3. 백준 -

n = int(input())
arr = list(map(int,input().split(' ')))
target = int(input())
ans = 0

def dfs(num, arr):
    arr[num] = -2
    for i in range(n):
        if num == arr[i]:
            dfs(i, arr)


dfs(target,arr)

for i in range(n):
    if arr[i] != -2 and i not in arr:
        ans += 1

print(ans)

4. 프로그래머스 - 전력망을 둘로 나누기

def bfs(v, graph, visited):
    q = [v]
    cnt = 0
    while q:
        node = q.pop(0)
        for n in graph[node]:
            if visited[n] == False:
                visited[n] = True
                cnt += 1
                q.append(n)
    return cnt
                
def solution(n, wires):
    graph = [[] for _ in range(n+1)]
    for v, u in wires:
        graph[v].append(u)
        graph[u].append(v)

    answer = 100
    for i in range(n-1):
        visited = [False for _ in range(n+1)]
        v1, v2 = wires[i]
        visited[v2] = True
        visited[v1] = True
        
        tmp = abs(bfs(v1, graph, visited) - bfs(v2, graph, visited))
        answer = min(tmp, answer)

    return answer