dfs

코드1 (dfs) n,m,k = map(int, input().split()) money = [0,*map(int, input().split())] graph = [[] for _ in range(n+1)] visited = [0]*(n+1) for _ in range(m): x,y = map(int, input().split()) graph[x].append(y) graph[y].append(x) moneylist = [] def dfs(a, graph, visited): stack = [a] visited[a] = 1 cost = money[a] while stack: pn = stack.pop() for i in graph[pn]: if not visited[i]: visited[i] = 1 cos..

DFS 코드 import sys sys.setrecursionlimit(10**9) # 재귀 제한 설정 input = sys.stdin.readline a, b = map(int, input().split()) tree = [[] for _ in range(a+1)] count = 0 # 연결 요소 개수 세기 visited = [] # 방문 여부 확인 for _ in range(b): x,y = map(int, input().split()) tree[x].append(y) tree[y].append(x) def dfs(v, graph, check_visit): check_visit.append(v) for i in graph[v]: if i not in check_visit: dfs(i, graph, c..

코드 import sys sys.setrecursionlimit(10**9) input = sys.stdin.readline a = int(input()) tree = [[] for _ in range(a+1)] visited = [False] * (a+1) # for 방문여부 체크 parents = [0] * (a+1) # for 부모노드 기록 # 그래프 작성 for _ in range(a-1): x,y = map(int, input().split()) tree[x].append(y) tree[y].append(x) def dfs(v, graph, visit_check): visit_check[v] = True # 방문 여부 확인 for i in graph[v]: if visit_check[i] != ..

해당 글은 https://8iggy.tistory.com/104 를 참고하여 썼습니다. DFS 진짜 어렵다... 너무 어렵다. 그래도 해야겠지. 가봅시다. DFS는 그래프 탐색을 할 때 사용하는 알고리즘으로, Depth First Search의 줄임말이다. 깊이 우선 탐색을 뜻하며 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. DFS는 stack이나 재귀함수를 이용해서 구현할 수 있다. DFS의 동작과정은 다음과 같다. 1. 탐색 시작 노드를 스택에 삽입하고 방문처리를 한다. 2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접노드를 스택에 넣고 방문처리를 한다. 방문하지 않은 노드가 없다면 스택에서 최상단 노드를 꺼낸다. 3. 2의 과정을 더 이상 수행할 수 없을 때까지 반복..