자격증/PCCP 6

[Graph] 알고리즘 및 문제풀이

그래프는 회로가 존재할 수 있지만 트리는 회로가 존재하지 않음(트리는 회로가 없기 때문에, 어느 한 선을 끊어주면은 둘로 나뉜다) 회로가 없는 그래프라고 가정하고 풀기 차례로 하나씩 끊어보기 check 배열 ch를 만들기 3-4를 끊고싶으면 ch[4]=1로 해놓고 DFS(3)을 돌려보기 def DFS(v,ch,graph) global cnt cnt += 1 for i in graph[v]: if ch[i]==0 DFS(i,ch,graph) 전체 코드 cnt = 0 def DFS(v, ch, graph): global cnt ch[v] = 1 cnt += 1 for i in graph[v]: if ch[i] == 0: DFS(i, ch, graph) def solution(n, wires): global ..

자격증/PCCP 2024.02.29

[Graph] 그래프 표현법(인접행렬 & 인접리스트)

인접행렬 Graph: 정점과 정점을 연결하는 간선의 집합(정점과 간선의 집합) a와 b가 연결되어 있을 때 아래와 같이 표시 graph[a][b]=1 graph[b][a]=1 정점의 개수가 n개면 n*n 배열을 선언해야 함 노드는 100개 밖에 안되는데 100*100 = 10,000을 접근해야 함 인접 행렬은 정점의 개수가 많아질수록 저장 공간이 낭비가 됨 인접 리스트 인접 행렬이 너무 많은 저장 공간을 낭비하기 때문에 인접 리스트 방식을 생각함 > 시간 복잡도, 공간 복잡도가 확 줄어듬 인접 리스트 구현 graph = [[] for _ in range(6)] # [] [] [] [] [] [] for a, b in edges: graph[a].append(b) graph[b].append(a) 3번 정..

자격증/PCCP 2024.02.29

[BFS] 레벨탐색(BFS 익히기)

Level 순으로 탐색: Level 0 다 탐색했으면 → Level 1 탐색 → Level 2 탐색 → Level 3 탐색 BFS: 출발상태에서 도착상태까지 최소 횟수 구하는 문제 Level 0 1 Level 1 2 3 Level 2 4 5 6 7 from collections import deque: def BFS(): dQ=deque() dQ.append(1) L = 0 while(dQ): #dQ가 비어있으면 멈춤 length=len(dQ) for _ in range(length): v=dQ.popleft() print(v, end='') for nv in [v*2, v*2+1]: if nv > 7: continue dQ.append(nv) L += 1 BFS()

자격증/PCCP 2024.02.27