커뮤니티
포인트
쿠폰
내 강의실
국비 신청 내역
증명서
계정
로그아웃
학습 질문
개발 일지
나의 활동
답변 완료
위상정렬 관련
[스킬업] 실무에 바로 쓰이는 알고리즘 by Python
기타
북마크
현*람
댓글
2
추천
0
조회수
6
조회수
6
답변 완료

* 겪고 있는 문제 상황을 최대한 자세하게 작성해주세요.

* 문제 해결을 위해 어떤 시도를 해보았는지 구체적으로 함께 알려주세요.



위상정렬을 구현했는데 chatGPT가 처음에 큐에 넣을때 차수가 0인걸 전부 다 넣으라는데 이유를 잘 모르겠습니다;;

제 생각엔 chatGPT가 거짓말을 한것 같은데 한번 코드 보고 확인 부탁드리겠습니다.





#위상정렬
N = int(input())
E = int(input())
nodes = [[0,[]] for i in range(N + 1)]
queue = [] # 노드번호, 진출할 노드들
added = [0 for _ in range(N + 1)] # 큐에 중복 등록 방지
# 노드별 가져야 하는 정보 - 진입차수개수, 추가된 순서, 노드번호, 진출할 노드들
# 진입차수가 0인 아이를 큐에 추가 하며, 연결된 노드들에 진입차수를 줄임. -> 큐가 없을 때까지 반복
for _ in range(E):
    s, e = map(int, input().split())
    nodes[s][1].append(e)
    nodes[e][0] += 1
    # 진입차수가 0인 노드 선택, 하며 동일 노드가 처음에 중복 등록되는것 방지
    if(nodes[s][0] == 0 and added[s] == 0):
        # 챗GPT가 한개만 넣는게 아니라 다 넣으라는데 이유를 모르겠음
        queue.append([s, nodes[s][1]])
        added[s] = 1
while queue:
    idx, childs = queue.pop(0)
    print('방문', idx)
    for child in childs:
        cn = nodes[child] 
        cn[0] -= 1
        if(cn[0] == 0):
            queue.append([child, cn[1]])
            added[child] = 1


예시 입력

7

8

1 2

1 5

2 3

2 6

3 4

4 7

5 6

6 4

취소
 공유
취소
댓글 0
댓글 알림
나의얼굴