전체 글

[백준1504&파이썬] 다익스트라에서 특정정점을 무조건 방문해야할때, 다익스트라는 시작정점으로부터 최단경로를 보장한다.

# 문제 백준 1504 파이썬 특정한 최단 경로 풀이 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net # 코드 ''' - 임의로 주어진 두 정점을 반드시 통과해야 한다. - 한번 이동했던 정점과 간선도 다시 이용할 수 있다. - 1번 정점부터 N번 정점으로 이동한다. ''' import sys from heapq import * from collections import defaultdict N, E = map(int, sys.stdin.readline().spli..

[백준1261&파이썬] 가중치가 0과1뿐일때는 다익스트라 또는 0-1BFS를 활용할 수 있다.

# 문제 백준 1261 알고스팟 파이썬 풀이 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net # 코드 ''' - (1,1) -> (M,N) 으로 이동해야함 - 무조건 아래랑 오른쪽으로 가는것만 사용해야 하는거 아님? - 벽을 최소개로 부수는거지, 최단으로 이동하는 문제는 아닌거 같다 - 이문제는 0,1(BFS) 가중치 문제로 풀어볼 수 있겠다. - 벽을 최소한으로 부수는거이기 때문에 벽을 부수는데 가중치를 1로 두자 - 0-1bfs와 다익스트라로 풀 수 있을것 같다. ''' import ..

[백준1238&파이썬] 다익스트라를 여러번 사용해서 최장 경로를 얻어보자

# 문제 백준 1238 파티 파이썬 풀이 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net # 코드 ''' - 오고 가야함, X까지 오는건 각각 구하고, X에서 다시 원래 지점까지 가는 방법은 X로 다익스트라 한번만 돌리면 될듯 - total_distance를 하나 만든다 - total_distance는 X에서 N까지의 모든 경로를 미리 구해놓는다 - 이후 N -> X로 가는 최단거리의 값을 구해서 다익스트라를 사용해서 해당 경로에 더해준다. ''' import sys from c..

[백준11779&파이썬] 다익스트라에서 경로 추적이 필요할땐 route배열을 만들어 활용하자

# 문제 백준 11779 파이썬 최소비용 구하기 풀이 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net # 코드 ''' - 경로를 구해야 하기 때문에, 경로가 확정되면 이전에 어디서 왔는지를 distance에 함께 저장하던지, 경로 배열을 만들어서 사용해야 함 - 최소 경로로 가는 법은 한가지 이상일 수 있음, 백준 예제는 하나만 나와서 괜히 뭐 틀린 줄 알고 찾았네.. ''' import sys import heapq from collections import defaultdic..

[백준1753&파이썬] 다익스트라 알고리즘은 한 정점에서 모든 정점까지의 최단거리를 구할 수 있다.

# 문제 백준 1753 최단경로 파이썬 풀이 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net # 코드 ''' 1. 다익스트라는 시작정점으로부터 모든 정점까지의 최단거리를 구할 수 있다 2. 간선(Edge)의 값이 0 이상의 양수일때 정상 작동한다. - 최단 거리 테이블 초기화( 시작 노드 0, 나머지 inf ) - https://www.acmicpc.net/board/view/82405 그래프 초기화 관련 - 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에..