[Baekjoon 2668 / Python / 골드5] 숫자고르기

문제

 

 

DFS 문제이다. 진짜 최근에 푼 문제중 가장 어렵고 헷갈렸다.

그래프의 싸이클을 찾는 문제이며, 문제만 읽고 싸이클을 찾아야 겠다는 유추를 해내기가 힘들다. 그래프로 옮기는 과정도 힘들고, 싸이클 찾는 로직도 매우 헷갈리고, 단방향인지 양방향인지, 역방향은 결과에 영향을 미치는지, 싸이클을 찾으면 해당 거쳐온 노드를 모두 추가하는 건 안되는지 판단해야 했고.. 하여튼 여러 방향으로 미치는 줄 알았다.

 

# DFS

import sys

input = sys.stdin.readline

# 입력받기

N = int(input())

graph = [[] for _ in range(N + 1)]

for i in range(1, N + 1):

    graph[i].append(int(input()))

def DFS(node, start, tmpPath): # 현재노드, 시작노드, 현재경로

    # 방문 체크, 경로 추가

    visited[node] = True

    tmpPath.append(node)

    for nextNode in graph[node]:

        if nextNode in cycle: continue # 이미 싸이클에 포함된 노드일 경우 continue

        if not visited[nextNode]:

            DFS(nextNode, start, tmpPath)

        elif nextNode == start:

            for t in tmpPath:

                cycle.append(t)

# 하나의 노드는 하나의 싸이클에 속한다

# 따라서 이미 싸이클에 들어간 노드는 탐색하지 않음

cycle = []

for start in range(1, N + 1):

    if start not in cycle:

        visited = [False] * (N + 1)

        DFS(start, start, [])

cycle.sort()

print(len(cycle))

for c in cycle:

    print(c)

 

우선, 단방향 그래프로 입력받는다. 즉 윗줄이 노드고 아랫줄이 간선이라고 생각하면 된다.

결과를 저장할 cycle 리스트를 만든 후, 모든 노드를 시작점으로 1번 노드부터 전부 DFS를 돌린다.

단, 이미 싸이클에 포함되었다고 판단된 노드는 시작 노드에서 제외한다.

 

인접 노드를 탐색하다가 시작 노드를 다시 만났다면, 즉 되돌아왔다면 사이클이 존재한다고 판단하고 지나온 모든 노드를 cycle 리스트에 추가한다.

 

중요한 점은 시작 노드이든 탐색 중간에 거치는 노드이든 이미 cycle 리스트에 존재한다면 탐색을 중지하는 것이다. 그 이유는 문제 특성상 하나의 노드는 하나의 싸이클에만 포함되기 때문이다. cycle 리스트는 결과를 담을 리스트이자 제2의 visited 같은 역할도 하는 것이다.

 

탐색이 끝났다면 마지막으로 cycle을 정렬해주고 출력하면 된다.

 

결과