다익스트라 787. Cheapest Flights Within K Stops There are n cities connected by some number of flights. You are given an array flights where flights[i] = [fromi, toi, pricei] indicates that there is a flight from city fromi to city toi with cost pricei. You are also g... 코딩 테스트다익스트라leetcodeleetcode [백준 13549 파이썬] 숨바꼭질 3 (골드 5, 다익스트라 or BFS) 알고리즘 유형 : 다익스트라 or BFS 다익스트라 풀이 BFS 풀이 SOLVE 1) 풀이 요약 (다익스트라 풀이) 이 문제는 가중치가 0 또는 1인 그래프로 생각할 수 있다. 가중치가 모두 0 또는 양수이고, 특정 노드에서 특정 노드까지의 최단 경로 가중치를 구하는 것이므로 다익스트라 알고리즘을 적용할 수 있다. 기존의 다익스트라 형태에서 조금 다른 점은, 그래프 간선 정보가 따로 주어지는... 파이썬ps알고리즘다익스트라BFS최단 경로백준코딩테스트BFS 다익스트라 파이썬 용도 : 각 정점간 최단경로를 구할 때 공간 복잡도 : v^2 시간 복잡도 " v^3 장단점 소스가 더 간결함 간선 수가 많으면 다익스트라 알고리즘보다 빠를 수 있음 시작점으로부터 각 정점까지 최단거리만 구할때에 보통 다익스트라가 압도적으로 빠름 그래프에 음의 가중치 간선이 있으면 다익스트라 알고리즘은 사용불가 But 플로이드 알고리즘은 사용 가능함 용도 : 시작점으로 부터 나머지 정점까지 ... 알고리즘다익스트라다익스트라 [백준] 1238번: 파티 문제 풀이 파이썬 문제 링크 이번 문제의 태그는 다익스트라, 나에겐 생소한 방식이었기 때문에 다익스트라가 뭔지에 대해 먼저 공부할 필요가 있었다. 다익스트라란? 하나의 정점에서 다른 정점들까지의 최단 거리들을 찾는 최단 경로 알고리즘의 일종이다. 이 때, 힙큐를 함께 사용하여, 해당 정점에서 연결된 정점들 중 거리가 가장 짧은 경로 먼저 계산을 한다. 이렇게 하면 이미 계산딘 경로의 길이보다 더 긴 거리가 있... beakjoon그래프다익스트라백준골드3beakjoon [백준] 1504번: 특정한 최단 경로 문제 풀이 파이썬 문제 링크 풀이 방식 각 노드간의 거리를 양방향 그래프로 저장한다. v1와 v2를 포함하는 1부터 N까지의 경로 두가지를 구한다. 1 > v1 > v2 > N 1 > v2 > v1 > N 이 때, 다익스트라를 이용하여 구하며, 최소 거리를 구하기 위해 힙큐를 활용한다. 두가지 루트의 거리 중 최소값을 구한다. 이 때, 최소 거리가 비정상적으로 크다면 v1 혹은 v2가 없는 것으로 간주한다. ... beakjoon그래프다익스트라골드4백준beakjoon [백준] 1753번: 최단 경로 문제 풀이 파이썬 문제 링크 풀이 방식 기존 다익스트라 문제에서 K번 정점부터 각 노드간의 거리를 출력하는 문제이다. 이 때, 해당 노드와 연결되어있지 않으면 distance 리스트에는 INF(1e9)로 저장되어있기 때문에, 거리가 INF와 같으면 문자열 'INF'로 대체하여 출력한다. 전체 코드... beakjoon그래프다익스트라골드5백준beakjoon BJ1753 최단경로 (다익스트라) 정석적인 다익스트라 알고리즘 문제이다. 다익스트라의 과정은 1. 출발 정점 설정 2. 출발 정점과 연결된 정점들까지의 최소거리 저장 3. 방문하지 않은 정점 중 가장 비용이 적은 정점 선택 4. 해당 정점을 방문처리하고, 그 정점을 거칠 경우, 최소거리 갱신 5. 3~4과정을 모두 방문처리될 때까지 반복 큐를 이용하여 조건이 맞을 때, 큐에 추가해주며 진행하면 된다.... 백준 알고리즘다익스트라다익스트라 [백준] 1916번: 최소비용 구하기 문제 풀이 파이썬 문제 링크 풀이 방식 기존에 사용해왔던 다익스트라 방식을 사용하면 된다. 지금껏 풀어왔던 다익스트라 문제들과 크게 다를것이 없는 문제이다. 전체 코드... beakjoon그래프다익스트라골드5백준beakjoon [백준] 2554 : 미로만들기 BFS와 heap을 사용해서 계속 내가 동서남북으로 이동할 수 있는 좌표 중 최소 비용(벽을 뚫는 횟수)을 가지는 좌표로만 이동하게 하는 것이 핵심! 그때 이미 while heap: 안에서 계속 최소 비용을 가지는 좌표로만 이동해주고 있으므로, visited했던 곳을 또 방문할 필요가 없어진다. visited 방문 기록을 남겨주는 이유가 바로 그것! 방문했던 곳을 방문하지 않게 하려고!! 풀... 다시풀문제그래프다익스트라BFS백준코딩테스트BFS [백준 11779] 최소비용 구하기2 (JAVA) 다익스트라에 경로 역추적까지 해야하는 문제 다익스트라는 인접리스트와 PriorityQueue를 사용하여 구현. 이때 경로 역추적을 위해 현재 도시 기준으로 방문한 이전 도시를 저장해주는 preCity 배열 선언 경로 역추적은 preCity[end]에서부터 stack을 이용하여 역추적한다. 다익스트라 식에서 위에 한줄 안 넣어서 시간초과 났다. 그리고 오랜만에 다익스트라 풀어서인지 식도 잘 기... 알고리즘경로 역추적다익스트라경로 역추적 [BOJ] 9376 - 탈옥 상근이는 감옥에서 죄수 두 명을 탈옥시켜야 한다. 평면도에는 모든 벽과 문이 나타나있고, 탈옥시켜야 하는 죄수의 위치도 나타나 있다. 감옥은 무인 감옥으로 죄수 두 명이 감옥에 있는 유일한 사람이다. 상근이는 특별한 기술을 이용해 제어실을 통하지 않고 문을 열려고 한다. 하지만, 문을 열려면 시간이 매우 많이 걸린다. 두 죄수를 탈옥시키기 위해서 열어야 하는 문의 개수를 구하는 프로그램을 작... 그래프이론코딩공부boj공부노트알고리즘다익스트라boj 백준 - 1719번 택배 접근법 다익스트라로 최단거리를 구하기 위해 ArrayList<Point>[] ADJ 배열을 생성함 배열에 양방향으로 간선 연결을 해줌 2차원 배열로 하게되면, 연결되어있는지 아닌지 n번 탐색을 해야하는데, arrayList면 size만큼만 탐색하면 되니 시간을 아낄 수 있음 각각의 노드를 기준으로 다익스트라 함수를 탐색 path[] 배열로 현재 노드의 앞 노드를 기록해둠 출력 시, 현재 노드... 다익스트라다익스트라 알고리즘 - 다익스트라 자꾸 잊어서 작성.. 하나의 정점에서 모든 정점까지 최소 비용 거리 구하기 ex) 가장 저렴하게 도로놓기, 최단 시간내에 목적지까지 가기 등 다익스트라 흐름 초기상태 0번 노드는 INF가 아니라 0으로 초기화 해도 됨 하나의 정점을 기준으로 설정 0번 노드를 기준 0번 노드를 기준으로 인접해서 갱신한 노드 기준으로 다시 인접 노드 가중치를 탐색 1번 노드를 다시 기준 1번 노드의 인접한 2번... 다익스트라다익스트라 BOJ_2206_G4_벽 부수고 이동하기 문제 링크: 문제 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 만약에 이동하는 도중에 한 개의 ... boj알고리즘다이나믹프로그래밍메모이제이션다익스트라boj [알고리즘] 백준 9370 (파이썬) 처음에 ans list를 밖에다 두어 계산 오류가 계속 났었고 이걸 함수를 호출할 때 마다 copy()를 썻다. 하지만 메모리나 시간적으로 비효율이라 그냥 함수 안에다 넣었다. 그리고 inf가 뽑힐 때도 정답으로 처리해줬는데 이걸 못찾아서 1시간동안 해맸다... 최소거리 -> inf가 뽑힐 수도 있다(연결 node X)는 점을 항상 명심해야겠다.... 최소거리백준알고리즘다익스트라다익스트라 6087 - Java Point클래스를 만들어서 방향과 몇번 꺾었는지를 나타내려고 함 for문 돌때 기존 방향과 다르면 cnt+1, 같으면 그대로 어느 한점까지 갈때 이미 방문을 헀는데 기존보다 덜 꺾어서 갈 수 있는 경우가 있어도 업데이트를 안하는 문제가 있다.... 백준다익스트라다익스트라 [백준 9370 파이썬] 미확인 도착지 (골드2, 다익스트라) 특정 도로를 거치고 가는 최단 거리와, 조건 없이 가는 최단 거리를 비교하여 진위를 가리는 풀이(다익스트라 3번 실행) g-h 도로 길이에 -0.1을 해준 뒤, 목적 교차로 후보까지의 조건없는 최단 거리를 구하고 그 값이 실수형인지 정수형인지로 진위를 따지는 풀이(다익스트라 1번 실행) SOLVE 1) 풀이 요약 (특정 도로를 거치고 가는 최단 거리와, 조건 없이 가는 최단 거리를 비교하여 ... 최단 경로백준알고리즘파이썬코딩테스트ps다익스트라ps [BOJ]5719 거의 최단 경로 s노드에서 e노드로 가는 최단 경로들이 있을때, 이 경로의 간선들을 이용하지 않는 최단 경로를 거의 최단 경로라고 한다. 거의 최단 경로의 길이를 구하여라 최단 경로가 여러개라면 최단 경로들을 이루는 모든 간선을 이용 할 수 없습니다. 거의 최단 경로가 없을 수도 있습니다. 거의 최단 경로도 여러개 있을 수 있습니다. 최단경로, 거의 최단 경로 둘다 없을 수도 있습니다. 최단 거리 구하기 최... 다익스트라백준역추적bojboj [알고리즘] Java / SWEA / 보급로 / 1249 [알고리즘] Java / SWEA / 보급로 / 1249 문제 접근 방식 다익스트라 알고리즘으로 (0,0) 위치에서 (N-1,N-1) 위치의 최단거리를 구한다. 코드... Java다익스트라SWEAJava A)다익스트라(Dijkstra) 알고리즘 다익스트라 알고리즘은, 가중치가 주어지는 그래프, 즉 각 노드마다의 거리가 다른 그래프에서, 각 노드까지로 가는데에 가장 최소한의 시간, 최단 거리를 구하는 알고리즘으로, 구현이 좀 까다롭고 많이 사용되는 알고리즘의 종류다. 그래서 필자는 최소힙 구조를 이용하여, 우선순위 큐를 만들고, 이를 통하여 최단거리를 구하는 알고리즘을 다루려한다. 최단거리, 즉 노드간 거리가 적은 순으로 정렬(최소 ... 백준코딩다익스트라알고리즘개발자개발자 B)1446 지름길 문제 매일 아침, 세준이는 학교에 가기 위해서 차를 타고 D킬로미터 길이의 고속도로를 지난다. 이 고속도로는 심각하게 커브가 많아서 정말 운전하기도 힘들다. 어느 날, 세준이는 이 고속도로에 지름길이 존재한다는 것을 알게 되었다. 모든 지름길은 일방통행이고, 고속도로를 역주행할 수는 없다. 세준이가 운전해야 하는 거리의 최솟값을 출력하시오. 입력 첫째 줄에 지름길의 개수 N과 고속도로... 백준코딩그래프다익스트라알고리즘개발자개발자 B)1697 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 ... 백준코딩그래프다익스트라파이썬알고리즘개발자개발자 백준 알고리즘 14284번 : 간선 이어가기 2 정점 n개, 0개의 간선으로 이루어진 무방향 그래프가 주어진다. 그리고 m개의 가중치 간선의 정보가 있는 간선리스트가 주어진다. 간선리스트에 있는 간선 하나씩 그래프에 추가해 나갈 것이다. 이때, 특정 정점 s와 t가 연결이 되는 시점에서 간선 추가를 멈출 것이다. 연결이란 두 정점이 간선을 통해 방문 가능한 것을 말한다. s와 t가 연결이 되는 시점의 간선의 가중치의 합이 최소가 되게 추가... 백준 알고리즘다익스트라다익스트라 [BOJ 10282] 해킹 (Java) 문제 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 그로부터 일정 시간 뒤 a도 감염되고 만다. 이때 b가 a를 의존하지 않는다면, a가 감염되더라도 b는 안전하다. 최흉최악의 해커 yum3이 해킹한 컴퓨터 번호와 각 의존성이 주어질 때, 해킹당한... 다익스트라그래프이론그래프이론 [프로그래머스/C++] 배달 각 마을은 양방향으로 통행할 수 있는 도로로 연결되어 있는데, 서로 다른 마을 간에 이동할 때는 이 도로를 지나야 합니다. 현재 1번 마을에 있는 음식점에서 각 마을로 음식 배달을 하려고 합니다. 각 마을로부터 음식 주문을 받으려고 하는데, N개의 마을 중에서 K 시간 이하로 배달이 가능한 마을에서만 주문을 받으려고 합니다. 위 그림에서 1번 마을에 있는 음식점은 [1, 2, 4, 5] 번 ... ps프로그래머스programmerscpp다익스트라cpp 백준 알고리즘 13424번 : 비밀 모임 모임 장소를 정하기 전, 호그와트 비밀지도를 이용해 학교 안에 있는 사람들의 현재 위치를 확인해보니 모임에 참여하는 친구들은 N개의 방 중에서 한군데씩에 각각 위치해 있었다. 어느 방을 모임 장소로 사용할까 고민하던 해리는 모임에 참석하는 친구들의 이동 거리의 총합이 최소가 되는 방을 오늘의 모임 장소로 사용하기로 했다. 만약 오늘 모임의 장소로 2번 방을 이용한다면 3번 방에 있는 친구 A... 플로이드-와샬백준 알고리즘다익스트라다익스트라
787. Cheapest Flights Within K Stops There are n cities connected by some number of flights. You are given an array flights where flights[i] = [fromi, toi, pricei] indicates that there is a flight from city fromi to city toi with cost pricei. You are also g... 코딩 테스트다익스트라leetcodeleetcode [백준 13549 파이썬] 숨바꼭질 3 (골드 5, 다익스트라 or BFS) 알고리즘 유형 : 다익스트라 or BFS 다익스트라 풀이 BFS 풀이 SOLVE 1) 풀이 요약 (다익스트라 풀이) 이 문제는 가중치가 0 또는 1인 그래프로 생각할 수 있다. 가중치가 모두 0 또는 양수이고, 특정 노드에서 특정 노드까지의 최단 경로 가중치를 구하는 것이므로 다익스트라 알고리즘을 적용할 수 있다. 기존의 다익스트라 형태에서 조금 다른 점은, 그래프 간선 정보가 따로 주어지는... 파이썬ps알고리즘다익스트라BFS최단 경로백준코딩테스트BFS 다익스트라 파이썬 용도 : 각 정점간 최단경로를 구할 때 공간 복잡도 : v^2 시간 복잡도 " v^3 장단점 소스가 더 간결함 간선 수가 많으면 다익스트라 알고리즘보다 빠를 수 있음 시작점으로부터 각 정점까지 최단거리만 구할때에 보통 다익스트라가 압도적으로 빠름 그래프에 음의 가중치 간선이 있으면 다익스트라 알고리즘은 사용불가 But 플로이드 알고리즘은 사용 가능함 용도 : 시작점으로 부터 나머지 정점까지 ... 알고리즘다익스트라다익스트라 [백준] 1238번: 파티 문제 풀이 파이썬 문제 링크 이번 문제의 태그는 다익스트라, 나에겐 생소한 방식이었기 때문에 다익스트라가 뭔지에 대해 먼저 공부할 필요가 있었다. 다익스트라란? 하나의 정점에서 다른 정점들까지의 최단 거리들을 찾는 최단 경로 알고리즘의 일종이다. 이 때, 힙큐를 함께 사용하여, 해당 정점에서 연결된 정점들 중 거리가 가장 짧은 경로 먼저 계산을 한다. 이렇게 하면 이미 계산딘 경로의 길이보다 더 긴 거리가 있... beakjoon그래프다익스트라백준골드3beakjoon [백준] 1504번: 특정한 최단 경로 문제 풀이 파이썬 문제 링크 풀이 방식 각 노드간의 거리를 양방향 그래프로 저장한다. v1와 v2를 포함하는 1부터 N까지의 경로 두가지를 구한다. 1 > v1 > v2 > N 1 > v2 > v1 > N 이 때, 다익스트라를 이용하여 구하며, 최소 거리를 구하기 위해 힙큐를 활용한다. 두가지 루트의 거리 중 최소값을 구한다. 이 때, 최소 거리가 비정상적으로 크다면 v1 혹은 v2가 없는 것으로 간주한다. ... beakjoon그래프다익스트라골드4백준beakjoon [백준] 1753번: 최단 경로 문제 풀이 파이썬 문제 링크 풀이 방식 기존 다익스트라 문제에서 K번 정점부터 각 노드간의 거리를 출력하는 문제이다. 이 때, 해당 노드와 연결되어있지 않으면 distance 리스트에는 INF(1e9)로 저장되어있기 때문에, 거리가 INF와 같으면 문자열 'INF'로 대체하여 출력한다. 전체 코드... beakjoon그래프다익스트라골드5백준beakjoon BJ1753 최단경로 (다익스트라) 정석적인 다익스트라 알고리즘 문제이다. 다익스트라의 과정은 1. 출발 정점 설정 2. 출발 정점과 연결된 정점들까지의 최소거리 저장 3. 방문하지 않은 정점 중 가장 비용이 적은 정점 선택 4. 해당 정점을 방문처리하고, 그 정점을 거칠 경우, 최소거리 갱신 5. 3~4과정을 모두 방문처리될 때까지 반복 큐를 이용하여 조건이 맞을 때, 큐에 추가해주며 진행하면 된다.... 백준 알고리즘다익스트라다익스트라 [백준] 1916번: 최소비용 구하기 문제 풀이 파이썬 문제 링크 풀이 방식 기존에 사용해왔던 다익스트라 방식을 사용하면 된다. 지금껏 풀어왔던 다익스트라 문제들과 크게 다를것이 없는 문제이다. 전체 코드... beakjoon그래프다익스트라골드5백준beakjoon [백준] 2554 : 미로만들기 BFS와 heap을 사용해서 계속 내가 동서남북으로 이동할 수 있는 좌표 중 최소 비용(벽을 뚫는 횟수)을 가지는 좌표로만 이동하게 하는 것이 핵심! 그때 이미 while heap: 안에서 계속 최소 비용을 가지는 좌표로만 이동해주고 있으므로, visited했던 곳을 또 방문할 필요가 없어진다. visited 방문 기록을 남겨주는 이유가 바로 그것! 방문했던 곳을 방문하지 않게 하려고!! 풀... 다시풀문제그래프다익스트라BFS백준코딩테스트BFS [백준 11779] 최소비용 구하기2 (JAVA) 다익스트라에 경로 역추적까지 해야하는 문제 다익스트라는 인접리스트와 PriorityQueue를 사용하여 구현. 이때 경로 역추적을 위해 현재 도시 기준으로 방문한 이전 도시를 저장해주는 preCity 배열 선언 경로 역추적은 preCity[end]에서부터 stack을 이용하여 역추적한다. 다익스트라 식에서 위에 한줄 안 넣어서 시간초과 났다. 그리고 오랜만에 다익스트라 풀어서인지 식도 잘 기... 알고리즘경로 역추적다익스트라경로 역추적 [BOJ] 9376 - 탈옥 상근이는 감옥에서 죄수 두 명을 탈옥시켜야 한다. 평면도에는 모든 벽과 문이 나타나있고, 탈옥시켜야 하는 죄수의 위치도 나타나 있다. 감옥은 무인 감옥으로 죄수 두 명이 감옥에 있는 유일한 사람이다. 상근이는 특별한 기술을 이용해 제어실을 통하지 않고 문을 열려고 한다. 하지만, 문을 열려면 시간이 매우 많이 걸린다. 두 죄수를 탈옥시키기 위해서 열어야 하는 문의 개수를 구하는 프로그램을 작... 그래프이론코딩공부boj공부노트알고리즘다익스트라boj 백준 - 1719번 택배 접근법 다익스트라로 최단거리를 구하기 위해 ArrayList<Point>[] ADJ 배열을 생성함 배열에 양방향으로 간선 연결을 해줌 2차원 배열로 하게되면, 연결되어있는지 아닌지 n번 탐색을 해야하는데, arrayList면 size만큼만 탐색하면 되니 시간을 아낄 수 있음 각각의 노드를 기준으로 다익스트라 함수를 탐색 path[] 배열로 현재 노드의 앞 노드를 기록해둠 출력 시, 현재 노드... 다익스트라다익스트라 알고리즘 - 다익스트라 자꾸 잊어서 작성.. 하나의 정점에서 모든 정점까지 최소 비용 거리 구하기 ex) 가장 저렴하게 도로놓기, 최단 시간내에 목적지까지 가기 등 다익스트라 흐름 초기상태 0번 노드는 INF가 아니라 0으로 초기화 해도 됨 하나의 정점을 기준으로 설정 0번 노드를 기준 0번 노드를 기준으로 인접해서 갱신한 노드 기준으로 다시 인접 노드 가중치를 탐색 1번 노드를 다시 기준 1번 노드의 인접한 2번... 다익스트라다익스트라 BOJ_2206_G4_벽 부수고 이동하기 문제 링크: 문제 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 당신은 (1, 1)에서 (N, M)의 위치까지 이동하려 하는데, 이때 최단 경로로 이동하려 한다. 최단경로는 맵에서 가장 적은 개수의 칸을 지나는 경로를 말하는데, 이때 시작하는 칸과 끝나는 칸도 포함해서 센다. 만약에 이동하는 도중에 한 개의 ... boj알고리즘다이나믹프로그래밍메모이제이션다익스트라boj [알고리즘] 백준 9370 (파이썬) 처음에 ans list를 밖에다 두어 계산 오류가 계속 났었고 이걸 함수를 호출할 때 마다 copy()를 썻다. 하지만 메모리나 시간적으로 비효율이라 그냥 함수 안에다 넣었다. 그리고 inf가 뽑힐 때도 정답으로 처리해줬는데 이걸 못찾아서 1시간동안 해맸다... 최소거리 -> inf가 뽑힐 수도 있다(연결 node X)는 점을 항상 명심해야겠다.... 최소거리백준알고리즘다익스트라다익스트라 6087 - Java Point클래스를 만들어서 방향과 몇번 꺾었는지를 나타내려고 함 for문 돌때 기존 방향과 다르면 cnt+1, 같으면 그대로 어느 한점까지 갈때 이미 방문을 헀는데 기존보다 덜 꺾어서 갈 수 있는 경우가 있어도 업데이트를 안하는 문제가 있다.... 백준다익스트라다익스트라 [백준 9370 파이썬] 미확인 도착지 (골드2, 다익스트라) 특정 도로를 거치고 가는 최단 거리와, 조건 없이 가는 최단 거리를 비교하여 진위를 가리는 풀이(다익스트라 3번 실행) g-h 도로 길이에 -0.1을 해준 뒤, 목적 교차로 후보까지의 조건없는 최단 거리를 구하고 그 값이 실수형인지 정수형인지로 진위를 따지는 풀이(다익스트라 1번 실행) SOLVE 1) 풀이 요약 (특정 도로를 거치고 가는 최단 거리와, 조건 없이 가는 최단 거리를 비교하여 ... 최단 경로백준알고리즘파이썬코딩테스트ps다익스트라ps [BOJ]5719 거의 최단 경로 s노드에서 e노드로 가는 최단 경로들이 있을때, 이 경로의 간선들을 이용하지 않는 최단 경로를 거의 최단 경로라고 한다. 거의 최단 경로의 길이를 구하여라 최단 경로가 여러개라면 최단 경로들을 이루는 모든 간선을 이용 할 수 없습니다. 거의 최단 경로가 없을 수도 있습니다. 거의 최단 경로도 여러개 있을 수 있습니다. 최단경로, 거의 최단 경로 둘다 없을 수도 있습니다. 최단 거리 구하기 최... 다익스트라백준역추적bojboj [알고리즘] Java / SWEA / 보급로 / 1249 [알고리즘] Java / SWEA / 보급로 / 1249 문제 접근 방식 다익스트라 알고리즘으로 (0,0) 위치에서 (N-1,N-1) 위치의 최단거리를 구한다. 코드... Java다익스트라SWEAJava A)다익스트라(Dijkstra) 알고리즘 다익스트라 알고리즘은, 가중치가 주어지는 그래프, 즉 각 노드마다의 거리가 다른 그래프에서, 각 노드까지로 가는데에 가장 최소한의 시간, 최단 거리를 구하는 알고리즘으로, 구현이 좀 까다롭고 많이 사용되는 알고리즘의 종류다. 그래서 필자는 최소힙 구조를 이용하여, 우선순위 큐를 만들고, 이를 통하여 최단거리를 구하는 알고리즘을 다루려한다. 최단거리, 즉 노드간 거리가 적은 순으로 정렬(최소 ... 백준코딩다익스트라알고리즘개발자개발자 B)1446 지름길 문제 매일 아침, 세준이는 학교에 가기 위해서 차를 타고 D킬로미터 길이의 고속도로를 지난다. 이 고속도로는 심각하게 커브가 많아서 정말 운전하기도 힘들다. 어느 날, 세준이는 이 고속도로에 지름길이 존재한다는 것을 알게 되었다. 모든 지름길은 일방통행이고, 고속도로를 역주행할 수는 없다. 세준이가 운전해야 하는 거리의 최솟값을 출력하시오. 입력 첫째 줄에 지름길의 개수 N과 고속도로... 백준코딩그래프다익스트라알고리즘개발자개발자 B)1697 숨바꼭질 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 ... 백준코딩그래프다익스트라파이썬알고리즘개발자개발자 백준 알고리즘 14284번 : 간선 이어가기 2 정점 n개, 0개의 간선으로 이루어진 무방향 그래프가 주어진다. 그리고 m개의 가중치 간선의 정보가 있는 간선리스트가 주어진다. 간선리스트에 있는 간선 하나씩 그래프에 추가해 나갈 것이다. 이때, 특정 정점 s와 t가 연결이 되는 시점에서 간선 추가를 멈출 것이다. 연결이란 두 정점이 간선을 통해 방문 가능한 것을 말한다. s와 t가 연결이 되는 시점의 간선의 가중치의 합이 최소가 되게 추가... 백준 알고리즘다익스트라다익스트라 [BOJ 10282] 해킹 (Java) 문제 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 그로부터 일정 시간 뒤 a도 감염되고 만다. 이때 b가 a를 의존하지 않는다면, a가 감염되더라도 b는 안전하다. 최흉최악의 해커 yum3이 해킹한 컴퓨터 번호와 각 의존성이 주어질 때, 해킹당한... 다익스트라그래프이론그래프이론 [프로그래머스/C++] 배달 각 마을은 양방향으로 통행할 수 있는 도로로 연결되어 있는데, 서로 다른 마을 간에 이동할 때는 이 도로를 지나야 합니다. 현재 1번 마을에 있는 음식점에서 각 마을로 음식 배달을 하려고 합니다. 각 마을로부터 음식 주문을 받으려고 하는데, N개의 마을 중에서 K 시간 이하로 배달이 가능한 마을에서만 주문을 받으려고 합니다. 위 그림에서 1번 마을에 있는 음식점은 [1, 2, 4, 5] 번 ... ps프로그래머스programmerscpp다익스트라cpp 백준 알고리즘 13424번 : 비밀 모임 모임 장소를 정하기 전, 호그와트 비밀지도를 이용해 학교 안에 있는 사람들의 현재 위치를 확인해보니 모임에 참여하는 친구들은 N개의 방 중에서 한군데씩에 각각 위치해 있었다. 어느 방을 모임 장소로 사용할까 고민하던 해리는 모임에 참석하는 친구들의 이동 거리의 총합이 최소가 되는 방을 오늘의 모임 장소로 사용하기로 했다. 만약 오늘 모임의 장소로 2번 방을 이용한다면 3번 방에 있는 친구 A... 플로이드-와샬백준 알고리즘다익스트라다익스트라