Graph
[DFS, Graph] BOJ 9466 텀 프로젝트
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 import sys from collections import deque input = sys.stdin.readline T = int(input()) ''' 그래프 문제 중에서 순환 고리를 찾는 문제 ''' def dfs(n, graph): visited = [False] * (n+1) cnt = 0 for i in range(1, n+1): if visited[i]: continue cycle = [] queue = deque() queue.append(i) while queue: # dfs node = que..
[그래프, 다익스트라] BOJ 1753 최단경로
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 import sys import heapq input = sys.stdin.readline V, E = map(int, input().split()) K = int(input()) INF = int(1e9) graph = [list(map(int, input().split())) for _ in range(E)] graph_dict = dict() for u, v, w in graph: if not graph_dict.get(u): graph_dict[u] = [[w, v]] else: graph_dic..
[Graph] BOJ 1043 거짓말
https://seclab-j.tistory.com/102 그래프 관련 알고리즘 요약 정리 (크루스칼, 프림, 위상 정렬) 그래프를 사용하는 알고리즘은 뭐가 있을까? - 크루스칼, 프림, 위상 정렬 https://seclab-j.tistory.com/86 그래프 이론 요약 정리 그래프란? 그래프란 정점(Edge)과 간선(Vertex/Node)으로 이루어진 자료구조 seclab-j.tistory.com 해당 문제를 푸려면 Graph의 집합 알고리즘, union과 find를 사용해야한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 4..
[백트래킹] BOJ 15649 N과 M (1)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 import sys input = sys.stdin.readline def backtracking(n, N, M): if n == M: print(" ".join(map(str, arr))) return for i in range(1, N+1): if is_used[i] == 0: is_used[i] = 1 arr[n] = i backtracking(n+1, N, M) is_used[i] = 0 N, M = map(int, input().split()) arr = [0 for _ in range(M)] is_used = [0 for _ in range(N+1)] backtracking(0, N, M) Colored..
[Graph, DFS, BFS] BOJ 2606 바이러스
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 import sys from collections import deque input = sys.stdin.readline N = int(input()) E = int(input()) arr = [list(map(int, input().split())) for _ in range(E)] graph = [[] for _ in range (N+1)] for start, end in arr: graph[start].append(end) graph[end].append(start) result = 0 visited = [0] * (N+1) q = deque() q.append(1)..
[Graph, DFS, BFS] BOJ 1260 DFS와 BFS
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 import sys from collections import deque input = sys.stdin.readline N, M, V = map(int, input().split()) arr = list(map(int, input().split()) for _ in range(M)) # graph 생성 graph = [[] for _ in range(N+1)] for start, end in arr: graph[start].append(end) gr..
[Graph, DFS] BOJ 11724 연결 요소의 개수
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 import sys from collections import deque input = sys.stdin.readline N, M = map(int, input().split()) arr = [list(map(int, input().split())) for _ in range(M)] graph = [[] for _ in range(N+1)] visited = [0] * (N+1) # 무방향 그래프 만들기 for start, end in arr: graph[start].append(end) graph[end].append(start..
그래프 이론 요약 정리
그래프란? 그래프란 정점(Edge)과 간선(Vertex/Node)으로 이루어진 자료구조를 의미한다. 그림으로 나타내자면 다음과 같다. 차수(degree)는 간선으로 연결된 이웃한 정점의 개수를 의미한다. 그래프는 특징에 따라서 여러 종류로 구분할 수 있다. 1. 방향성 그래프에는 간선에 방향성이 존재하느냐 존재하지 않느냐에 따라서 무방향 그래프(Undirected Graph)와 방향 그래프(Directed Graph)로 나뉜다. 2. 사이클 그래프안에 사이클이 존재하느냐 존재하느냐에 따라서 순환 그래프(Cyclic Graph)와 비순환 그래프(Acyclic Graph)로 나눌 수 있다. 이때의 사이클이란 임의의 한점에서 출발했을 때 다시 자기 자신으로 돌아오는 경로가 있을 때 이를 사이클이 존재한다고 한..