링크 된 동일한 기호 각 그룹을 고려할 수 (및 연결에 의해 당신이 하나 개의 심볼에서 다른 여행 수 있음을 의미) 별도의 그래프 . 이러한 각 그래프에 대해 해당 그래프의 가장 긴 경로의 일부가 아닌 그래프의 각 노드에서 시작하는 DFS ( Depth First Search)를 적용하십시오 . DFS를 적용하는 동안 막 다른 골목에 도달 할 때마다 방금 통과 한 경로가 지금까지 찾은 전역 최대 길이보다 긴지 확인하십시오. 그렇다면 새로운 가장 긴 경로로 저장하십시오.

이전 단락에서 각 그래프에 대해 DFS를 여러 번 적용하는 것에 대해 언급했음을 알 수 있습니다. 그래프에서 실행 된 단일 DFS로는 충분하지 않습니다. 이 특별한 경우를 고려하십시오.

    1
1 1 1
    1
    1
    1
    1

우연히 맨 위 노드에서이 그래프에 대해 DFS를 먼저 실행하면 가능한 가장 긴 경로가 세로선 인 것으로 발견되지만 올바르지 않습니다. 이는 결과 경로 내에 있거나 전혀 포함되지 않은 노드에서 DFS 알고리즘을 시작할 때마다 발생합니다. 이 특정 예제에서해야 할 일은 두 번째 줄의 가장 왼쪽 노드에서 DFS 알고리즘을 시작하는 것입니다. 올바른 경로를 찾을 수 있습니다. 일반적으로 말하자면 위에서 언급 한 것처럼 현재 해당 그래프의 가장 긴 경로에 포함되지 않은 각 노드에서 DFS 알고리즘을 실행해야합니다.

이 알고리즘의 최악의 시나리오는 보드가 채워지거나 대부분 단일 기호 유형으로 채워져 있지만 게임에서는 발생하지 않을 것입니다. 또한 각 그래프의 가장 긴 경로를 저장하는 방법에주의하십시오. 이 비트를 최적화하지 않으면 스테이지의 각 노드에 대해 DFS를 호출하는 것이 좋습니다. 매우 큰 보드로 작업하지 않고 속도가 큰 문제가 아니라고 가정하면이 솔루션은 충분히 빠릅니다.

기술적으로 말하자면, 보드를 별도의 그래프로 분류하면 여러 개의 ” 최장 경로 문제 “가 발생합니다. 예제에서 볼 수 있듯이 그래프에주기가있을 수 있습니다 (예 : 동일한 유형의 스테이지 외부에 모든 기호가 있음).이 특정 문제에서 가장 긴 경로를 찾아야합니다. 여러 개의 정주기 방향성 그래프에서 다항식 시간에 수행 할 수 없습니다 .

이것이 너무 느리다 면 개별 “가장 긴 경로 문제”를 최적화하는 방법에 대한 자세한 내용은 StackOverflow 에서이 답변 을 참조하십시오 .

답변