[백준]9466 - 텀 프로젝트 (#파이썬 #DFS #cycle구현)

 

 

9466번: 텀 프로젝트

문제 요약

각각의 학생이 가리키는 타 학생 번호 정보를 통해 무리(cycle)가 만들어지지 않는 학생의 수를 구한다. 가령 A ➡️ B ➡️ C ➡️ D ➡️ E ➡️ C 순서로 지명하는 경우 무리가 만들어진 학생은 C, D, E이고, 무리가 만들어지지 않은 학생은 A, B이다. 가리키는 정보를 순서대로 따라가기 위해 DFS 구조를 사용하기로 하였다. 동시에 DFS 함수의 반환 값(결과)을 통해 무리 지어졌는지 여부를 저장할 수 있다.

DFS 구성

DFS를 어떻게 구성할 수 있을까?

위 이미지 처럼 cycle이 형성되면 형성되는 순간의 학생을 무리 친구들끼리 갖는다. DFS의 반환 값으로 '도착' 했을 때의 학생을 반환하면 되는 것이다. 이후 DFS가 반환(파란 화살표)되면서 C를 거치는 경우 그 순간(if (기존 node == 반환값)) -1과 같은 빈 값을 반환(빨간 화살표)하여 무리에 속하지 않음을 나타낸다.

즉, 해당 문제는 DFS를 통해 순회한 후 반환 값을 다루는 방식으로 해결할 수 있다.

F가 갑자기 B 또는 C를 가리킨다면? 🙄

전체적인 로직은 위와 같고, 예외 케이스를 생각해본다. 현재 DFS로 순회하지 않은 친구(F)가 이미 순회한 친구(A~E 중 하나)를 가리키는 경우가 있을 수 있다. 해당 case의 친구 F 같은 경우 어떤 친구를 가리키든 -1과 같은 빈 값을 반환 받으면 된다.

왜냐하면 1️⃣ '도착'한 학생의 반환 값을 갖는 친구(C, D, E 중 하나)를 선택하는 경우에는 무리 형성이 완료된 경우이기에 어떤 경우에도 새로운 친구가 발생하지 않는다. 만약 무리에 포함된 친구였다면 이미 DFS 순회에서 포함되었을 것이다. 이에 -1과 같은 빈 값을 받는 것이 타당하다.

2️⃣ 빈 값을 반환 받은 학생을 가리키는 경우에는 해당 학생을 따라 순회하면 결국 빈 값을 받은 학생으로 부터 다시 빈 값을 반환 받을 것이기 때문이다. F ➡️ A인 경우를 생각해보면 F는 무조건 A가 반환 받은 값을 다시 반환 받는다.

위 예외 케이스는 DFS 함수 내에 아래와 같이 반영할 수 있다.

def dfs(node):
        next_node = seq[node]
        
        if vis[next_node] != 0:
            vis_set.add(node)
            vis[node] = -1
            return -1

        ...

vis[next_node] 가 0이 아니라는 것은 이미 DFS를 통해 한 번 순회한 것에 접근하려고 하는 것이다. 즉, 이 경우 무조건 -1로 반환되도록 한다.

반환 값이 C이다가 조건에 따라 -1로 변환되는 코드

DFS가 반환(파란 화살표)되면서 C를 거치는 경우 그 순간(if (기존 node == 반환값)) -1과 같은 빈 값을 반환(빨간 화살표)하여 무리에 속하지 않음을 나타낸다.

위 설명과 같이 반환 값을 어떻게 변환시킬 수 있을까?

def dfs(node):
        next_node = seq[node]
        
        ...
                
        if vis[next_node] == 0:
            vis_set.add(next_node)
            root = dfs(next_node)
            vis[next_node] = root
            
            if root == next_node: return -1
            return root

DFS가 반환하는 값(root)이 현재의 node(= next_node)와 같은 경우 -1을 반환하고, 그렇지 않은 경우 지속 반환하는 값을 그대로 반환하면 된다.

Intuitive

백트래킹에서 자주 사용하는 방법이 떠올라 해당 문제에 적용시켜 보았다. 백트래킹에서는 DFS로 순회를 하고, return 되면서 '어떤 조치'를 취하기 때문이다. 여기서는 백트래킹 처럼 '어떤 조치'를 취하고 다시 다음 depth로 순회하는 것이 아니라, 순회한 경로를 다시 빠져나오는 것이라고 생각하였다.

 

📁 코드 전문