다익스트라 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 [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 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의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 ... 백준코딩그래프다익스트라파이썬알고리즘개발자개발자 [BOJ]13907 세금 [정답이 아니라 풀이 기록입니다.] 도로간의 통행료가 있고, 모든 도로의 통행료가 K번 Ki씩 오를때 S도시에서 D도시로 가는 최초의 최소비용과 인상후 최소비용은 얼마인가? 도시 간 도로는 양방향 도로입니다. 트리구조가 아니고 도시 사이에 통행료가 두개 존재할 수도 있습니다. 통행료 인상은 모든 도로에 일괄적용 됩니다. 인상된 이후에 최소비용을 다시 구하기엔 시간이 부족합니다. 세금 인상 세... 다익스트라boj백준cppboj 백준 알고리즘 14284번 : 간선 이어가기 2 정점 n개, 0개의 간선으로 이루어진 무방향 그래프가 주어진다. 그리고 m개의 가중치 간선의 정보가 있는 간선리스트가 주어진다. 간선리스트에 있는 간선 하나씩 그래프에 추가해 나갈 것이다. 이때, 특정 정점 s와 t가 연결이 되는 시점에서 간선 추가를 멈출 것이다. 연결이란 두 정점이 간선을 통해 방문 가능한 것을 말한다. s와 t가 연결이 되는 시점의 간선의 가중치의 합이 최소가 되게 추가... 백준 알고리즘다익스트라다익스트라 [BOJ 10282] 해킹 (Java) 문제 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 그로부터 일정 시간 뒤 a도 감염되고 만다. 이때 b가 a를 의존하지 않는다면, a가 감염되더라도 b는 안전하다. 최흉최악의 해커 yum3이 해킹한 컴퓨터 번호와 각 의존성이 주어질 때, 해킹당한... 다익스트라그래프이론그래프이론 백준 알고리즘 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 [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 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의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 ... 백준코딩그래프다익스트라파이썬알고리즘개발자개발자 [BOJ]13907 세금 [정답이 아니라 풀이 기록입니다.] 도로간의 통행료가 있고, 모든 도로의 통행료가 K번 Ki씩 오를때 S도시에서 D도시로 가는 최초의 최소비용과 인상후 최소비용은 얼마인가? 도시 간 도로는 양방향 도로입니다. 트리구조가 아니고 도시 사이에 통행료가 두개 존재할 수도 있습니다. 통행료 인상은 모든 도로에 일괄적용 됩니다. 인상된 이후에 최소비용을 다시 구하기엔 시간이 부족합니다. 세금 인상 세... 다익스트라boj백준cppboj 백준 알고리즘 14284번 : 간선 이어가기 2 정점 n개, 0개의 간선으로 이루어진 무방향 그래프가 주어진다. 그리고 m개의 가중치 간선의 정보가 있는 간선리스트가 주어진다. 간선리스트에 있는 간선 하나씩 그래프에 추가해 나갈 것이다. 이때, 특정 정점 s와 t가 연결이 되는 시점에서 간선 추가를 멈출 것이다. 연결이란 두 정점이 간선을 통해 방문 가능한 것을 말한다. s와 t가 연결이 되는 시점의 간선의 가중치의 합이 최소가 되게 추가... 백준 알고리즘다익스트라다익스트라 [BOJ 10282] 해킹 (Java) 문제 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 그로부터 일정 시간 뒤 a도 감염되고 만다. 이때 b가 a를 의존하지 않는다면, a가 감염되더라도 b는 안전하다. 최흉최악의 해커 yum3이 해킹한 컴퓨터 번호와 각 의존성이 주어질 때, 해킹당한... 다익스트라그래프이론그래프이론 백준 알고리즘 13424번 : 비밀 모임 모임 장소를 정하기 전, 호그와트 비밀지도를 이용해 학교 안에 있는 사람들의 현재 위치를 확인해보니 모임에 참여하는 친구들은 N개의 방 중에서 한군데씩에 각각 위치해 있었다. 어느 방을 모임 장소로 사용할까 고민하던 해리는 모임에 참석하는 친구들의 이동 거리의 총합이 최소가 되는 방을 오늘의 모임 장소로 사용하기로 했다. 만약 오늘 모임의 장소로 2번 방을 이용한다면 3번 방에 있는 친구 A... 플로이드-와샬백준 알고리즘다익스트라다익스트라