다익스트라 알고리즘 검색 결과
4 개의 검색 결과가 있습니다.
알고리즘 문제풀이[Algorithm]

[백준] 1238번 파티(다익스트라 알고리즘)(Python - 파이썬)

백준 1238번 문제입니다. (solved.ac)기준 골드 3 문제입니다. 문제 접근 n개의 숫자로 구분된 각각의 마을(노드)에 한 명의 학생이 살고 있습니다.m개의 단 방향 도로(간선)가 있고 x번 마을에 모여서 파티를 한다고 합니다. 학생들이 x번 마을에 갔다가 다시 돌아오는 최단 경로 중 가장 오래 걸리는 학생의 소요시간을 출력하면 됩니다. 최단 경로를 구해야하는 문제라서 다익스트라 알고리즘을 사용하여 접근하였습니다. start라는 리스트를 만들어서 start[4]라면 4번째 마을에서 다른 모든 노드로 향하는 최단 경로를 저장하도록 하였습니다. ex) 2번 마을에서 x번 마을로 갔다가 돌아오는 최단 경로는 start[2][x] + start[x][2] 입니다. start[2][x]는 2번 마을에서 ..

2022. 3. 1. 10:36
알고리즘 문제풀이[Algorithm]

[백준] 4485번 녹색 옷 입은 애가 젤다지?(다익스트라 알고리즘)(Python - 파이썬)

백준 4485번 문제입니다. (solved.ac)기준 골드 4 문제입니다. 문제 접근 링크는 잃는 비용을 최소로 만들어 동굴을 탈출해야합니다. ([0][0] 부터 [n-1][n-1]까지 이동) 잃는 비용을 경로의 길이라고 생각하고 최단 경로를 찾는 방식으로 접근하였습니다. graph 에 이차원 리스트로 동굴 정보를 입력받고 최단 경로 또한 이차원 리스트에 INF( int(1e9) ) 로 초기화 해줍니다. 그 후 상,하,좌,우 탐색하면서 각 distance에 최단 경로(잃는 루피의 최소 금액)을 갱신하여 주면 됩니다. 예를 들어 distance[3][3]은 0,0부터 3,3으로 가는 최단 경로가 저장 됩니다. 0,0에서 시작하기 때문에 distance[0][0]의 값은 graph[0][0]으로 초기화 해줍..

2022. 2. 28. 15:41
알고리즘 문제풀이[Algorithm]

[백준] 1504번 특정한 최단 경로(다익스트라 알고리즘)(Python - 파이썬)

백준 1504번 문제입니다. (solved.ac)기준 골드 4 문제입니다. https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 문제 접근 두 정점을 반드시 지나는 최단 경로의 길이를 출력해야하는 문제입니다. 다익스트라 알고리즘은 출발노드에서 다른 모든 노드까지의 최소거리를 구하는 알고리즘이기 때문에 다익스트라 알고리즘을 이용하여 1 -> v1 -> v2 -> n 혹은 1 -> v2 -> v1 -> n 두..

2022. 2. 27. 12:39
알고리즘 문제풀이[Algorithm]

[백준] 1916번 최소비용 구하기(다익스트라 알고리즘)(Python - 파이썬)

백준 1916번 문제입니다. (solved.ac)기준 골드 5 문제입니다. 문제 접근 [백준] 1753번 최단경로(다익스트라 알고리즘)(Python) 위의 문제와 마찬가지로 다익스트라 알고리즘으로 간단하게 최소 비용을 구할 수 있는 문제입니다. 위의 문제와 다른 점은 1916번 문제는 노드의 수(N)가 최대 1,000개이기 때문에 이 문제는 우선순위 큐를 사용하지 않는, 시간복잡도가 O(N^2)인 간단한 다익스트라 알고리즘은로도 문제를 해결할 수 있습니다. 간단한 다익스트라 알고리즘은 1. 출발 노드(start)를 설정 2. 최단 거리 테이블(distance)을 int(1e9)로 설정(노드 수 만큼) 3. 방문하지 않은 노드(visited = False) 중 최단 거리(distance)가 가장 짧은 노드..

2022. 2. 23. 16:20