전체 글

[백준2610&파이썬] 플로이드-와샬과 유니온파인드를 함께 이용해보자.

# 문제 백준 2610 회의준비 파이썬 풀이 2610번: 회의준비 첫째 중에 회의에 참석하는 사람의 수 N이 주어진다. 참석자들은 1부터 N까지의 자연수로 표현되며 회의에 참석하는 인원은 100 이하이다. 둘째 줄에는 서로 알고 있는 관계의 수 M이 주어진다. 이 www.acmicpc.net # 코드 ''' - 플로이드-와샬을 이용해서 다른 노드까지의 방문의 합이 최소인 노드를 대표로노드로 선정한다 - 근데 같은 집단(위원회)인건 어떻게 구별해야하나? - 보통 집단을 찾는건 BFS를 활용하기는 하는데.. OR UNION - FIND - 일단 못가는 곳은 INF로 표현 되긴 함 - 유니온 파인드로 구분하는 전처리 과정을 거치자 https://eun-jeong.tistory.com/15 ''' import ..

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