Algorithm - DFS/BFS

dfs

visited = [-1]*(V+1)
visited[1] = 0

# 리턴 값 없음. visited에 모든 노드까지의 거리 저장
def DFS(node, dist):
    for v, d in tree[node]:
        cal_dist = dist + d
        if visited[v] == -1:
            visited[v] = cal_dist
            DFS(v, cal_dist)
    return

전력망을 둘로 나누기

from collections import defaultdict

def solution(n, wires):
    answer = 100
    link=defaultdict(list)
    for a,b in wires:
        link[a].append(b)
        link[b].append(a)

    def calc(node, _from, link, visited):
        visited[node]=1
        network=link[node]
        cnt=1
        for _next in network:
            if _next==_from or visited[_next]==1: continue
            cnt+=calc(_next, node, link, visited)
        return cnt

    for _from, _to in wires:
        visited=[0 for _ in range(n+1)]
        from_total=calc(_from, _to, link, visited)
        to_total=n-from_total
        gap=from_total-to_total
        if gap<0: gap*=-1
        answer=min(answer, gap)

    return answer

타겟 넘버

• visited 사용 x(인덱스가 높은 순으로 depth가 깊어지기 때문에)

cnt=0
def dfs(numbers, target, idx, sum):
    global cnt
    if sum==target:
        cnt+=1
        return
    if idx>=len(numbers):
        return
    if sum==target:
        cnt+=1
        return
    dfs(numbers,target,idx+1,sum+numbers[idx])
    dfs(numbers,target,idx+1,sum)
    
def solution(numbers, target):
    global cnt
    numbers_sum=sum(numbers)
    target=numbers_sum-target
    if target<=0 or target%2 :
        return 0
    dfs(numbers, target/2, 0, 0)
    return cnt

트리의 지름

# 참고 -> 트리의 지름 구하기
1. 노드를 하나 정하고, 그 노드에서 가장 멀리 떨어진 노드 A를 찾는다.
2. A에서 가장 멀리 떨어진 노드(B)를 또 찾는다. 
3. 이때 A에서 B까지의 거리가 트리의 지름이다.

DFS + DP

내리막 길

import sys
input = sys.stdin.readline
m,n=list(map(int, input().split()))
board=['' for i in range(m)]
for i in range(m):
    board[i]=list(map(int,input().split()))

cnt=0
dy,dx=[1,-1,0,0],[0,0,1,-1]

def dfs(y,x,dp,height):
    if y==m-1 and x==n-1: return 1 
    if dp[y][x]!=-1: return dp[y][x]
    cnt=0
    for i in range(4):
        ny,nx=y+dy[i],x+dx[i]
        if 0<=ny<m and 0<=nx<n and board[ny][nx]<height:
            cnt+=dfs(ny,nx,dp,board[ny][nx])
    dp[y][x]=cnt
    return dp[y][x]

dp=[[-1 for _ in range(n)] for _ in range(m)]
dfs(0,0,dp,board[0][0])
print(dp[0][0])

bfs