[S/W 문제해결 응용] 10일차 - 작업순서 Python (SW Expert Academy)

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

SW Expert Academy

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개 정수를 공백을 사이에 두고 나열하는 것이다.

 

2. 코드

코딩을 배운지 얼마 안되서 푼 문제입니다. 기억상 dfs 같은 방법을 잘 못써서 반복문을 통해 풀게되었던 것 같네요.

다시보니 수정하고 싶은 부분이 정말 많아서 조금 고친 것이지만 처음부터 다시하는 것이 깔끔할 것 같긴하네요. 의미없는 배열도 좀 만드는 것 같지만 저렇게 안하면 반복문으로 할 수가 없는 것 같아서... 여러 방법을 배우는 것 같습니다.

 

아래가 작성한 코드입니다.

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()))
    # 각 노드 번호 다음에 할 수 있는 작업을 저장
    for i in range(0, len(temp_list), 2):
        a = temp_list[i]
        b = temp_list[i+1]
        graph[b].append(a)
    # 결과를 저장할 리스트
    result = []
    # 노드를 결과값에 저장했는지 확인할 리스트
    do_list = [i for i in range(1, v+1)]
    count = v
    while count:
        for idx, i in enumerate(do_list):
            # 선행 노드가 실행되었는지 확인
            for j in graph[i]:
                if visited[j]:
                    break
            else:  
                # 선행노드가 모두 수행되었으면 실행
                # 노드가 실행된 것을 표시
                visited[i] = False
                result.append(i)
                count -= 1
                # 결과값에 저장한 노드는 삭제
                do_list.pop(idx)
                break
    print('#{} '.format(t), end='')
    print(*result)