Dijkstra 검색 결과
4 개의 검색 결과가 있습니다.
개발/알고리즘

[백준 1238] 파티 (python)

1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 다익스트라 알고리즘을 사용한다. 파티를 갔다가 와야하므로 정방향과 역방향 그래프 두개의 합을 계산해준다. 가는길 goarr, 오는길 comearr에 경로들을 저장한다. 가는데 걸리는 시간을 저장하는 time 배열을 생성한다. queue에 시작점을 넣어준다. 시작점에서 뻗을 수 있는 것들 중 저장되어 있는 것보다 더 작은 경로라면 update해주고 queue에 넣는다. 두 결과값을 더해서 큰값을 구해준다. import sys impo..

2021. 4. 19. 02:03
개발/알고리즘

[백준 10282] 해킹 (python)

10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 다익스트라 알고리즘을 사용하자! arr에 의존 관계를 저장한다. time에는 감염되기 까지 걸리는 시간을 저장한다. (default = sys.maxsize) queue에 시작점 넣고 시작한다. 저장되어있는 감염시간(time[e])과 이전꺼에서 뻗어나가는 감염시간(w+v) 중 작은 것을 저장한다. time배열을 순회하며 sys.maxsize가 아닌 max 값과 개수를 구한다. import sys import heapq input = sys.stdin.readline ..

2021. 4. 19. 01:06
개발/알고리즘

[백준 1446] 지름길 (python)

1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하이고, D는 10,000보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이가 주 www.acmicpc.net 다익스트라 알고리즘을 이용한다. 지름길이 없을때 자기 자신을 default로 가지는 arr 배열을 생성한다. 0부터 목적지까지 돈다. 이전지점+1 이 더 작다면 update해준다. 지름길이 있다면 저장된 길이 (distance[타겟점])와 뻗어나간 길이 (w + distance[시작점]) 중 작은 것으로 update해준다. (지름길 시작지점이 D보다 작다고 해서 arr 배열을 range(D+1)로 했는데 Indexerror가 난다. 왜나는 걸까?) i..

2021. 4. 18. 23:01
개발/알고리즘

[백준 1753] 최단경로 (python)

1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 우선순위큐에 다익스트라 알고리즘을 사용한다 v_arr: 최단경로 저장 arr: 간선 저장 heap: 계산할 것들 저장 heap(우선순위 큐)에 [0, 시작점]을 넣는다. 시작점에 연결되있는 것들을 v_arr와 비교한 뒤에 더 작다면 v_arr를 수정하고, heap에 넣어줌 반복 계산 v_arr 출력 import sys import heapq input = sys.stdin.readline V, E = map(int, input().sp..

2021. 3. 30. 03:00