그래프에서 역방향 간선을 놓아 노드들의 크기 순서를 찾는 테크닉(도달 가능성)

1. 문제 2458번: 키 순서  1번부터 n번까지 번호가 붙여진 학생들의 키 순서가 주어진다. 예를 들어 1번  이 결과로 모든 학생중 키가 가장 작은 학생부터 자신이 몇번째 학생인지 알 수 있는 학생도 있고,  그렇지 못한 학생들도 있다. 이러한 결과가 주어질때 자신의 키가 몇번째 학생인지 정확히 알 수 있는 학생 수를 구한다 ------------------------------------------------------------------------------------------------------------------------------------------------ 상식적으로? 먼저 생각해보면 i번이 몇번째 순서인지 알고 싶다면 i번보다 키가 큰 학생의 수, 키가 작은 학생의 수를 찾..

• format_list_bulleted 그래프 이론 정복기
• · 2025. 3. 29.
• 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

DFS 2번으로 트리의 지름을 구하는 방법

1. 문제 1967번: 트리의 지름 (acmicpc.net) 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 2. 풀이1 트리는 사이클이 없는 무방향 그래프이며, 두 노드 사이 모든 경로가 유일하다. 가장 길이가 긴 경로를 트리의 지름이라고 정의했는데.. 어쨌든 가장 길이가 긴 경로라면 결국 리프 노드와 리프 노드 사이 거리가 가장 길이가 긴 경로이다. 루트 노드가 1번 노드이고 (부모, 자식)으로 입력이 주어지니까 부모 노드 모두 표시해두면 표시가 안된 노드는 어떤 노드의 부모가 아니니까..

• format_list_bulleted 그래프 이론 정복기
• · 2023. 11. 28.
• textsms

저울의 무게 비교를 그래프로 바꿔서 최단 거리 알고리즘으로 해결(플로이드 워셜, 그래프 탐색)

1. 문제 10159번: 저울 (acmicpc.net) 10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net 2. 풀이 그냥 보면 어떻게 해야할지 감 잡기가 쉽지 않다.. 하지만 "2 > 3, 3 > 4로부터 2 > 4라는 것을 알 수 있다"를 봤을때, 1 > 2, 2 > 3, 3 > 4, 5 > 4, 6 > 5를 마치 방향 그래프에서 간선으로 보면 2에서 4로 도달할 수 있는가? 아닌가를 체크하면 되는 문제이다. 사실 뭐 최단 거리를 묻는 것은 아니므로 BFS나 DFS로 탐색하면 해결할 수..

• format_list_bulleted 그래프 이론 정복기
• · 2023. 9. 7.
• 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