053 : 줄 세우기

ArrayList<ArrayList<Integer>>

- capacity를 별도로 정하지 않고

- 1~V번 new ArrayList<>()를 add한다

 

[]처럼 순차 pointer(i)가 없으므로, get(s)를 사용하여 access

그리고 add를 더함

 

또 순서가 있으므로 배열과 달리 단방향만 더해주면 된다

 

 

 

 

TP와 별도로 Field인 Queue가 필요

* 에지 가중치가 아닌, 에지 양 끝 노드의 순서이고 순서 정보는 indegree로 공급받으므로 pQ는 필요없다

 

*통상 OP시 개설해도 되지만, indegree가 0인것을 먼저 넣고 시작해야 하므로(sP) 미리 개설 후 sP 유입까지 끝내둔다

 

 

 

 

 

 

indegree가 0인 (동일 위상 내) 무더기 작업이 끝나고 다음 작업이 필요하므로 BFS를 사용한다(DFS와 대조하여)

 

sP는 위에서 작업했으므로, 바로 poll + 마킹 pair

 

다음 poll(now)이 진입하는 connected의 indegree를 하나씩 줄이다가, 0이 되면 진입(phaser)

 

*일반 탐색은 방문하지 않았을시

*"indegree를 줄임" + "0되면 방문"