sujae03   2년 전

dfs를 이용하여 위상정렬 하여 문제를 풀었습니다.


1. 먼저 풀면 좋은 조건에 따라 그래프를 만들어줍니다.

A B라면, A->B 될 수 있도록 방향 그래프 생성


2. 가장 어려운 문제인 N부터 가장 쉬운 문제인 1까지 차례대로 for문을 돌면서

2-1) 만약, 지금 가리키는 index 문제 번호보다 나중에 풀어야 할 것이 없다면 stack에 넣어주고,

2-2) 그렇지 않고 지금 가리키는 index 문제 번호보다 나중에 풀어야 할 것이 있다면 dfs함수로 점프합니다.


3. dfs함수에서는 위상정렬 알고리즘을 이용합니다.

A-> B

A-> C

우선, A->B 가 아닌 A->C (큰 값부터) 돌 수 있도록 내림차순 정렬을 해주고,

dfs를 돌며 위상정렬을 합니다.


이렇게 해서 제가 직접 test case 만들어보면서 실행했는데

어떠한 반례도 못찾겠습니다 ㅠㅠ


도와주세요


댓글을 작성하려면 로그인해야 합니다.