저희는 유명한 게임인 뱀과 사다리에 대해 알고 있습니다. 이 게임에서 일부 방은 방 번호와 함께 보드에 있습니다. 일부 객실은 사다리 또는 뱀으로 연결되어 있습니다. 사다리를 얻으면 어떤 방까지 올라갈 수 있어 순차적으로 움직이지 않고 목적지에 가까워질 수 있다. 마찬가지로, 뱀을 잡으면 더 낮은 방으로 보내어 그 방에서 다시 여행을 시작합니다. 이 문제에서는 시작점에서 목적지까지 도달하는 데 필요한 최소 주사위 수를 찾아야 합니다. 입력 및 출력 Input: The starting and ending location of t

Tarjans Algorithm은 방향 그래프의 강하게 연결된 구성 요소를 찾는 데 사용됩니다. 이 알고리즘을 구현하려면 단 한 번의 DFS 순회만 필요합니다. DFS 탐색을 사용하여 숲의 DFS 트리를 찾을 수 있습니다. DFS 트리에서 강력하게 연결된 구성 요소를 찾습니다. 그러한 하위 트리의 루트가 발견되면 전체 하위 트리를 표시할 수 있습니다. 그 하위 트리는 강력하게 연결된 구성 요소 중 하나입니다. 입력 및 출력 입력:그래프의 인접 행렬.0 0 1 1 01 0 0 0 00 1 0 0 00 0 0 10 0 0 0 0출

방향성 비순환 그래프의 위상 정렬은 정점의 선형 순서입니다. 방향 그래프의 모든 모서리 U-V에 대해 정점 u는 순서에서 정점 v보다 먼저 옵니다. 소스 정점이 대상 정점 다음에 올 것이라는 것을 알고 있으므로 스택을 사용하여 이전 요소를 저장해야 합니다. 모든 노드를 완료한 후 스택에서 간단히 표시할 수 있습니다. 입력 및 출력 입력:0 0 0 0 0 00 0 0 0 0 00 0 0 1 0 00 1 0 0 0 01 1 0 0 0 01 0 1 0 0 0출력:토폴로지 정렬 순서 이후의 노드:5 4 2 3 1 0 알고리즘 top

Ford-Fulkerson 알고리즘은 주어진 그래프에서 시작 정점에서 싱크 정점까지의 최대 흐름을 감지하는 데 사용됩니다. 이 그래프에서 모든 간선에는 용량이 있습니다. Source 및 Sink라는 두 개의 정점이 제공됩니다. 소스 꼭짓점에는 바깥쪽 가장자리가 없고 안쪽 가장자리가 없으며 싱크에는 바깥쪽 가장자리가 없는 모든 안쪽 가장자리가 있습니다. 몇 가지 제약이 있습니다. 가장자리의 흐름은 해당 그래프의 주어진 용량을 초과하지 않습니다. 들어오는 흐름과 나가는 흐름도 소스와 싱크를 제외한 모든 가장자리에 대해 동일합니다

Transitive Closure 그래프의 꼭짓점 u에서 꼭짓점 v까지 도달하는 도달 가능성 매트릭스입니다. 하나의 그래프가 주어지면 모든 정점 쌍(u, v)에 대해 다른 정점 u에서 도달할 수 있는 정점 v를 찾아야 합니다. 마지막 행렬은 부울 유형입니다. 꼭짓점 u에서 꼭짓점 v까지의 값이 1이면 u에서 v까지의 경로가 하나 이상 있음을 의미합니다. 입력 및 출력 Input: 1 1 0 1 0 1 1 0 0 0 1 1 0 0 0 1 Output: The matrix of transitive closure 1 1 1

그래프가 제공됩니다. 주어진 그래프가 별 그래프인지 확인해야 합니다. 그래프를 순회함으로써 우리는 차수가 1인 꼭짓점의 수와 차수가 n-1인 꼭짓점의 수를 찾아야 합니다. (여기서 n은 주어진 그래프의 정점 수입니다). 차수가 1인 꼭짓점의 수가 n-1이고 차수(n-1)인 꼭짓점이 1이면 별 그래프입니다. 입력 및 출력 Input: The adjacency matrix: 0 1 1 1 1 0 0 0 1 0 0 0 1 0 0 0 Output: It is a star graph. 알고리즘 checkStarGraph(graph)

