플로이드 워셜 주의해야할 점(k > i > j 순서로 돌기)

2224번: 명제 증명 명제가 주어질때 참으로 가능한 명제들을 모두 출력하는 문제 p => p같은 전건과 후건이 같은 명제는 출력하지 말고 삼단논법에 의해서만 참이 될 수 있는 명제만 출력하는 문제 전건 후건으로 가능한 것은 알파벳 대소문자이고 총 52개여서 이를 노드 번호로 바꿔주고 from sys import stdinn = int(stdin.readline())node = {chr(i+65):i for i in range(26)}for i in range(26,52): node[chr(i+71)] = ichange = {v:k for k,v in node.items()}  A => b,  b => C이면 A노드에서 b노드로 갈 수 있다는 의미이고, b노드에서 C노드로 갈 수 있다는 의미..

• format_list_bulleted 알고리즘/최단거리 알고리즘
• · 2025. 1. 11.
• textsms

플로이드 워셜로 구하는 그래프의 사이클의 길이

1956번: 운동   시작점에서 다시 시작점으로 돌아오는 사이클을 찾고자 하는데, 이때 길이 합이 가장 작은 사이클을 찾는 문제 사이클을 찾아야하나?  dfs로 돌려서 사이클 찾고 해야하나.. 생각했는데 꼭짓점이 최대 400개이기도 하고 플로이드 워셜로 i번에서 시작해서 i번으로 돌아오는 최단 거리 dp[i][i]를 구하면 될것 같다 사이클이라는게 결국 i번에서 시작해서 i번으로 돌아오는거니까 일반적인 경우와 다르게 dp[i][i] = 0으로 하지말고 dp[i][i] = INF로 초기화함  꼭짓점이 1~V번이니까 1번부터 V번 돌아야하는거 실수하지말고 마지막에 dp[i][i]돌아서 최솟값을 찾으면 그것이 길이가 최소인 사이클의 길이 answer = INF로 변화없으면 사이클이 없는거고 from sys i..

• format_list_bulleted 알고리즘/최단거리 알고리즘
• · 2025. 1. 5.
• textsms

특정 위치까지는 함께 이동하고 나머지는 따로 이동할 때 최단거리 구하기

코딩테스트 연습 - 합승 택시 요금 | 프로그래머스 스쿨 (programmers.co.kr) 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr A,B가 s에서 출발하는데 어떤 위치까지는 함께 갈 수 있고 그러다가 각자 도착 위치 a,b로 간다고 한다면... 최소 요금은 얼마인가 물론 함께가지 않아도 최소라면 그래도 된다 복잡하게 생각하면 상당히 어렵다.. 어디까지 함께 가야하나?.. 함께 가는 거리가 최소여야하나??... 함께 가는 거리가 최소더라도.. 나머지 A,B까지 가는 거리는 최소로 해야하나???... 함께 가는 거리가 최소가 아니더라도.. 나머지 A..

• format_list_bulleted 알고리즘/최단거리 알고리즘
• · 2024. 3. 16.
• textsms

python 시간을 줄이는 테크닉 - min,max를 남발하지 말자(플로이드 워셜에서 주의하기)

16958번: 텔레포트 (acmicpc.net) 16958번: 텔레포트 2차원 평면 위에 N개의 도시가 있다. 일부 도시는 특별한 도시이다. (r1, c1)에 있는 도시에서 (r2, c2)에 있는 도시로 가는 이동 시간은 |r1 - r2| + |c1 - c2|와 같다. 만약, 두 도시가 특별한 도시라면, 텔 www.acmicpc.net 이 문제에서 다음과 같이 제출하면.. 시간 초과로 통과하지 못한다 from sys import stdin INF = 1e9 def floyd(graph,city): for k in range(1,n+1): for a in range(1,n+1): if k == a: continue for b in range(1,n+1): if a == b: continue graph[a]..

• format_list_bulleted 알고리즘/최단거리 알고리즘
• · 2023. 8. 14.
• textsms

최단거리가 k의 배수가 되는 경로를 찾는 다익스트라 알고리즘

1. 문제 28131번: K-지폐 (acmicpc.net) 28131번: K-지폐 첫째 줄에 $N$, $M$, $K$가 주어진다. $(2\leq N\leq 10\,000; 1\leq M\leq \min\left(100\,000, N(N-1)\right); 1\leq K\leq 50)$ 둘째 줄에 $S$와 $T$가 공백으로 구분되어 주어진다. $(1\leq S,T\leq N;S\neq T)$ 셋째 줄부터 $M$개의 www.acmicpc.net 2. 풀이 문제 자체는 간단하다 s에서 t로 이동하는데 가중치의 합이 k의 배수가 되는 최단 경로를 찾는 문제 어떤 수가 k의 배수라는 것은, k로 나눈 나머지가 0이라는 사실을 이용해서 찾는다. D[i][j]를 s에서 출발해서 i 정점으로 가는 경로의 가중치 합을 ..

• format_list_bulleted 알고리즘/최단거리 알고리즘
• · 2023. 8. 2.
• textsms

우선순위가 2개 이상인 다익스트라 알고리즘 연습

1. 문제1 16167번: A Great Way (acmicpc.net) 16167번: A Great Way 첫 번째 줄에 거점의 수 N과 경로의 개수 R이 주어진다. (2 ≤ N ≤ 100, 1 ≤ R ≤ 200) 모든 거점에는 1부터 N까지 번호가 매겨져 있으며 중앙대학교는 1번, 숭실대학교는 N번이다. 두 번째 줄부터는 R www.acmicpc.net 2. 풀이 다익스트라 알고리즘으로 최단거리만을 요구하는 문제가 기본문제고, 최단거리면서, 그러한 거리가 여러개인 경우 거쳐가는 노드가 최소가 되는 경로를 찾으라고 한다면? 접근 방법은 distance 배열 설정을 조금만 바꿔주면 된다 distance[v]를 출발점에서 v까지 가는데 가는 [비용, 거친 노드 수]로 정의해주자 "비용이 먼저 최소가 되면서..

• format_list_bulleted 알고리즘/최단거리 알고리즘
• · 2023. 7. 18.
• textsms