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

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

그래프에서 각 노드의 사이클까지 거리를 빠르게 구하는 놀라운 방법

1. 문제 정확히 하나의 사이클을 포함하는 무방향 연결 그래프(connected undirected graph)가 주어진다. 각 노드 번호가 0부터 n-1까지 n개의 노드를 가진다. 노드 a와 b 사이 거리가 a에서 b로 가기 위해 필요한 최소 간선의 수 노드 i = 0,1,2,..,n-1에서 이 그래프에 존재하는 사이클에 있는 임의의 노드까지의 최소 거리를 구한다면? 당연히 사이클에 포함된 노드는 사이클 까지의 거리가 0이다.   위 그래프는 1,2,3,4가 사이클을 이룬다. 1,2,3,4는 각각 사이클까지 거리가 0이고, 0번 노드는 사이클 까지 거리가 1 5번 노드는 사이클 까지 거리가 1, 6번 노드는 사이클 까지 거리가 2이다.  2. 풀이 사이클에 포함된 노드는  위상정렬에 포함되지 않는다는 ..

• format_list_bulleted 위상정렬
• · 2024. 11. 13.
• textsms

DFS로 사이클 탐지하는 알고리즘 탐구하기2 -사이클의 길이-

1. 연습문제1 9466번: 텀 프로젝트 (acmicpc.net) 문제를 보면 u가 A[u]를 향하는 그래프이고 이 그래프에서 사이클을 모두 찾아 각 사이클에 속하는 노드의 개수를 구하고 전체 노드 수에서 사이클에 속하는 노드의 개수를 빼면 된다 dfs로 사이클을 탐지할 수는 있는데... 사이클에 속하는 노드의 개수는 어떻게 알 수 있을까? 노드 u1부터 u2,u3,...,un을 차례대로 방문한다고 생각해보자 u1 > u2 > u3 > .... > un 그러다가 다시 un에서 u1으로 온다면? u1 > u2 > u3 > ... > un > u1으로 오면 (u1,u2,.u3,...,un)이 하나의 사이클이 된다. 따라서 dfs로 노드를 방문할때마다, 방문한 노드의 번호를 1,2,3,.. 순서대로 매겨준다...

• format_list_bulleted 그래프 이론 정복기
• · 2024. 6. 15.
• textsms

DFS로 사이클 탐지하는 알고리즘 탐구하기1 -기본 이론-

1. 무향 그래프에서 사이클 union find 알고리즘을 이용해서 쉽게 판단할 수 있다 https://deepdata.tistory.com/432 union find 알고리즘 활용 - 사이클을 판별하는 방법 -1. 사이클 판별 서로소 집합 알고리즘은 무방향 그래프에서 사이클을 판별할 때 사용할 수 있다. 방향 그래프에서 사이클 여부는 DFS로 확인할 수 있다고 한다 핵심 원리는 union 연산이 그래프에deepdata.tistory.com  간선을 확인하면서, 간선을 연결하는 두 노드의 대표자가 서로 같다면 사이클이 발생하는것이고, 서로 다르다면 union을 수행하면 된다  2. 유향 그래프에서 사이클 한 노드에서 출발했다가, 다른 노드들을 거쳐 이동하다보니 출발 노드로 돌아오면 사이클이 존재한다고 한..

• format_list_bulleted 그래프 이론 정복기
• · 2024. 6. 14.
• textsms

강한 연결 요소(Strongly connected component)를 구하는 코사라주 알고리즘(kosaraju's algorithm) 배우기

1. 강한 연결 요소(strongly connected component) 방향그래프에서 임의의 정점 v1,v2를 골랐을때, 항상 v1과 v2를 서로 오갈 수 있는 경로가 존재한다면, 그러한 방향 그래프를 강한 연결 요소(SCC)라고 부른다. 이 정의에 의하면 무방향 그래프에서는 전체 그래프가 반드시 강한 연결 요소가 되므로 의미가 없다. 즉, 방향 그래프에서만 의미있는 정의가 된다. 아무튼 예를 들어 다음 그래프는 모든 정점 쌍 (v1,v2)에 대하여 서로 오가는 경로가 존재하는 강한 연결 요소이다. 하지만 다음 그래프는.. 2번에서 5번으로는 갈 수 있어도 5번에서 2번으로 올 수는 없다. 그러므로 강한 연결 요소가 아니다. 하지만 그래프를 다음과 같이 적당히 분할하면, 분할된 그룹들 [1,2,3,4..

• format_list_bulleted 그래프 이론 정복기
• · 2023. 9. 2.
• textsms

위상정렬 재활치료하기 - 그래프에 사이클이 존재하여 정렬이 불가능한경우

1. 위상정렬 가볍게 복습 그래프의 노드를 정렬하는 위상정렬 정복하기 (tistory.com) 그래프의 노드를 정렬하는 위상정렬 정복하기 1. 개요 위상 정렬(topology sort)은 정렬 알고리즘의 일종 위상 정렬은 순서가 정해져 있는 일련의 작업을 차례대로 수행해야할 때 사용할 수 있는 알고리즘 이론적으로, 위상 정렬은 방향 그래프의 deepdata.tistory.com 1) 그래프를 만들면서, 각 노드의 진입차수(indegree)를 세준다. 2) 진입차수가 0인 노드를 큐에 모두 넣는다. 3) 큐가 빌때까지 다음을 반복 3-1) 큐에서 노드를 하나 빼고, 결과 리스트에 넣어준다. 3-2) 3-1)에서 뺀 노드에서 출발하는 모든 간선을 제거 3-3) 3-2) 후에 노드의 진입차수가 0이 된 노드는..

• format_list_bulleted 위상정렬
• · 2023. 3. 17.
• textsms