플로이드워셜

배달 (플로이드 워셜)

https://school.programmers.co.kr/learn/courses/30/lessons/12978 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 분석 https://karla.tistory.com/29 [11404번] 가장 빠른 버스 노선 구하기(그래프, 최단거리 , 플로이드) 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 karla.tistory.com 풀이 import sys def..

회장뽑기 (플로이드 워셜)

분석 [1389] 케빈 베이컨의 6단계 법칙 (플로이드-워셜) 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루 karla.tistory.com 풀이 """ 회원사이에 서로 모르는 사람도 있지만, 몇 사람을 통하면 서로 모두 알 수 있 다. 각 회원은 다른 회원들과 가까운 정도에 따라 점수를 받게 된다. 예를 들어 어느 회원이 다른 모든 회원과 친구이면, 이 회원의 점수는 1점이다. 어느 회원의 점수가 2점이면, 다른 모든 회원이 친구이거나, 친구의 친구임을 말한다. 또한, 어느 회원의 점수가 3점이면, 다른 모든 회원이 친구..

플로이드 워셜 알고리즘

분석 [11403] 경로 찾기 (플로이드-워셜) 11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 분석 최단거리를 구하 karla.tistory.com 풀이 """ N개의 도시가 주어지고, 각 도시들을 연결하는 도로와 해당 도로를 통행하는 비용이 주어질 때 모든 도시에서 모든 도시로 이동하는데 쓰이는 비용의 최소값 첫 번째 줄에는 도시의 수N(N

[11403] 경로 찾기 (플로이드-워셜)

11403번: 경로 찾기 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오. www.acmicpc.net 분석 최단거리를 구하는 문제가 아니기 때문에 플로이드-워셜 알고리즘에서 업데이트 부분 수정 S와 E가 모든 중간 경로(K) 중 1개라도 연결되어 있다면 S와 E는 연결 노드로 저장 풀이 """ 모든 정점 (i,j) i에서 j로 가는 경로가 있는지 없는지 i에서 j로 가는 경로가 있으면 i번째 줄의 j번째 숫자를 1로, 없으면 0으로 출력 """ import sys # 인접행렬 크기 n = int(input()) # 인접행렬 d = array = [[sys.maxsize for j in range(n)] f..

[1389] 케빈 베이컨의 6단계 법칙 (플로이드-워셜)

1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻 www.acmicpc.net 분석 2023.03.21 - [Algorithm/Graph] - [11404번] 가장 빠른 버스 노선 구하기(그래프, 최단거리 , 플로이드) 풀이 """ 임의의 두 사람이 최소 몇 단계 만에 이어질 수 있는지 계산 케빈 베이컨의 수가 가장 작은 사람 구하기 유저수 N(2~100), 친구관계수 M(1~5,000) 친구 관계는 중복되어 들어올 수도 있으며, 친구가 한 명도 없는 사람은 없다 """ import sys ..

[11404번] 가장 빠른 버스 노선 구하기(그래프, 최단거리 , 플로이드)

11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 플로이드-워셜 시작점 X 모든 노드간에 최단 경로 탐색 시간복잡도 O(V³) 안좋음 ➡️ 노드의 개수 100~200까지 사용 가능 문제 유형 시작점이 없고 모든 도시간의 최단거리, 모든 도시 100개 이하 점화식 D[S][E] = Math.min(D[S][E], D[S][K] + D[K][E]) 원리 리스트를 선언하고 초기화하기 최단 거리 리스트에 그래프 데이터 저장하기 점화식으로 리스트 업데이트하기 더보기 [Step 1] 1번 노드를 거쳐 가는 경우를 고려하여 ..