Topology Sort (1) 썸네일형 리스트형 [백준/C++] 2252번 줄 세우기 (Topology sort) 문제 해석 문제 풀이 코딩테스트 준비하면서 위상 정렬은 알고 있어야지~ 싶어서 한 문제 풀려고 찾아본 문제이다. 위상 정렬이 기억나지 않아 푸는데 좀 헤맸다. 문제 풀이에 들어간 내 의식의 흐름은 아래와 같다. 우선 배열(인접행렬)로 생성하면 3만 x 3만으로 128MB는 훌쩍 넘어 터질 것 같아 인접리스트(adjacency list) 형태로 구현하였다. 만약 한 번도 누군가의 뒤에 선다는 정보가 없었던 사람이 있다면 모두 큐에 넣어주고 순서대로 출력하면 되겠다 싶었으나 (반례: 4,4 1->2 2->3 4->3 4->1 형태로 준다면 단순 bfs로는 해결할 수 없고 응용해야한다는 것을 알게 되었다. bfs에서 생기는 반례는 결국 내 이전 작업이 끝나지 않았는데 내가 먼저 queue에 들어가서 생기는 문.. 이전 1 다음
