Kuhn 알고리즘에서 각 시작 정점마다 visited를 초기화하지 않고 timestamp token을 쓰는 이유는 무엇인가요?

Kuhn의 한 번의 augmentation DFS 안에서는 같은 오른쪽 정점을 반복 방문하지 않아야 순환과 중복 재귀를 막을 수 있습니다. 하지만 다음 시작 정점의 DFS에서는 매칭이 이미 달라졌기 때문에 과거 탐색에서 방문한 정점을 다시 시도해야 합니다. seen[v]에 boolean을 영구 저장하는 대신 탐색마다 attempt를 증가시키고, seen[v] == attempt일 때만 이번 DFS의 방문으로 간주하는 timestamp token을 쓰면 이 두 요구를 동시에 만족합니다.

예를 들어 attempt=7에서 R2를 방문해 seen[R2]=7이 되었다고 하겠습니다. 현재 DFS가 끝난 뒤 새 왼쪽 정점에서 attempt=8로 시작하면 seen[R2]=7은 현재 세대가 아니므로 R2를 다시 검사합니다. 이때 매칭 배열에는 직전 augmentation의 재배치가 반영되어 있으므로, 과거에는 막혔던 상대가 새 증가 경로의 일부가 될 수 있습니다. 반대로 같은 attempt 안에서 재방문을 허용하면 L1→R1→old L→R1 같은 순환성 탐색이 생길 수 있습니다.

토큰은 매번 배열 전체를 false로 채우는 비용을 줄이는 구현 기법이기도 합니다. 다만 정수 토큰이 언젠가 래핑될 수 있으므로, 충분히 큰 타입을 쓰거나 포화 시 seen 전체를 0으로 초기화해야 합니다. 전역 visited를 영구 유지하면 정확성 문제가 생기고, 매번 전체 배열을 초기화하면 정확성은 유지되지만 시작 정점 수와 오른쪽 정점 수가 큰 경우 초기화 비용이 추가됩니다.

토큰의 정확한 범위는 구현에 따라 오른쪽 정점 또는 왼쪽 정점이지만, “한 번의 증가 시도에서만 순환을 차단한다”는 범위는 바뀌지 않습니다. 예를 들어 R1이 L0와 매칭되고 L1이 R1을 요청하면 L0를 재귀 호출합니다. 같은 시도에서 R1을 다시 허용하면 L0가 또 R1을 요청하는 고리가 생깁니다. 반대로 L1 시도가 실패한 뒤 매칭이 다른 시작점에서 바뀌었다면 token을 새로 발급해야 새 경로를 볼 수 있습니다. 전체 배열 초기화는 정확하지만 매번 오른쪽 정점 수만큼 쓰기 작업을 하며, token 방식은 보통 시도당 실제 방문분만 기록합니다.