Bellman-Ford 알고리즘은 소스 정점에서 다른 정점까지의 최소 거리를 찾는 데 사용됩니다. 이 알고리즘과 Dijkstra 알고리즘의 주요 차이점은 Dijkstra 알고리즘에서는 음수 가중치를 처리할 수 없지만 여기서는 쉽게 처리할 수 있다는 것입니다. Bellman-Ford 알고리즘은 상향식 방식으로 거리를 찾습니다. 처음에는 경로에 가장자리가 하나만 있는 거리를 찾습니다. 그런 다음 가능한 모든 솔루션을 찾기 위해 경로 길이를 늘립니다. 입력 및 출력 Input: The cost matrix of the graph:

이 문제에서는 다른 상자 세트가 제공되며 길이, 너비 및 너비는 상자마다 다를 수 있습니다. 우리의 임무는 가능한 한 높이가 높은 이러한 상자 더미를 찾는 것입니다. 원하는 대로 상자를 회전할 수 있습니다. 하지만 지켜야 할 규칙이 있습니다. 하단 상자의 상단 표면 면적이 상단 상자의 하단 면적보다 크면 다른 상자에 상자를 놓을 수 있습니다. 입력 및 출력 Input: A list of boxes is given. Each box is denoted by (length, bredth, height). { (4, 6, 7), (1,

무방향 그래프에 주기가 있는지 여부를 감지하기 위해 주어진 그래프에 대해 DFS 순회를 사용합니다. 모든 방문 정점 v에 대해 인접 정점 u를 찾았을 때 u는 이미 방문했고 u는 정점 v의 부모가 아닙니다. 그러면 한 주기가 감지됩니다. 정점 쌍에 대해 평행한 모서리가 없다고 가정합니다. Input and Output: Adjacency matrix         0 1 0 0 0     1 0 1 1 0     0 1 0 0 1    

DFS(Depth First Search) 탐색 알고리즘을 사용하여 방향 그래프에서 주기를 감지할 수 있습니다. 임의의 노드에 자체 루프가 있으면 주기로 간주되고, 그렇지 않으면 자식 노드에 부모를 연결하는 다른 가장자리가 있는 경우에도 주기가 됩니다. 연결이 끊긴 그래프의 경우 다른 나무가 있을 수 있으며 이를 포리스트라고 부를 수 있습니다. 이제 우리는 숲의 모든 나무에 대한 주기를 감지해야 합니다. 이 접근 방식에서는 다른 집합을 사용하여 DFS 탐색을 수행할 노드를 할당합니다. 화이트, 그레이, 블랙의 3가지 세트가

오일러 경로는 모든 모서리를 정확히 한 번만 방문할 수 있는 경로입니다. 같은 정점을 여러 번 사용할 수 있습니다. 오일러 회로는 특수한 유형의 오일러 경로입니다. 오일러 경로의 시작 꼭짓점과 해당 경로의 끝 꼭짓점이 연결되어 있는 경우 이를 오일러 회로라고 합니다. 그래프가 오일러인지 아닌지 확인하려면 두 가지 조건을 확인해야 합니다. - 그래프가 연결되어 있어야 합니다. 각 꼭짓점의 내차수와 외차수는 동일해야 합니다. 입력 및 출력 Input: Adjacency matrix of the graph. 0 1 0 0 0 0

오일러 경로는 모든 모서리를 정확히 한 번만 방문할 수 있는 경로입니다. 같은 정점을 여러 번 사용할 수 있습니다. 오일러 회로는 특수한 유형의 오일러 경로입니다. 오일러 경로의 시작 꼭짓점과 해당 경로의 끝 꼭짓점이 연결되어 있는 경우 이를 오일러 회로라고 합니다. 경로와 회로를 감지하려면 다음 조건을 따라야 합니다. 그래프가 연결되어 있어야 합니다. 정확히 두 개의 정점이 홀수 차수를 가질 때 오일러 경로입니다. 무방향 그래프의 정점이 홀수 차수를 가지지 않으면 오일러 회로입니다. 입력 및 출력 Input: Adjac

Fleurys Algorithm은 주어진 그래프에서 오일러 경로 또는 오일러 회로를 표시하는 데 사용됩니다. 이 알고리즘에서는 한 모서리에서 시작하여 이전 정점을 제거하여 다른 인접 정점을 이동하려고 합니다. 이 트릭을 사용하면 그래프가 오일러 ​​경로 또는 회로를 찾기 위한 각 단계에서 더 간단해집니다. 경로 또는 회로를 얻으려면 몇 가지 규칙을 확인해야 합니다. 그래프는 오일러 그래프여야 합니다. 에지가 두 개일 때 하나는 브리지이고 다른 하나는 비 브리지이므로 처음에는 비 브리지를 선택해야 합니다. 시작 정

그래프 채색 문제는 그래프 레이블 지정의 특별한 경우입니다. 이 문제에서 각 노드는 몇 가지 색상으로 채색됩니다. 그러나 채색에는 몇 가지 제약이 있습니다. 인접한 정점에 동일한 색상을 사용할 수 없습니다. 이 문제를 해결하기 위해서는 greedy 알고리즘을 사용해야 하지만 최소 색상 사용을 보장하지는 않습니다. 입력 및 출력 Input: Adjacency matrix of the graph. 0 0 1 0 1 0 0 1 1 1 1 1 0 1 0 0 1 1 0 1 1 1 0 1 0 Output: Node: 0, Assigne

가중된 방향성 비순환 그래프 하나가 제공됩니다. 다른 소스 정점도 제공됩니다. 이제 그래프에서 시작 노드에서 다른 모든 정점까지의 가장 긴 거리를 찾아야 합니다. 토폴로지 정렬 기법으로 노드를 정렬해야 하며, 토폴로지 정렬 후 결과는 스택에 저장됩니다. 그 후 스택에서 반복적으로 팝되고 각 정점에 대한 가장 긴 거리를 찾습니다. 입력 및 출력 Input: The cost matrix of the graph. 0  5   3 -∞ -∞ -∞ -∞ 0   2

그래프의 정점을 두 개의 독립적인 집합으로 나눌 수 있는 경우 그래프의 모든 모서리가 첫 번째 집합에서 시작하여 두 번째 세트 또는 두 번째 세트에서 시작하여 첫 번째 세트에 연결됩니다. 즉, 동일한 세트에서 가장자리를 찾을 수 없다고 말할 수 있습니다. 정점 채색을 사용하여 이분 그래프의 확인이 가능합니다. 정점이 같은 집합에 있으면 같은 색을 가집니다. 다른 집합에 대해서는 색이 바뀝니다. 입력 및 출력 입력:인접 매트릭스 알고리즘 isBipartite(출처) 입력 - 소스 정점. 출력 그 :그래프가 이분법이면 참입

가중된 방향성 비순환 그래프 하나가 제공됩니다. 다른 소스 정점도 제공됩니다. 이제 그래프에서 시작 노드에서 다른 모든 정점까지의 최단 거리를 찾아야 합니다. 더 작은 거리를 감지하기 위해 음수 가중치 그래프에 Bellman-Ford와 같은 다른 알고리즘을 사용할 수 있습니다. 양수 가중치의 경우 Dijkstra 알고리즘도 도움이 됩니다. Directed Acyclic Graph의 경우 토폴로지 정렬 기술을 사용하여 복잡성을 줄입니다. 입력 및 출력 Input: The cost matrix of the graph. 0 &nbs

이분법 일치는 그래프의 모서리 세트가 끝점을 공유하지 않는 방식으로 그래프의 모서리 세트를 선택하는 것입니다. 최대 일치는 최대 가장자리 수와 일치합니다. 최대 일치 항목이 발견되면 다른 가장자리를 추가할 수 없습니다. 최대 일치 그래프에 하나의 간선이 추가되면 더 이상 일치하지 않습니다. 이분 그래프의 경우 최대 일치가 두 개 이상 있을 수 있습니다. 입력 및 출력 Input: The adjacency matrix. 0 1 1 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0

이 문제에서는 2D 평면에 n개의 점 집합이 제공됩니다. 이 문제에서는 거리가 최소인 점 쌍을 찾아야 합니다. 이 문제를 해결하려면 두 점 사이의 가장 작은 거리를 재귀적으로 계산한 후 점을 두 개의 반으로 나누어야 합니다. 중간 선으로부터의 거리를 사용하여 점을 일부 스트립으로 분리합니다. 스트립 배열에서 가장 작은 거리를 찾습니다. 처음에는 데이터 포인트로 두 개의 목록이 생성되며, 하나의 목록은 x 값으로 정렬된 포인트를 보유하고 다른 목록은 y 값으로 정렬된 데이터 포인트를 보유합니다. 이 알고리즘의 시간 복잡도는 O(n

항목은 해당 요소의 이웃 4개 모두보다 크거나 같을 때 피크 요소라고 합니다. 이웃 요소는 위쪽, 아래쪽, 왼쪽 및 오른쪽 요소입니다. 이 문제에 대해 몇 가지 경계를 고려할 것입니다. 대각선 요소는 인접 요소로 확인되지 않습니다. 하나 이상의 피크 요소가 매트릭스에 존재할 수 있으며 피크 요소가 반드시 매트릭스에서 가장 큰 요소일 필요는 없습니다. 입력 및 출력 Input: A matrix of different numbers. 10  8  10  10 14 13  12  11 15 &