Willing

1. 문제 / 난이도 : Gold Ⅴ

www.acmicpc.net/problem/2668

2. 풀이 및 코드 설명

단순히 그래프의 순환을 찾아서 출력하는 문제. 순환을 찾기 -> 해당 순환의 첫노드와 마지막 노드까지를 answer 배열에 넣기 -> 다음 순환 찾기의 반복으로 풀 수 있었다.

(1) 순환 찾기

for (int i = 1; i <= N; i++) {
		if (!visited[i] && !visited[nums[i]]) checkCycle(i); //현재 노드와 연결된 노드 둘 다 아직 방문한 적이 없는 노드라면 checkCycle
		visited[i] = true; //visited 갱신
	}

• 현재 노드와 연결된 노드를 둘 다 보는 이유는 현재 노드는 당연히 방문한 적이 없어야 하고, 연결된 노드가 이미 방문된 노드라면 앞에서 순환 검사를 이미 끝마쳤다는 소리이기 때문

void checkCycle(int node) {
	visited[node] = true; //visited 갱신
	int next = nums[node];
	
    //만일 순환이 발생한다면
	if (visited[next]) { 
		addAnswer(next, node);//순환의 처음과 끝을 가지고 addAnswer수행
		return;
	}
	checkCycle(next); //순환이 발생하지 않으면 연결된 다음 노드로 이동
}

(2) answer배열에 추가하기

void addAnswer(int start, int goal) {
	int current = start;
	answer.push_back(current);
    // 그래프를 타고 다음 노드로 넘어가며 goal과 같은 노드에 다다르기 전까지 answer 배열에 추가
	while (current != goal) {
		current = nums[current];
		answer.push_back(current);
	}
}

3. 전체 코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int N;
int nums[101];
bool visited[101];
vector<int> answer;

void addAnswer(int start, int goal) {
	int current = start;
	answer.push_back(current);
	while (current != goal) {
		current = nums[current];
		answer.push_back(current);
	}
}

void checkCycle(int node) {
	visited[node] = true;
	int next = nums[node];
	
	if (visited[next]) {
		addAnswer(next, node);
		return;
	}
	checkCycle(next);
}


int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> N;

	for (int i = 1; i <= N; i++) cin >> nums[i];

	for (int i = 1; i <= N; i++) {
		if (!visited[i] && !visited[nums[i]]) checkCycle(i);
		visited[i] = true;
	}

	cout << answer.size()<<'\n';
	sort(answer.begin(), answer.end());
	for (auto& ele : answer) cout << ele << '\n';
}

1. 위상 정렬이란?

위상 정렬 (Topology Sort)

• 순서가 정해져 있는 작업 을 차례로 수행해야할 때, 그 순서를 결정해주는 알고리즘
• 순차적으로 어떤 그래프가 형성되어 있을 때, 해당 그래프를 하나의 경로로 표현
• 여러 나열 방법이 있을 수 있기 때문에 답이 다양하게 나올 수 있음
• DAG에만 적용 가능
  • DAG : Directed Acyclic Graph, 사이클이 존재하지 않는 방향 그래프
  • 위상 정렬은 시작점이 존재해야 하지만, 사이클 그래프에서는 시작점을 찾을 수가 없음

위상 정렬에서 알 수 있는 두 가지

• 현재 그래프가 위상 정렬이 가능한가?
• 위상 정렬이 가능하다면 그 결과는 무엇인가?

2. 위상 정렬 구현

큐를 이용한 방식

1. 진입차수가 0인 정점을 큐에 삽입
   • 진입차수가 0인 정점이 여러 개 존재할 경우 어느 정점이든 무방
   • 초기에 간선의 수가 0인 모든 정점을 큐에 삽입
2. 큐에서 원소를 꺼내 연결된 모든 간선을 제거
   • 선택된 정점에 부속된 모든 간선에 대해 간선의 수를 감소
3. 간선 제거 이후에 진입차수가 0이 된 정점을 큐에 삽입
4. 큐가 빌 때까지 2번 ~ 3번 과정 반복
   • 모든 원소를 방문하기 전에 큐가 빈다면 => 사이클 존재
   • 모든 원소를 방문했다면 큐에서 꺼낸 순서가 위상 정렬의 결과

스택을 이용한 방식

1. 그래프에서 방문하지 않은 노드면 DFS를 수행
2. DFS가 끝나면 해당 노드를 스택에 추가
3. 스택에서 하나씩 꺼내면 위상 정렬된 노드들을 얻을 수 있음 (역순으로 출력하는 것과 같은 결과)

3. 코드 구현

큐를 이용한 방식

import queue

# 그래프의 인접 행렬
graph = {0: [1, 2, 3], 1: [4], 2: [4, 5], 3: [], 4:[6], 5:[1], 6: []}

def topology_sort_queue(graph):
    N = len(graph)
    sort_queue = queue.Queue() # 큐
    degree = [0 for _ in range(N)] # 진입차수 리스트

    for nodes in graph:
        for j in graph[nodes]:
            degree[j] += 1
    print("진입차수 리스트 : ", degree)

    for i in range(N):
        if degree[i] == 0: sort_queue.put(i)

    answer = []
    while not sort_queue.empty():
        current = sort_queue.get()
        answer.append(current)
        for i in graph[current]:
            degree[i] -= 1
            if degree[i] == 0 : sort_queue.put(i)
    print("최종 답 : ", answer)

topology_sort_queue(graph)

스택을 이용한 방식

# 그래프의 인접 행렬
graph = {0: [1, 2, 3], 1: [4], 2: [4, 5], 3: [], 4:[6], 5:[1], 6: []}

def topology_sort_stack(graph):
    N = len(graph)
    stack = [] # 스택
    visited = [0 for _ in range(N)] # 방문확인 리스트

    for i in graph:
        if visited[i] == 0:
            dfs(i, stack, visited)
    
    answer = []
    while len(stack) != 0:
        answer.append(stack.pop())
    print("최종 답 : ", answer)

def dfs(v, stack, visited):
    visited[v] = 1
    for i in graph[v]:
        if visited[i] == 0: dfs(i, stack, visited)
    stack.append(v)
topology_sort_stack(graph)

#. References

• velog.io/@max9106/Algorithm-%EC%9C%84%EC%83%81-%EC%A0%95%EB%A0%ACTopology-Sort
• m.blog.naver.com/ndb796/221236874984
• haedallog.tistory.com/122