[BOJ/solved.ac] [Python] 14567 선수 과목

14567번: 선수과목 (Prerequisite) (acmicpc.net)

14567번: 선수과목 (Prerequisite)

 

문제

선수 과목이 존재하는 과목을 포함한, 모든 과목에 대해 각 과목을 이수하려면 최소 몇 학기가 걸리는지 계산
(한 학기에 들을 수 있는 과목 수에는 제한이 없고 모든 과목은 매 학기 항상 개설됨)

 

예제

# 입력
'''
N M
A B (A번 과목이 B번 과목의 선수과목, A < B인 입력만 주어짐)
'''
6 4
1 2
1 3
2 5
4 5

# 출력
1 2 2 1 3 1

---

최초 풀이

# 42588 KB / 592ms
# 입력 받기
import sys
new_input = sys.stdin.readline
N, M = map(int, new_input().split())

# 각 과목별 선수과목 목록 채워줄 리스트
match = [[] for _ in range(N+1)]

# 과목을 들을 수 있는 최소 학기
min_time = [1]*(N+1)

# match에 선수과목 목록 채워주기
for _ in range(M):
    before, after = map(int, new_input().split())
    match[after].append(before)
    
# min_time의 각 요소에 대해 최소 학기가 가장 큰 값 찾아서 1을 더해줌
for i in range(1, N+1):
    if match[i]:
        max_time = [min_time[j] for j in match[i]]
        min_time[i] = max(max_time)+1
        
print(*min_time[1:])

---

해설

match 리스트는 각 과목(인덱스)별 선수과목 목록을 나타낸다. 인덱스 번호와 과목 번호를 맞춰주기 위해 길이를 (N+1)로 설정해줬다.

min_time 리스트는 각 과목(인덱스)별 이수에 걸리는 최소 학기를 나타낸다. match 리스트와 마찬가지로 인덱스 번호와 과목 번호를 맞춰주기 위해 길이를 (N+1)로 설정해줬다. 선수과목이 없을 경우, 이수에 걸리는 최소 학기가 1이므로 값을 1로 초기화해주었다.

 

i 가 1일 때는 선수 과목이 없으므로 아무 변화가 없다. i가 2, 3일 때는 선수과목이 1로 존재하므로 값이 1+1 = 2가 된다. i가 5일 때는 선수과목이 2개이므로 둘 중 이수에 걸리는 최소 학기가 큰 값에 1을 더해줘야 한다. 따라서 2+1 = 3이 된다. 선수과목의 번호는 후이수 과목 번호보다 작으므로 for문을 한 번만 사용해주면 된다.

---

최적화

# 42592 KB / 500 ms
# 코드를 함수 안에 넣어줌

def find_min():
    import sys
    new_input = sys.stdin.readline
    N, M = map(int, new_input().split())
    match = [[] for _ in range(N+1)]
    min_time = [1]*(N+1)

    for _ in range(M):
        before, after = map(int, new_input().split())
        match[after].append(before)

    for i in range(1, N+1):
        if match[i]:
            max_time = [min_time[j] for j in match[i]]
            min_time[i] = max(max_time)+1

    return min_time[1:]

print(*find_min())

 

참고

# 42592 KB / 528 ms
# min_time에 pop 사용해 인덱스 0인 값 삭제
def find_min():
    import sys
    new_input = sys.stdin.readline
    N, M = map(int, new_input().split())
    match = [[] for _ in range(N+1)]
    min_time = [1]*(N+1)

    for _ in range(M):
        before, after = map(int, new_input().split())
        match[after].append(before)

    for i in range(1, N+1):
        if match[i]:
            max_time = [min_time[j] for j in match[i]]
            min_time[i] = max(max_time)+1
    
    min_time.pop(0)
    return min_time

print(*find_min())


# 42712 KB / 524 ms
# deque 사용
def find_min():
    import sys
    from collections import deque
    new_input = sys.stdin.readline
    N, M = map(int, new_input().split())
    match = [[] for _ in range(N+1)]
    min_time = deque([1]*(N+1))

    for _ in range(M):
        before, after = map(int, new_input().split())
        match[after].append(before)

    for i in range(1, N+1):
        if match[i]:
            max_time = [min_time[j] for j in match[i]]
            min_time[i] = max(max_time)+1
    
    min_time.popleft()
    return min_time

print(*find_min())