그래프 사이클 관련 문제

기본적인 원리

일단 DFS로 푼다고만 생각하자. BFS로 될 수도 있는데 생각보다 어려움...

 

parent list 만들어서 부모 노드를 기록한다.

 

부모 노드가 아닌데 방문했던 노드를 다시 방문하는 경우 사이클이 존재하는 것이다!

 

또, 사이클을 찾는 순간 y(사이클의 시작점), x(사이클의 끝점) 를 알게 된다!

x부터 쭉 x = parent[x] 해주면서 cycle list에 넣어준다. y까지 넣고 나면 종료한다.

 

함수 자체는 사이클의 존재 여부를 반환하게 한다.

이러면 사이클을 저장한 뒤 True를 반환하고 이 함수를 호출했던 부모 함수가 계속 True를 반환해서 모든 프로세스가 거의 즉시 종료된다.

 

소스코드

cycle = []
check = [False]*(n+1)
parent = [-1]*(n+1) # 부모 노드를 저장

def dfs_visit(x): # 사이클 존재 여부를 반환
    for y in a[x]:
        if check[y]: # 이미 방문한 점을 다시 방문
            if y == parent[x]: continue # 부모 노드를 다시 방문하는 건 사이클의 징조가 아님

            # 사이클을 찾았다! x부터 y까지 부모 노드를 찾으면서 사이클 list에 집어넣는다
            cycle.append(x)
            while x != y:
                x = parent[x]
                cycle.append(x)
            return True
        check[y] = True # 방문 처리
        parent[y] = x # 부모 노드 저장
        if dfs_visit(y): return True
    return False

 

연습문제

 

https://www.acmicpc.net/problem/16929

16929번: Two Dots

 

https://www.acmicpc.net/problem/16947

16947번: 서울 지하철 2호선

 

(참고)

서울 지하철 2호선은 먼저 사이클을 구한 뒤 사이클로부터의 거리를 재는 문제!

 

특정 성질을 가진 노드들로부터의 거리를 재는 문제에 필요한 아이디어는 다음과 같다.

 

특정 성질을 가진 노드들을 모두 queue에 넣는다!

 

그리고 BFS를 한다! 그러면 특정 성질을 가진 노드들로부터의 거리가 자연스럽게 재진다!