분류 전체보기

[백준1613&파이썬] 플로이드 와샬 알고리즘은 모든 노드로부터 특정노드까지의 연결여부를 알 수 있다.

# 문제 백준 1613 역사 파이썬 풀이 1613번: 역사 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. www.acmicpc.net # 코드 import sys n,k = map(int,sys.stdin.readline().split()) # n : 사건의개수, k : 전후 관계의 개수 distance = [ [float('inf')] * (n+1) for _ in range(n+1)] for _ in range(k) : a,b = map(int,sys.stdin.readline().split()) distance[a][b] = 1 for i ..

[백준11404&파이썬] 플로이드-와샬을 이용해서 모든정점에서부터 모든정점까지의 최단거리 구하기

# 문제 백준 11404 플로이드 파이썬 풀이 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net # 코드 ''' - 플로이드-워셜 알고리즘은 모든정점에서부터 모든 정점까지의 최단거리를 구하는 방법 - DISTANCE를 N*N로 만들고, 행이 시작점, 열이 도착점이 된다. - 다익스트라는 그리디 알고리즘 적용, 플로이드 워셜은 다이나믹 프로그래밍이 녹아있음 - 구해야하는 노드의 갯수가 적으면 플로이-워셜을 사용해도 괜찮 - 거쳐가는 노드가 반복문의 중심에 있다. - 거쳐가는 노드를 반복문을 하나씩 시작함. - 다익..

[백준1162&파이썬] 다익스트라에서 distance를 여러가지로 갈래로 분리시켜야 할때

# 문제 백준 1162 도로포장 파이썬 풀이 1162번: 도로포장 첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로가 연결하는 두 도시와 도로를 통과하 www.acmicpc.net # 코드 import sys from collections import defaultdict from heapq import * # N : 도시의 수, M : 도로의 수, K : 포장할 도로의 수 N, M, K = map(int,sys.stdin.readline().split()) graph = defaultdict(list) for _ in range(M) : a,b,w = map..

[백준17835&파이썬] 다익스트라로 역방향 그래프 만들어 특정노드들로부터 가장 가까운 거리 구해 확정하기

# 문제 백준 17835 면접보는 승범이네 파이썬 풀이 17835번: 면접보는 승범이네 첫째 줄에 도시의 수 N(2 ≤ N ≤ 100,000), 도로의 수 M(1 ≤ M ≤ 500,000), 면접장의 수 K(1 ≤ K ≤ N)가 공백을 두고 주어진다. 도시는 1번부터 N번까지의 고유한 번호가 매겨진다. 다음 M개의 줄에 걸쳐 www.acmicpc.net # 코드 import sys from heapq import * from collections import defaultdict # N 도시의 수, M 도로의 수, K 면접장의 수 N, M, K = map(int, sys.stdin.readline().split()) graph =defaultdict(list) for _ in range(M) : u,v,..

[백준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 ..