[알고리즘] dp와 dfs, bfs

https://www.acmicpc.net/problem/1463

 

다음의 문제를 기반으로 dp에 대해 공부하였다

 

문제와 입출력

 

다음의 문제에서 최소의 방식을 구하기 위해 dp를 사용할 수 있다

 

import sys
input = sys.stdin.readline

x = int(input())
d = [0] * (x + 1)

 

우선 다음의 방식으로 시작값과 시작값 만큼의 0으로 채우진 배열을 준비한다

 

for i in range(2, x + 1):
    d[i] = d[i - 1] + 1
    if i % 2 == 0:
        d[i] = min(d[i], d[i // 2] + 1)
    if i % 3 == 0:
        d[i] = min(d[i], d[i // 3] + 1)

 

그리고 0으로 채워진 배열에 반복문으로 모든 경우의 수가 들어가 있는 점화식을 준비한다

print(d[x])

 

그 후 원하는 값을 찾으면 되는 것이다

 

그리고 다음의 문제로 dfs와 bfs에 대해 공부를 하였다

https://www.acmicpc.net/problem/2606

 

문제와 입출력

다음의 문제는 특정한 노드와 연결되어 있는 노드의 개수를 찾는 문제이다 그에 따라 dfs, bfs 모두 사용할 수 있다

 

import sys
input = sys.stdin.readline

n = int(input())
m = int(input())
graph = [[] for _ in range(n+1)]
for _ in range(m) :
    a,b = map(int,input().split())
    graph[a].append(b)
    graph[b].append(a)

 

다음의 방식으로 우선 총 노드의 개수, 그리고 간선의 개수를 받고 노드의 개수 만큼 그래프의 크기를 정한 뒤 간선에 수와 연결된 노드를 입력받아 그래프를 그려준다

 

visited = [False] * (n+1)

 

이후 방문을 확인하기 위해 노드 수 만큼 배열을 만든다

 

q = deque()
q.append(1)
visited[1] = True

 

queue를 만들고 시작 노드를 입력한다

 

cnt = 0

while q : 
    x = q.popleft()
    for nxt in graph[x] :
        if not visited[nxt] :
            visited[nxt] = True
            q.append(nxt)
            cnt += 1
print(cnt)

 

그리고 bfs 로 시작 노드로부터 가장 가까운 노드를 너비탐색하고 방문한 노드를 count하여 출력을 한다

 

이를 dfs로 다시 풀어 보자면

 

def dfs(v):
    global count
    visited[v] = True
    for nxt in graph[v]:
        if not visited[nxt]:
            count += 1
            dfs(nxt)

dfs(1)
print(count)

 

시작 노드에서 갈 수있는 노드를 깊이 탐색하며 방문한 노드를 count하여 출력하게 된다