[Algorithm] 백준_2252번: 줄세우기

오늘의 문제는 🚀 백준 2252 줄세우기이다.

못풀었다. 어렵다. 위상 정렬을 공부하고 풀어보려고 했는데 메모리 초과, 시간초과…😂

테스트케이스 이해하기

주어진 순서들을 고려해서 줄을 세우면 된다. 여러가지 경우가 나온다면 그 중 하나를 프린트 하면 된다.

1차 시도 : 실패

어려운 문제가 아닌데 다른 방법이 왜 생각이 안나는지 모르겠다.

코테 볼때 이러면 멘붕이 올 것 같다.

1. 딕셔너리를 선언해서 입력값을 key, value로 저장해준다.

2. 큐를 선언해서 아직 방문하지 않았다면 dict의 key 값을 넣어준다.

3. 그리고 아직 방문 하지 않았다면, value들을 큐에 넣어준다.

4. 그리고 큐에서 나온 것들을 result에 넣어준다.

5. result의 값들을 반대로 빼준다.

   하지만 결과는 실패!

from collections import deque
from collections import defaultdict
n,m = map(int, input().split())

a=[list(map(int,input().split())) for _ in range(m)]
check=[0]*n
result = []
dict = defaultdict(list)

#딕셔너리 채우기
for i in range(m):
    if not a[i][1] in dict:
        dict[a[i][1]] = [a[i][0]]

    else:
        dict[a[i][1]].append(a[i][0])


q = deque()
# print(dict)
for k in list(dict):
    if check[k-1] == 0 and len(result) != n :
        q.append(k)
        while q:
            val = q.popleft()
            for i in range(len(dict[val])):
                if check[dict[val][i]-1] == 0:
                    check[dict[val][i]-1] = 1
                    q.appendleft(dict[val][i])
            result.append(val)

# print(result)
for i in range(len(result)-1,-1,-1):
    print(result[i], end=" ")

🚀Reference: 백준 2252 줄세우기