# Shortest Path

26개의 포스트

백준 #11657 타임머신 (파이썬)

전형적인 벨만-포드 알고리즘 문제

4일 전
·
0개의 댓글
post-thumbnail

백준 #1956 운동 (파이썬)

플로이드-워셜에서 대각성분 값을 INF 그대로 두고 시작하면, 끝났을 때 담긴 값은 0이 아니라 사이클 값이 된다~

2022년 6월 5일
·
0개의 댓글

백준 #11404 플로이드 (파이썬)

생각할 것도 없고, 그냥 플로이드-워셜 알고리즘을 쓰기만 하면 통과할 수 있다.

2022년 5월 28일
·
0개의 댓글

[오답노트] 백준 #1238 파티 (파이썬)

그래프 간선 방향을 역으로 바꾸면 생기는 일

2022년 5월 2일
·
0개의 댓글

백준 #11779 최소비용 구하기 2 (파이썬)

아주 전형적인 다익스트라 문제다. 하지만 최단 비용만 출력하는 게 아니라 그때의 경로를 함께 출력해야 하므로 추가 변수가 필요하다.

2022년 4월 6일
·
0개의 댓글

다익스트라, 벨만-포드, 플로이드-워셜 함수 핵심부만 모아보기

위 글이 너무 길어서 구현 부분을 따로 보면서 외우기가 힘드니까 구현부만 발췌한 글을 새로 작성한다. 알고리즘에 대한 설명은 따로 하지 않겠다.

2022년 3월 28일
·
0개의 댓글
post-thumbnail

최단 경로 알고리즘 : 다익스트라 VS 벨만-포드 VS 플로이드-워셜

솔브닥 CLASS 4의 난관이자 코딩테스트를 위해 반드시 넘어야 하는 벽인 최단 경로 알고리즘에 대해 소개한다. 눈으로 보지만 말고, 반드시 직접 파이썬으로 구현해보자!

2022년 3월 27일
·
0개의 댓글
post-thumbnail

[Python] 백준 11265 - 끝나지 않는 파티 문제 풀이

분류: Shortest Path (최단거리), Dijkstra(다익스트라), Floyd-Warshall(플로이드와샬)

2022년 3월 22일
·
0개의 댓글
post-thumbnail

[Python] 백준 1939 - 중량제한 문제 풀이

분류: Shortest Path (최단거리), Binary Search (이분탐색)

2022년 3월 15일
·
0개의 댓글

[오답노트] 백준 #11403 경로 찾기 (파이썬) : 플로이드-워셜

플로이드-와샬 알고리즘 문제 중에 가장 쉬운 문제가 이거 아닐까?

2022년 3월 14일
·
0개의 댓글
post-thumbnail

백준 1956, 운동 - 플로이드-와샬

https://www.acmicpc.net/problem/1956각 도시(노드)에서 출발하여, 해당 도시(노드)로 돌아오는 싸이클의 최소 가중치 합모든 노드 -> 나머지 다른 모든 노드의 최단경로=> 플로이드-와샬 (dist\[i]\[i] = 0 초기화)모든

2022년 3월 11일
·
0개의 댓글
post-thumbnail

백준 11403, 경로 찾기 - 플로이드-와샬

https://www.acmicpc.net/problem/11403모든 정점 -> 다른 모든 정점으로 탐색=> 플로이드-와샬예외처리) 노드 본인에서 출발하여 다시 되돌아오는 싸이클 구성하는지 확인 필요비용 배열 초기화 시, 노드 본인 -> 본인의 비용dist\

2022년 3월 10일
·
0개의 댓글
post-thumbnail

백준 1389, 케빈 베이컨의 6단계 법칙 - 플로이드-와샬

https://www.acmicpc.net/problem/1389케빈 베이컨의 수 = "모든 사람과 케빈 베이컨 게임을 했을 때, 나오는 단계의 합"모든 노드 -> 나머지 모든 노드=> 플로이드-와샬\[i]번 노드의 케빈 베이컨 수 = \[i]행 dist\[i

2022년 3월 10일
·
0개의 댓글
post-thumbnail

백준 2660, 회장 뽑기 - 플로이드-와샬

https://www.acmicpc.net/problem/2660\[i]번 회원의 점수 = 가장 먼 회원과의 거리 (최대 거리)모든 회원(노드) -> 다른 모든 회원(노드)의 거리=> 플로이드-와샬1) 비용 배열 초기화dist\[]\[] 모든 원소 INF로 초

2022년 3월 10일
·
0개의 댓글
post-thumbnail

백준 11404, 플로이드 - 플로이드-와샬

https://www.acmicpc.net/problem/11404플로이드-와샬모든 노드 -> 다른 모든 노드로 갈 때, 최소 비용음의 가중치 가능1) 비용 배열 초기화cost\[i]\[i] = 0, 나머지 cost\[i]\[j] = INFINF = (노드 최

2022년 3월 10일
·
0개의 댓글
post-thumbnail

백준 13549, 숨바꼭질 3 - 다익스트라 / BFS

https://www.acmicpc.net/problem/13549목표 지점을 찾으면 탐색을 종료하는, 일반적인 DFS, BFS는 간선의 가중치가 모두 같아야 함.하지만, 본 문제는 +1, -1 로 가는 경우 가중치가 1,x2 로 가는 경우 가중치가 0 으로

2022년 3월 10일
·
0개의 댓글
post-thumbnail

백준 2665, 미로 만들기 - 다익스트라

https://www.acmicpc.net/problem/2665단순히 시작 지점 \[0]\[0] -> 끝 지점 \[n-1]\[n-1]으로의 최단경로는 BFS로 해결 가능.하지만, 방을 바꾸는 최소 개수에 해당하는 경로는 최단경로가 아닐 수 있음시작 지점으로부

2022년 3월 9일
·
0개의 댓글
post-thumbnail

백준 1504, 특정한 최단경로 - 다익스트라

https://www.acmicpc.net/problem/1504case 1) 1번 노드 -> v1 노드 -> v2 노드 -> n번 노드1번 노드 -> v1 노드 최단경로 다익스트라v1 노드 -> v2 노드 최단경로 다익스트라v2 노드 -> n번 노드 최단경로

2022년 3월 8일
·
0개의 댓글
post-thumbnail

백준 1753, 최단경로 - 다익스트라

https://www.acmicpc.net/problem/1753다익스트라한 노드 -> 다른 모든 노드로의 최단거리음이 아닌 간선의 가중치1) 비용 배열, 우선순위 큐 초기화dist\[]: 시작 노드 거리 0, 나머지 노드 무한대pq: (시작 노드, 0) 추가

2022년 3월 8일
·
0개의 댓글
post-thumbnail

[Python] 백준 1719 - 택배 문제 풀이

분류: Shortest Path (최단거리)

2022년 3월 2일
·
0개의 댓글