문제n(2 100)개의 도시가 있다. 한 도시에서 출발해 다른 도시에 도착하는 m개의 버스가 있다. 한 번 사용할 때 필요한 비용이 있다. 모든 도시의 쌍 (A, B)에 관해 가는데 필요한 비용의 최솟값을 구하는 프로그램n 플로이드 워셜 코드import sysinput = sys.stdin.readlinen = int(input())m = int(input())# 인접 행렬로 선언graph = [ [float('inf')] * (n+1) for _ in range(n+1)]# 자기 자신으로 가는 경로는 0으로 설정for i in range(1, n+1): graph[i][i] = 0for i in range(m): start, end, weight = map(int, input().split..

08-6 플로이드-워셜기능: 모든 노드 간에 최단 경로 탐색 (시작점 x)특징- 음수 가중치 에지가 있어도 수행할 수 있음 (음수 사이클은 있으면 안됨)- 동적 계획법의 원리를 이용해서 알고리즘에 접근시간 복잡도: O(v^3) -> 노드의 개수가 1000 이런식이면 쓰면 안됨 핵심 이론A 노드에서 B 노드까지 최단 경로를 구했다면, 그 경로위에 K노드가 존재했을 때 그 부분 경로 역시 최단 거리임전체의 최단 거리는 부분의 최단 거리의 합과 같음D[s][e] = Math.min(D[s][e], D[s][k] + D[k][e] 1. 리스트를 선언하고 초기화하기인접행렬로 선언 가능 (노드의 개수가 적을테니) 2. 최단 거리 리스트에 그래프 데이터 저장하기 3. 점화식으로 리스트 업데이트하기점화식을 3중 for..

https://www.acmicpc.net/problem/11657문제N개의 도시와 한 도시에서 출발해 도착하는 버스가 M개 있다. A는 시작 도시, B는 도착 도시, C는 버스를 타고 이동하는 데 걸리는 시간C가 양수가 아닐 때도 있음. 1번 도시에서 출발해 나머지 도시로 가는 가장 빠른 시간을 구하기 최단거리1. 다익스트라2. 벨만 포드 -> 음수 간선이 있음3. 플로이드 워셜 코드import sysinput = sys.stdin.readlinen, e = map(int, input().split())# 에지 리스트로 그래프 구현graph = []for i in range(e): u, v, w = map(int, input().split()) graph.append((u,v,w)) #..

https://www.youtube.com/watch?v=061eXyAFRuI&t=8s 08-5 벨만 포드기능: 특정 출발 노드에서 다른 모든 노드까지의 최단 경로 검색 (다익스트라와 같음)특징- 음수 가중치 에지가 있어도 수행할 수 있음- 전체 그래프에서 음수 사이클의 존재 여부를 판단할 수 있음시간 복잡도: O(VE) 핵심이론1. 에지 리스트로 그래프 구현하고 최단 경로 리스트 초기화하기에지 리스트: 에지 클래스는 노드 변수 2개(start, end)와 가중치 변수로 구성 최단 경로 리스트 - 출발노드는 0, 나머지는 무한대graph = []for _ in range(e): u, v, w = map(int, input().split()) graph.append((u, v, w)) 2. 모든 에지..

문제에지의 가중치가 10이하의 자연수인 방향 그래프가 있다. 이 그래프의 시작점에서 다른 모든 노드로의 최단 경로를 구하시오. 시작점과 다른 노드와 관련된 최단 거리를 묻는 문제 풀이 방법1. 다익스트라 (에지가 양수일때)2. 벨만 포드  코드import heapqimport sys input = sys.stdin.readlinen, e = map(int, input().split())start = int(input())graph = [[] for _ in range(v+1)]# 인접리스트로 그래프 구현for _ in range(e): u, v, w = map(int, input().split()) graph[u].append((v, w))# 거리 리스트 초기화dist = [float('inf..

https://school.programmers.co.kr/learn/courses/30/lessons/42587?language=python3 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 코드from collections import dequedef solution(priorities, location): queue = deque([(priority, idx) for idx, priority in enumerate(priorities)]) cnt = 0 while queue: curr_process = queue.pop..

https://school.programmers.co.kr/learn/courses/30/lessons/340213?language=python3 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr  내 코드def minute_to_sec(time): minute, sec = map(int, time.split(':')) return sec + (minute * 60)def sec_to_minute(time): minute = str(time // 60).zfill(2) sec = str(time % 60).zfill(2) ret..

프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr dfs로 풀어야겠다는 생각은 바로 들었는데 인접리스트랑 dfs 구현 중 자잘한게 생각이 안나서 생각보다 풀이시간이 많이 걸렸다. 내 코드def dfs(graph, start, visited): visited.append(start) for node in graph[start]: if node not in visited: dfs(graph, node, visited) return visited def solution(n, compu..