딥러닝 공부방

1753번 최단경로 www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 문제 파이썬 풀이 다익스트라 알고리즘을 활용하여 최단 경로를 찾습니다. 다익스트라 알고리즘은 1) 모든 가중치가 양수, 2) 방향 그래프 인 경우 활용할 수 있습니다. 가중치가 음수인 경우는 벨만포드 알고리즘을 사용합니다. import sys import collections import heapq sys.setrecursionlimit(10**6) input = ..

다익스트라 알고리즘(Dijkstra Algorithm) 간선 길이가 양의 정수인 그래프에서 최단 거리를 계산 간선 길이를 고려하여 노드에 순위를 매기고자, 일반적인 큐 대신에 우선순위 큐를 사용하는 것을 말고는 BFS와 동일 시간 복잡도는 우선 순위 큐 구현 방법에 달려있다. 이진 히프 O((V+E)logV), 삽입과 삭제 O(logV), 최소값 추출 O(logV) 다익스트라 알고리즘은 시작점s부터 가장 가까운 노드u를 포함하여 그래프를 생성하고, 해당 노드u로 이동합니다. 그래프 밖에 있는 s와 가장 가까운 노드v를 그래프에 포함합니다. 이 과정을 반복합니다. 파이썬 코드 # 다익스트라 알고리즘 # 간선 길이가 양의 정수인 그래프에서 최단 거리를 계산 # 간선 길이를 고려하여 노드에 순위를 매기고자 일..

무방향 그래프에서 사이클 찾기 dfs를 수행하면서, 방문한 정점을 기록합니다. 방문한 정점을 또 방문하면 사이클이 존재합니다. 파이썬 코드 # 2) 무향 그래프에서 순환 판별 # 방문한 정점을 기록하면서, 방문한 정점을 또 방문하면 사이클이 존재 V, E = map(int,input().split()) visited = [0] * (V+1) # 방문한 정점 정보를 담을 stack 생성 graph = [[] for i in range(V+1)] # 빈 인접 리스트 그래프 생성 # 그래프 생성 for i in range(E): a, b = map(int,input().split()) # 간선 정보 받아오기 graph[a].append(b) graph[b].append(a) # dfs 탐색 함수 생성 def ..

9466번 텀 프로젝트 파이썬 풀이 그래프 내에 순환이 존재하면, 순환이 되는 부분 그래프에 속하는 정점이 한 팀을 이루는 문제입니다. 따라서 유향 그래프 내에 (1) 순환을 찾고, (2) 순환에 해당하는 정점들의 수 체크하여 풉니다. import sys sys.setrecursionlimit(10 ** 6) input = sys.stdin.readline K = int(input()) # test 수 def dfs(v): global result visited[v] = 1 # 방문한 정점 기록 traced.append(v) # 탐색 경로 저장 w = graph[v] # 다음 방문할 정점 if visited[w] == 1: # 방문 가능한 곳이 끝났는지 체크 if w in traced: # 탐색 경로에 ..

유향 그래프에서 순환(cyclic) 판별 유향 그래프 내에 back edge가 존재하면, 순환이 존재합니다. dfs와 stack 2개를 활용하여 유향 그래프내에 순환 그래프가 존재하는지 확인할 수 있습니다. 작동 원리 (1) 2개의 stack을 생성합니다. (2) traced 스택에 dfs를 수행하면서 탐색한 경로 노드 를 저장합니다. (3) visited 스택에 방문한 노드들을 저장합니다. visited 스택은 가지치기가 목적입니다.(소요시간 감소). visited 내에 존재하는 노드는 탐색을 진행하지 않기 때문입니다. (4) 탐색을 마친 노드는 traced에서 제거합니다. (5) 만약, traced에 존재하는 노드를 또 방문하면 순환이 존재합니다. 파이썬 코드 stack 대신에 set 자료구조를 사용..

백준 1707번 이분 그래프 www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net 문제 풀이 코드 1) dfs 풀이 import sys sys.setrecursionlimit(10 ** 6) input = sys.stdin.readline # dfs def dfs(v, group): visited[v] = group # 방문한 노드에 group 할당 for i in graph[v]: if visited[i] == 0: # 아직 안 가본 곳이면 방문 i..

이분 그래프 판별(bipartite graph distinction) 무방향 그래프의 이분 그래프를 판별하는 방법은 1) dfs, 2) bfs 두 가지 방법이 존재합니다. dfs 작동 원리 (1) 정점을 방문하면서 각 정점으 1, -1 두 그룹으로 번갈아 지정합니다. (2) 이미 방문했던 정점을 발견할 시에, 현재 정점과의 그룹을 비교하여 동일한 그룹인 경우 False를 반환합니다. bfs 작동 원리 (1) 동일한 level에 존재하는 정점을 같은 그룹으로 지정합니다. (2) 이미 방문한 정점인 경우, 현재 정점과의 그룹과 비교하여 동일한 그룹이면 False를 반환합니다. dfs 코드 # bipartite graph distinction # 1) dfs # 정점을 방문하면서 각 정점을 1, -1 그룹으로..

2150번 Strongly Connected Component www.acmicpc.net/problem/2150 2150번: Strongly Connected Component 첫째 줄에 두 정수 V(1 ≤ V ≤ 10,000), E(1 ≤ E ≤ 100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정 www.acmicpc.net 문제 풀이 import sys sys.setrecursionlimit(10**6) V, E = map(int, input().split()) visited = [0] * (V+1) # visitied 초기화 graph = [[] for i in range(V + 1)] # 빈 ..

코사라주 알고리즘(kosaraju's algorithm) dfs를 활용하여 그래프 내의 ssc를 찾는 알고리즘 시간 복잡도 O(V+E) 정방향 그래프에서 dfs를 실행하여 post가 높은 정점이 sCc의 source가 되고, 역방향 그래프에서 dfs를 실행하여 post가 높은 정점이 scc의 sink가 된다. 찾은 source와 sink를 묶어 scc를 생성한다. 작동 원리 (1) 방향 그래프 내에서 dfs를 실행하여, dfs 탐색을 마친 정점을 stack에 삽입한다. (2) 역방향 그래프를 생성한다. (3) stack에서 정점을 추출하여, 역방향 그래프에서 dfs를 실행한다. (4) 방문하는 정점을 scc 에 삽입한다. (5) 탐색이 종료되면, scc (6) stack에서 방문하지 않은 정점을 추출하여..

2252번 줄 세우기 풀이 학생들의 키 비교 정보로 유향 그래프를 생성합니다. 그리고 위상정렬 알고리즘으로 풀었습니다. import collections v, e = map(int, input().split()) in_degree = [0] * (v+1) graph = [[] for i in range(v+1)] for _ in range(e): a, b = map(int,input().split()) graph[a].append(b) in_degree[b] += 1 result = [] q = collections.deque() for i in range(1, v+1): if in_degree[i] == 0: q.append(i) while q: node = q.popleft() result.appen..