Willing

1. 문제 / 난이도 : GoldⅡ

www.acmicpc.net/problem/2623

2. 풀이 및 코드 설명

처음에는 어떻게 풀어야하지...? 하고 고민하다가 결국 알고리즘 분류에 위상정렬이라는 키워드가 있는 것을 보고 간단한 위상정렬 구현으로 쉽게 풀었다.

순서가 정해져 있는 노드들을 전부 방문해야 한다면 => 위상 정렬을 사용할 수 있다는 점을 잊지 말자!

(1) 초기화 및 설정

	cin >> N >> M;
	while (M--) {
		cin >> K;
		int prev;
		for (int i = 0; i < K; i++) {
			int current;
			if (i == 0) cin >> prev; // i가 0이라면 맨 처음 값이므로 prev 초기화
			else {
				cin >> current;
				cnt[current] = cnt[current] + 1; // 진입 vertex 수 cnt 증가
				arr[prev].push_back(current); // prev -> current로 이어진 그래프 생성
				prev = current; // prev 갱신
			}
		}
	}

• arr : 각 노드마다 연결된 노드들의 정보들을 저장
• cnt : 위상정렬을 구현하기 위한 배열. 각 노드당 진입 vertex의 개수를 저장

(2) 큐 초기값

queue<int> q; // 위상정렬 큐
	for (int i = 1; i < N + 1; i++) {
		if (cnt[i] == 0 && visit[i] == 0) { // 아직 방문하지 않았고, 진입 vertex 수가 0이라면
			q.push(i); // 해당 노드 큐에 추가
			visit[i] = 1; // visit값 갱신
		}
	}

(3) 위상정렬

	while (!q.empty()) {
		int current = q.front(); // 현재 노드
		q.pop();
		result.push_back(current); // result 배열에 추가

		for (int i = 0; i < arr[current].size(); i++) {
			cnt[arr[current][i]]--; // 현재 노드와 연결된 노드 모두 진입 vertex 수 하나씩 감소
		}

		for (int i = 1; i < N + 1; i++) {
			if (cnt[i] == 0 && visit[i] == 0) { // 갱신된 노드들 중 진입 vertex 수가 0이고 아직 방문하지 않았다면
				q.push(i);
				visit[i] = 1;
			}
		}
	}

• 큐가 빌 때까지 위상정렬 진행

(4) 출력

	if (result.size() != N) cout << 0;
	else {
		for (int i = 0; i < N; i++) cout << result[i] << endl;
	}

• result 크기와 N이 같지 않다는 것 : 중간에 순환이 생겨 위상정렬이 제대로 이루어지지 않았다는 것 = 순서를 정할 수 없다는 말
• 위의 조건이 아닐때는 result 순서대로 출력

3. 전체 코드

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

int N, M, K;
vector<vector<int>> arr(1001);
int cnt[1001];
int visit[1001];
vector<int> result;

int main() {
	cin >> N >> M;
	while (M--) {
		cin >> K;
		int prev;
		for (int i = 0; i < K; i++) {
			int current;
			if (i == 0) cin >> prev;
			else {
				cin >> current;
				cnt[current] = cnt[current] + 1;
				arr[prev].push_back(current);
				prev = current;
			}
		}
	}

	queue<int> q;
	for (int i = 1; i < N + 1; i++) {
		if (cnt[i] == 0 && visit[i] == 0) {
			q.push(i);
			visit[i] = 1;
		}
	}
	
	while (!q.empty()) {
		int current = q.front();
		q.pop();
		result.push_back(current);

		for (int i = 0; i < arr[current].size(); i++) {
			cnt[arr[current][i]]--;
		}

		for (int i = 1; i < N + 1; i++) {
			if (cnt[i] == 0 && visit[i] == 0) {
				q.push(i);
				visit[i] = 1;
			}
		}
	}

	if (result.size() != N) cout << 0;
	else {
		for (int i = 0; i < N; i++) cout << result[i] << endl;
	}
}

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