ayeongjin 님의 블로그

벨만-포드 알고리즘 (Bellman-Ford Algorithm) 1. 벨만-포드 알고리즘이란? 벨만-포드 알고리즘(Bellman-Ford Algorithm) 은 하나의 시작 정점(source) 으로부터 모든 정점까지의 최단 거리를 구하는 알고리즘이다.다익스트라 알고리즘과 비슷한 목적을 가지지만, 다익스트라에서는 불가능한 음수 가중치(negative weight) 를 허용한다.따라서, 음의 간선(negative edge) 이 존재하는 그래프에서 최단 경로를 구할 때 매우 유용하다. 2. 알고리즘의 핵심 아이디어 벨만-포드는 모든 간선을 반복적으로 완화(Relaxation) 하는 알고리즘이다.Relaxation (완화):어떤 경로를 통해 더 짧은 거리로 도달할 수 있다면, 그 거리 값을 갱신하는 과정 즉,..

https://school.programmers.co.kr/learn/courses/30/lessons/72413 프로그래머스SW개발자를 위한 평가, 교육의 Total Solution을 제공하는 개발자 성장을 위한 베이스캠프programmers.co.kr 문제 조건1. A의 이동경로 : s -> b, B의 이동경로 : s -> b2. 두 사람의 경유지가 같을 경우 같은 택시를 타며, 요금은 한 번만 지불3. 두 사람의 총 택시 요금의 최소값 출력 접근 방식일단 A와 B의 공통 경유지를 생각하자마자 플로이드 워셜로 풀어야겠다고 생각했다. 플로이드 워셜 코드 구현1. 그래프 초기화dist = [[float('inf')] * (n + 1) for _ in range(n + 1)]for i in range(1,..

https://www.acmicpc.net/problem/24042 횡단보도 프로젝트를 진행하면서 이런식으로 알고리즘을 짜면 좋겠다 싶은 생각을 했는데 비슷한 문제가 있어서 풀어봤다. 문제 조건1. 교차로의 구역 : N개2. 주어진 횡단보도의 전체 주기 : M분 (M개의 연결 노드, 1분간격으로 바뀜)3. 0분에 출발해서 1번 구역에서 N번 구역까지 이동하는 최소 시간 구하기 접근 방식일단 다른 다익스트라랑 똑같이 풀되, 가중치 계산이 따로 필요하다고 생각했다.현재 시간, 현재 노드에서 이동할 수 있는 다른 연결 노드 중, 언제 출발할 수 있는지 (신호등이 언제 켜지는지) 계산이 필요했다. 알아야할 값1. 연결된 노드 중 신호등이 켜지는 시간 (기다리는 시간)2. 1에서 구한 기다리는 시간에서 현재시간..

https://www.acmicpc.net/problem/1504 처음엔 함수 없이 1 -> N 까지 다익스트라로 최단경로를 찾고, 그 과정에서 경유지 두개가 포함되는 경우에만  result 갱신하는 방법으로 풀려고 했다.근데 경유지 안지나가고 최단경로를 찾았을 때 다른 경로를 찾지 않아서 코드 완성 못하고 끝냈다.그래서 경유지를 사이에 끼워서 1 -> 경유지1 -> 경유지2 -> N / 1 -> 경유지2 -> 경유지1 -> N 이 두가지 경우를 따로따로 구하고 더 작은 값을 출력하도록 했다. # 성공 코드from heapq import heappush, heappopN, E = map(int, input().split()) # 정점 수, 간선 수adjl = [[] for _ in range(N+1)]f..

https://www.acmicpc.net/problem/11909  처음에 문제만 보고 그냥 다익스트라로 푸는 문제인줄알았는데 계속 시간초과났다. 1. (0, 0)부터 시작 -> 이미 더 빠르게 지나온 기록이 있으면 continue2. 현재 칸이 다음 칸보다 작으면 버튼 올려서 칸 맞춰주기3. 최솟값 갱신 # 실패 코드# 다익스트라 - 시간초과from heapq import heappop, heappush# 1. A[a][b] > A[c][d]# 2. 1 visited[r][c]: continue for di, dj in [(1, 0), (0, 1)]: nr, nc = r + di, c + dj if not (0 arr[nr][nc]: ..