Coding Test/Graph

[1707] 이분 그래프(DFS)

1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 이분그래프 각 집합에 속한 노드끼리 서로 인접하지 않는 두 집합으로 그래프의 노드를 나눌 수 있을 때 분석 싸이클이 발생하지 않으면 탐색을 하면서 다음 노드를 이번 노드와 다른 집합으로 지정 기존의 탐색 메커니즘에서 탐색한 노드에 다시 접근하게 됐을 때 현재 노드의 집합과 같으면 이분 그래프가 불가능 DFS를 실행할 때 현재 노드에서 연결된 노드 중 이미 방문한 노드가 나와 같은 집합이면 이분그래프가 아닌것으로 판별 실행 결과가 이분그래프가 아니면 이후 노드는 ..

[1325] 효율적인 해킹(BFS)

1325번: 효율적인 해킹첫째 줄에, N과 M이 들어온다. N은 10,000보다 작거나 같은 자연수, M은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에 신뢰하는 관계가 A B와 같은 형식으로 들어오며, "A가 B를 신뢰한www.acmicpc.net import sysfrom collections import dequeinput = sys.stdin.readline# 컴퓨터개수, 신례관계개수n,m,=map(int, input().split())# 인접 리스트graph=[[] for _ in range(n+1)]# 정답리스트answer=[0]*(n+1)def bfs(v): queue = deque() queue.append(v) visited[v]=True whi..

[18352] 특정 거리의 도시 찾기(다익스트라・heapq, BFS・deque)

18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 다익스트라 from heapq import heappush, heappop import sys input = sys.stdin.readline # 도시, 거리, 거리정보, 출발노드 n,m,k,x = map(int, input().split()) # 최단거리 리스트 d = [sys.maxsize] * (n+1) # 인접 리스트 graph = [[] for _ in range(n+1)] for ..

[24042번] 횡단보도(다익스트라)

24042번: 횡단보도 당신은 집으로 가는 도중 복잡한 교차로를 만났다! 이 교차로에는 사람이 지나갈 수 있는 $N$ 개의 지역이 있고 그 지역 사이를 잇는 몇 개의 횡단보도가 있다. 모든 지역은 횡단보도를 통해 직, www.acmicpc.net 분석 시간 역행 불가, 이미 지난 가중치로 지나갈 수 없음 ➔ 주기 이전 소요 시간 ≤ 지금 이용하는 시간 값이 될 때까지 M을 여러 번 더하여(곱하여) 사용 풀이 import heapq import sys input = sys.stdin.readline n, m = map(int, input().split()) graph = [[] for _ in range(n+1)] for i in range(m): a, b = map(int, input().split())..

그래프의 표현 및 비교 (간선 리스트, 인접 행렬, 인접 리스트)

간선 리스트 인접 행렬 인접 리스트 중심 간선 노드 노드 시간복잡도 - 느림 빠름 구조 [] d[시작노드][종료노드] d[시작노드] 입력 (시작노드 ,도착노드, 가중치) 가중치 (도착노드, 가중치) 알고리즘 벨만-포드 MST 크루스칼 플로이드-워셜 다익스트라 간선 리스트 Edge list 에지 중심으로 그래프를 표현 리스트에 출발 노드, 도착 노드, 가중치 저장하여 가중치가 있는 에지 표현 벨만-포드, 최소 신장 트리 크루스칼 알고리즘 # 벨만 포드 graph = [] for i in range(m): u, v, w = map(int, input().split()) graph.append((u, v, w)) # 크루스칼 from queue import PriorityQueue q = PriorityQue..

[1197번] 최소 신장 트리(MST, 크루스칼, 프림, 유니온파인드)

1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 최소 신장 트리 간선에 가중치를 고려하여 최소 비용의 Spanning Tree를 선택하는 것 그래프에서 모든 노드를 연결할 때 사용된 에지들의 가중치의 합을 최소로 하는 트리 사이클이 포함되면 가중치의 합이 최소가 될 수 없으므로 사이클을 포함하지 않음 N개의 노드가 있으면 최소 신장 트리를 구성하는 에지의 개수는 항상 N-1 더보기 크루스칼 알고리즘 간선 위주의 알고리즘 시작점을 따로 정하지 않고 최소 비용의 간선..

[11404번] 가장 빠른 버스 노선 구하기(그래프, 최단거리 , 플로이드)

11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 플로이드-워셜 시작점 X 모든 노드간에 최단 경로 탐색 시간복잡도 O(V³) 안좋음 ➡️ 노드의 개수 100~200까지 사용 가능 문제 유형 시작점이 없고 모든 도시간의 최단거리, 모든 도시 100개 이하 점화식 D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E]) 원리 리스트를 선언하고 초기화하기 최단 거리 리스트에 그래프 데이터 저장하기 점화식으로 리스트 업데이트하기 더보기 [Step 1] 1번 노드를 거쳐 가는 경우를 고려하여 ..

그래프 최단거리 알고리즘 정리 및 비교 (다익스트라, 벨만-포드, 플로이드-워셜)

다익스트라 벨만-포드 플로이드-워셜 시작 노드 (시작점) O O X (모든 노드) 음수 간선 X O O 시간 복잡도 O(ElogV) O(EV) O(V³) 1. 다익스트라 출발 노드와 모든 노드 간의 최단 거리 탐색 음수간선 X S 시작점부터 다른 모든 노드로 가는 최단거리 구하는 알고리즘 시간복잡도 : O(ElogV) 문제 유형 음수간선이 없는데 시작점이 있고 최단거리 구하는 문제 원리 최단거리를 구할 노드에서 시작하여 거리가 입력된 노드 중 최단거리가 가장 작은 노드를 돌아가며 선택 노드를 돌아가면서, 더 거리가 나오면 값 갱신하여 저장 더보기 2023.03.15 - [Algorithm/그래프] - [1753번] 최단경로 구하기 (다익스트라, 우선순위큐, 힙) 2023.03.15 - [Algorithm..

[11657번] 타임머신 (그래프, 최단거리, 벨만 포드 알고리즘)

11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 벨만 포드 최단 거리를 구하는 알고리즘 음수간선 OK 전체 그래프에서 음수 사이클의 존재 여부를 판단할 수 있음 O(VE) 기출 음수사이클이 있는 지 체크하는 문제 → 시간여행, 과거, 웜홀 음수간선, 시작점이 있고 최단거리 구하는 문제 과정 에지 리스트로 그래프를 구현하고 최단 경로 리스트 초기화 모든 에지를 확인해 정답 리스트 업데이트 음수 사이클 유무 확인 : 모든 에지를 한 번씩 다시 사용해 업데..

[1854번] k번째 최단경로 구하기

1854번: K번째 최단경로 찾기 첫째 줄에 n, m, k가 주어진다. (1 ≤ n ≤ 1000, 0 ≤ m ≤ 2000000, 1 ≤ k ≤ 100) n과 m은 각각 김 조교가 여행을 고려하고 있는 도시들의 개수와, 도시 간에 존재하는 도로의 수이다. 이어지는 m개의 줄에 www.acmicpc.net 분석 최단 경로를 표현하는 리스트를 k개의 row를 갖는 2차원 리스트의 형태로 변경 기존 다익스트라 로직에서, k번째 노드를 찾기 위해서는 노드를 여러번 사용하기 때문에 visited 로직 삭제 다익스트라 로직 수정 코드 1. 최단 거리 리스트를 1차원이 아닌 k개의 row를 갖는 2차원 리스트로 선언 distance = array = [[INF] * k for _ in range(n+1)] q = [(..