알고리즘

[c++] 백준 11657 풀이 ( 타임머신, 최단경로, 벨만-포드, 음수 가중치 )

우선 이 문제를 풀기위해서는 벨만-포드 알고리즘을 이해해야한다. 벨만-포드 단일시작점 알고리즘 (출발 노드가 고정) 최단 경로 알고리즘 음수 간선 가능 음수 사이클 확인 가능 쓱 보면 다익스트라와 비슷해보인다.(https://guccin.tistory.com/112?category=977502) 그러나 다익스트라와 달리 벨만-포드 알고리즘은 음수 간선에 대해서 최단거리를 알아낼수 있다. 또한 다익스트라는 우선순위 큐를 활용하여 최단 경로를 구하는데에 반해 벨만-포드는 매번 모든 간선을 전부 확인하며 최단거리를 알아내기 때문에 다익스트라보다 시간복잡도가 크다. 다익스트라 O(|E||log|V|), 벨만-포드 O(|E||V|) [c++] 백준 1753 풀이 ( 최단 경로, 다익스트라, 그래프, 우선순위 ) ..

백준 7562 python 풀이 (나이트의 이동, BFS, 그래프)

문제는 나이트가 위와 같이 움직일 수 있을때 몇번 움직이면 원하는 목적지에 도달하는지 구하는 문제이다. 이전에 BFS문제와 아주 유사하다. 다만 그전에는 한칸씩 상하좌우로 움직였지만 이번에는 좀더 여러방면으로 움직이는 차이가 있다. 이때 가장 적은 움직임의 수를 구해야 하기 때문에 DFS가 아닌 BFS로 풀면 된다. 1. BFS를 구현 2. 좌표의 움직임을 구현 3. 이미 움직이거나 움직일 곳은 표시하여 중복을 제거 이를 토대로 코드를 구현하면 아래와 같다. from collections import deque T = int(input()) def BFS(l, start, end): M = [[0 for i in range(l)] for i in range(l)] M[start[0]][start[1]] ..