✔ 줄 세우기
문제 분석하기
학생들을 노드로 생각하고, 키 순서 비교 데이터로 엣지를 만든다고 생각했을 때 노드의 순서를 도출하는 가장 기본적인 문제
특히 답이 여러 개일 때 아무것이나 출력해도 된다는 전제는 위상 정렬의 결괏값이 항상 유일하지 않다는 알고리즘의 전제와 동일
손으로 풀어보기
- 인접 리스트에 노드 데이터를 저장하고, 진입 차수 배열값을 업데이트
- 진입 차수가 0인 노드를 큐에 저장
- 큐에서 데이터를 poll해 해당 노드를 탐색 결과에 추가하고, 해당 노드가 가리키는 노드의 진입 차수를 1씩 감소
- 감소했을 때 진입 차수가 0이 되는 노드를 큐에 offer
- 큐가 빌 때까지 반복
슈도코드 작성하기
N(학생 수) M(비교 횟수) A(데이터 저장 인접 리스트)
학생 수만큼 인접 리스트 초기화하기
진입 차수 배열 초기화하기
for(비교 횟수만큼 반복하기) {
인접 리스트 데이터 저장하기
진입 차수 배열 초기 데이터 저장하기
}
큐 생성하기
for(학생 수) {
진입 차수 배열의 값이 0인 학생(노드)을 큐에 삽입하기
}
while(큐가 빌 때까지) {
현재 노드 = 큐에서 데이터 poll
현재 노드값 출력하기
for(현재 노드에서 갈 수 있는 노드의 개수) {
타깃 노드 진입 차수 배열 --
if(타깃 노드의 진입 차수가 0이면) {
큐에 타깃 노드 추가하기
}
}
}
코드 구현하기
/**
* 2252) 줄_세우기
*/
public class D053_2252 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// N(학생 수)
int N = sc.nextInt();
// M(비교 횟수)
int M = sc.nextInt();
// A(데이터 저장 인접 리스트)
ArrayList<ArrayList<Integer>> A = new ArrayList<>();
// 학생 수만큼 인접 리스트 초기화하기
for (int i = 0; i <= N; i++) {
A.add(new ArrayList<>());
}
// 진입 차수 배열 초기화하기
int[] indegree = new int[N + 1];
for (int i = 0; i < M; i++) {
// 인접 리스트 데이터 저장하기
int S = sc.nextInt();
int E = sc.nextInt();
A.get(S).add(E);
// 진입 차수 배열 초기 데이터 저장하기
indegree[E]++;
}
// 큐 생성하기
Queue<Integer> queue = new LinkedList<>();
for (int i = 1; i <= N; i++) {
// 진입 차수 배열의 값이 0인 학생(노드)을 큐에 삽입하기
if (indegree[i] == 0) {
queue.offer(i);
}
}
while (!queue.isEmpty()) {
// 현재 노드 = 큐에서 데이터 poll
int now = queue.poll();
// 현재 노드값 출력하기
System.out.println(now + " ");
// 현재 노드에서 갈 수 있는 노드의 개수
for (int next : A.get(now)) {
// 타깃 노드 진입 차수 배열 --
indegree[next]--;
// 타깃 노드의 진입 차수가 0이면
if (indegree[next] == 0) {
// 큐에 타깃 노드 추가하기
queue.offer(next);
}
}
}
}
}
'Coding Test > 알고리즘 실전' 카테고리의 다른 글
[11726] 2xn 타일링 (0) | 2023.08.12 |
---|---|
[11050] 이항 계수 1 (0) | 2023.08.11 |
[1717] 집합의 표현 (0) | 2023.08.01 |
[1707] 이분 그래프 (0) | 2023.07.05 |
[1929] 소수 구하기 (0) | 2023.07.04 |