작업순서 Python(SW Expert Academy, SWEA)

난이도 : D6

문제번호 : 1267

문제 주소 및 출처입니다.

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV18TrIqIwUCFAZN&categoryId=AV18TrIqIwUCFAZN&categoryType=CODE

SW Expert Academy

---

목차

1. 문제 설명

2. 문제 해석

3. 소스 코드

---

1. 문제 설명

해야 할 V개의 작업이 있다. 이들 중에 어떤 작업은 특정 작업이 끝나야 시작할 수 있으며, 이를 선행 관계라 하자. 이런 작업의 선행 관계를 나타낸 그래프가 주어진다. 이 그래프에서 각 작업은 하나씩의 정점으로 표시되고 선행 관계는 방향성을 가진 간선으로 표현된다. 단, 이 그래프에서 사이클은 존재하지 않는다 (사이클은 한 정점에서 시작해서 같은 정점으로 돌아오는 경로를 말한다). 아래 그림은 이런 그래프의 한 예다. 이 그래프에서 작업 1은 작업 4가 끝나야 시작할 수 있다. 작업 6은 작업 5와 작업 7이 끝나야 할 수 있다. 이 그래프에서는 사이클이 없다.   김과장은 선행 관계가 주어진 작업군을 한 번에 하나의 작업씩 처리해서 다 끝내려 한다. 위에서 예를 든 작업군에 대해서 이런 일을 한다면 아래의 순서로 처리할 수 있다.   8, 9, 4, 1, 5, 2, 3, 7, 6   또한 아래의 순서도 가능하다.   4, 1, 2, 3, 8, 5, 7, 6, 9   아래의 순서는 가능하지 않다.   4, 1, 5, 2, 3, 7, 6, 8, 9   이 순서에서는 작업 5가 작업 8보다 먼저 처리되는데, 위 그래프에서 주어진 선행 관계에서는 작업 5는 작업 8이 끝나야 시작할 수 있어 이 순서로 끝내는 것은 가능하지 않다.   V개의 작업과 이들 간의 선행 관계가 주어질 때, 한 사람이 한 번에 하나씩 일을 할 수 있는 작업 순서를 찾는 프로그램을 작성하라. 가능한 작업 순서는 보통 여러 가지가 있으므로 여러분은 이들 중 하나만 제시하면 된다. 사이클이 있는 그래프는 입력에서 주어지지 않으므로 이런 경우에 대한 에러 처리는 고려하지 않아도 좋다. 사이클이 없는 그래프에서 가능한 순서는 항상 존재한다. 그래프에서 정점의 총 수 V는 5≤V≤1000.

입력

10개의 테스트 케이스가 주어진다. 20줄에 걸쳐, 두 줄에 테스트 케이스 하나씩 제공된다. 각 케이스의 첫줄에는 그래프의 정점의 총 수 V와 간선의 총 수 E가 주어진다. 그 다음 줄에는 E개 간선이 나열된다. 간선은 간선을 이루는 두 정점으로 표기된다. 예를 들어, 정점 5에서 28로 연결되는 간선은 “5 28”로 표기된다. 정점의 번호는 1부터 V까지의 정수값을 가지며, 입력에서 이웃한 수는 모두 공백으로 구분된다.

출력

총 10줄에 10개의 테스트케이스 각각에 대한 답을 출력한다. 각 줄은 ‘#x’로 시작하고 공백을 하나 둔 다음 작업 순서를 기록한다. 작업 순서는 V개 정수를 공백을 사이에 두고 나열하는 것이다.

예시

입력	출력
9 9 4 1 1 2 2 3 2 7 5 6 7 6 1 5 8 5 8 9 5 4 1 2 2 3 4 1 1 5 ...	#1 8 9 4 1 5 2 3 7 6 #2 4 1 2 3 5 ...

---

2. 문제풀이

선행조건이 달성되어야 해당노드를 방문하는 문제이다. 이럴때는 반대로 생각해서 풀면 조금쉽다. 예를들어서 일반적인경우 4번의 리스트에 1번이 들어가게 되는데 4번노드에 1번노드가 연결되어있다는 뜻으로 적는다. 그런데 이런경우는 1번노드를 방문하기 위해 4번노드를 방문했어야 한다 라고 된다. 따라서 반대로 엮어서 확인한다. 1번노드쪽에 4번노드를 걸어준다. 1번노드를 방문하기 위해 안에 리스트를 돌면서 모두다 방문이 되어있다면 방문표시를 한다. 이와 같은 과정을 반복한다.

---

3. 소스코드

#D6 1267 작업순서
T = 10
for t in range(1, T+1):
    v, e = map(int, input().split())
    graph = [[] for _ in range(v+1)]
    visited = [True for _ in range(v+1)]
    temp_list = list(map(int, input().split()))
    count = v
    #그래프 만들기, 선행순서이므로 반대로 넣어준다.
    #ex a가 1이고 b가 2라면
    #2번노드는 1번노드가 수행완료가 되어야 가능하다.
    for i in range(0, len(temp_list), 2):
        a = temp_list[i]
        b = temp_list[i+1]
        graph[b].append(a)
    #결과누적 리스트
    result = []
    #노드가 모두 수행될때까지 반복한다.
    while count:
        #1번노드부터 마지막 노드까지 반복
        for i in range(1, len(graph)):
            #현재노드가 수행되지 않았다면
            if visited[i]:
                #선행노드를 확인한다.
                for j in graph[i]:
                    #선행노드가 아직 수행되지 않았다면 멈춘다.
                    if visited[j]:
                        break
                else:
                    #선행노드가 모두 수행되었다면
                    #현재노드를 수행했다고 바꾸고 결과에 추가한다.
                    #노드가 수행되었으므로 count를 감소시킨다.
                    visited[i] = False
                    result.append(i)
                    count -= 1
    print('#{} '.format(t), end='')
    print(*result)