[SWEA] 1267 [S/W 문제해결 응용] 10일차 - 작업순서 (파이썬 python)

 

 

문제 링크

 

 

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18TrIqIwUCFAZN 

SW Expert Academy

 

 

문제 풀이

 

위상정렬을 활용해서 문제를 풀이했다.

 

 

위상정렬이란?

 

- 순서가 정해져 있는 일련의 작업을 차례대로 수행해야 할 때 사용할 수 있는 알고리즘

- 사이클이 없는 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것'

- 기본 조건으로 위상 정렬을 수행할 수 있는 그래프는 사이클이 없는 방향 그래프이다.

 

* 진입차수(Indegree) : 특정한 노드로 들어오는 간선의 개수

* 진출차수(Outdegree) : 특정한 노드에서 나가는 간선의 개수

 

 

알고리즘 동작 과정

 

1) 진입차수가 0인 노드를 큐에 넣는다

2) 큐가 빌 때까지 다음 과정을 반복한다

1. 큐에서 원소를 꺼내 해당 노드에서 나가는 간선을 그래프에서 제거

2. 새롭게 진입차수가 0이 된 노드를 큐에 삽입

 

 

위상 정렬 특징

 

1) 사이클이 없는 방향 그래프에서만 수행 가능

2) 위상 정렬에서는 여러 답이 존재할 수 있다

=> 하나의 노드에서 여러 개의 노드로 간선이 존재 한다면,

그 순서가 달라질 수 있기 때문

3) 모든 원소를 방문하기 전에 큐가 비게 된다면 사이클이 존재한다고 판단

4) 보통 큐로 구현하지만 DFS를 이용해서 풀 수도 있음

 

 

시간 복잡도

 

차례대로 모든 노드를 확인하면서 O(V)

해당 노드에서 출발하는 간선을 차례로 제거 O(E) 해야 함

=> O(V + E)

 

 

from collections import deque
for tc in range(1, 11):
    v, e = map(int, input().split())
    edges = list(map(int, input().split()))  # 간선

    indegree = [0] * (v + 1)   # 진입차수
    graph = [[] for _ in range(v + 1)]  # 연결된 노드

    queue = deque()
    result = []

    for i in range(0, e):
        start = edges[i * 2]
        end = edges[i * 2 + 1]
        graph[start].append(end)
        indegree[end] += 1

    for i in range(1, v + 1):
        if indegree[i] == 0:
            queue.append(i)

    while queue:
        now = queue.pop()
        result.append(now)
        for i in graph[now]:
            indegree[i] -= 1
            if indegree[i] == 0:
                queue.append(i)

    result = ' '.join(list(map(str, result)))
    print("#{} {}".format(tc, result))

 

 

노드에 대한 숫자는 1부터 시작하므로,

진입 차수와 연결된 노드를 저장하는 indegree, graph 리스트를

v + 1까지의 범위로 초기화했다.

 

입력받은 간선을 표현하는 정점들을 저장하기 위해 graph 리스트에

graph[0번 인덱스의 값] = 1번 인덱스의 값

의 형식으로 짝수번째 인덱스의 값의 노드에서

홀수번째 인덱스의 값의 노드로 이동함을 저장했다.

이와 함께 홀수번째 인덱스의 값에 대한 indegree, 즉 진입차수는 1씩 증가시켜주었다.

 

진입 차수가 0인 것들을 하나씩 지워내며,

그 노드와 연결된 노드들의 진입 차수 역시 1씩 줄어나가는 알고리즘을 구현하기 위해

 

먼저, 진입차수가 0인 노드들을 큐에 넣어주었다.

(진입 차수가 0이라는 것은 가장 먼저 출발하는 노드라는 뜻)

 

큐에 넣은 것들을 하나씩 빼주며 결과 리스트에 더해주고

해당 노드에서 이동하게 되는 노드를 graph 리스트에서 빼내어

연결된 노드의 진입차수 값을 1씩 빼준다.

 

(이 때 큐에서 pop()을 하는 방식에 따라 결과값이 달라질 수 있다.)

 

진입 차수가 0이 된 노드가 있다면 다시 큐에 넣어주고

큐에 값이 없을 때까지 이를 반복한다.

 

이 반복이 끝난 후에 결과 리스트에 저장된 값이

작업 순서가 된다.