Most Muscular Most Muscular

기출: 백준 #2665 from heapq import heappush, heappop INF = int(1e9) dx = [1,-1,0,0] dy = [0,0,1,-1] n = int(input()) distance = [[INF for _ in range(n)] for __ in range(n)] distance[0][0] = 0 visited = [[False for _ in range(n)] for __ in range(n)] graph = list() for _ in range(n): graph.append(input()) queue = list() heappush(queue, (0,(0,0))) while queue: curVal, cur = heappop(queue) if distance[c..

기출 : 백준 #9205 from collections import deque INF = int(1e9) t = int(input()) def calcDist(st, en): dist = abs(st[0]-en[0]) + abs(st[1]-en[1]) if dist>1000: return INF return dist for _ in range(t): n = int(input()) node = [] graph = [[INF for _ in range(n+2)] for __ in range(n+2)] home = list(map(int,input().split())) node.append(home) for i in range(n): node.append(list(map(int,input().split()))..

기출 : 백준 #1389 INF = int(1e9) n, m = map(int,input().split()) graph = [[] for _ in range(n+1)] distance = [INF for _ in range(n+1)] answerArr = [0 for _ in range(n+1)] answerVal = INF answer = 0 for _ in range(m): a, b = map(int,input().split()) graph[a].append([1, b]) graph[b].append([1, a]) def dijkstra(start): distance[start] = 0 queue = [[0,start]] while queue: curVal, cur = queue.pop(0) if d..

기출 : 백준 #1261 from heapq import heappush, heappop INF = int(1e9) dx, dy = [1,-1,0,0], [0,0,1,-1] m, n = map(int,input().split()) board = list() for _ in range(n): board.append(list(input())) distance = [[INF for __ in range(m)] for _ in range(n)] distance[0][0] = 0 queue = list() heappush(queue, (0,[0,0])) while queue: curVal, cur = heappop(queue) curX, curY = cur # 이미 계산한 경우 if distance[curX][c..

기출 : 백준 #1504 1 -> v1 -> v2 -> n 1 -> v2 -> v1 -> n 위의 두 가지 경로를 고려하여 최솟값을 출력하면 된다 from heapq import heappop, heappush INF = int(1e9) n, e = map(int,input().split()) graph = [[]for _ in range(n+1)] queue = list() for _ in range(e): x,y,w = map(int,input().split()) graph[x].append((w, y)) graph[y].append((w, x)) v1, v2 = map(int,input().split()) def dijkstra(start, end): distance = [INF for _ in r..

기출 : 백준 #1916 일반적인 다익스트라 문제이다 from heapq import heappush, heappop INF = int(1e9) n = int(input()) m = int(input()) distance = [INF for _ in range(n+1)] graph = [[] for _ in range(n+1)] for _ in range(m): x, y, w = map(int,input().split()) graph[x].append([w,y]) start, end = map(int,input().split()) def djikstra(start): queue = list() distance[start] = 0 heappush(queue, (0,start)) while queue: cu..

기출 : 백준 1753 일반적인 다익스트라 문제다 두 정점 사이에 여러 간선이 있을 수 있다는 점을 고려해야 한다 from heapq import heappush, heappop INF = int(1e9) v, e = map(int, input().split()) k = int(input()) distance = [INF for _ in range(v+1)] minVal = dict() graph = [[] for _ in range(v+1)] queue = list() for _ in range(e): x, y, w = map(int,input().split()) if x not in minVal: minVal[x] = dict() if y not in minVal[x]: minVal[x][y] = w..

다익스트라 알고리즘은 한 노드에서 다른 모든 노드로 향하는 최단 경로를 구하는 것이 목적이다 하지만 이번에 알아볼 플로이드 워셜 알고리즘은 모든 노드에서 모든 노드로 향하는 최단 경로를 구하는 알고리즘이다 알고리즘의 핵심은 노드 N에 대해서 N을 제외한 모든 노드가 N을 거쳐 다른 노드로 이동하는 거리를 갱신하는 것이다 이를 점화식으로 표현하면 Dab = min(Dab,Dak+Dkb)이다 N개의 노드에 대해서 각 단계를 수행하고 각 단계는 (N-1)P2 이므로 시간 복잡도는 O(N^3)이 된다 이를 바탕으로 소스 코드를 작성하면 다음과 같다 #include #define inf 1e9 using namespace std; int n, m; int a, b, c; int graph[100][100]; in..