일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | |
7 | 8 | 9 | 10 | 11 | 12 | 13 |
14 | 15 | 16 | 17 | 18 | 19 | 20 |
21 | 22 | 23 | 24 | 25 | 26 | 27 |
28 | 29 | 30 | 31 |
- 포이마웹
- 백준알고리즘
- 다이나믹프로그래밍
- 리액트댓글기능
- 백준골드
- 리액트
- 익스프레스
- 프로그래머스JS
- 알고리즘
- 백준nodejs
- 자바스크립트
- CSS
- HTML5
- 코테
- 안드로이드 스튜디오
- css기초
- JS
- 백준구현문제
- 코딩테스트
- 백준구현
- 프로그래머스코테
- JS프로그래머스
- 백준js
- 몽고DB
- 리액트커뮤니티
- 프로그래머스
- 백준
- dp알고리즘
- js코테
- HTML
- Today
- Total
개발새발 로그
[JS] 백준 2252번 : 줄세우기 - 그래프이론, 위상정렬, 큐 본문
https://www.acmicpc.net/problem/2252
2252번: 줄 세우기
첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의
www.acmicpc.net
이전에 포스팅했던 위상정렬의 문제다
https://ydoag2003.tistory.com/43
위상 정렬
위상정렬 순서가 정해져있는 작업을 차례로 수행해야할 때 그 순서를 결정하기 위해 사용하는 알고리즘 위상정렬을 통해 여러개의 순서를 조건에 부합하는 일직선의 순서로 만든다. 배고픔 ->
ydoag2003.tistory.com
📋풀이방법
1. 연결되어있음을 표현할 graph배열과 간선의 정보를 표현할 indegrees배열을 선언한다
-graph배열은 인덱스를 기준으로 연결되어있는 값을 그 안에 누적한다.
ex) graph[1]에 [3,4]가 들어있다면 1 - 3, 1 - 4 와 같이 연결되어있음
-indegrees배열은 인덱스를 기준으로 연결되어있는 값의 갯수를 뜻함
ex)위 예시를 기준으로 indegress[1]에는 2가 들어있다.
2. 주어진 학생의 번호 A와 B를 graph[a]에 B값을 누적한다.
->graph[A]에 넣는 이유는 A가 키가 작으므로 앞에 오니까 queue를 이용할 때 앞에서 부터 값을 빼므로 graph[A]에 B값을 넣는다.
3. 학생의 A와 B의 비교 값을 graph에 기록하면서 indegress[B] 값을 +1해준다.
-> A가아닌 indegress[B] 값을 +1하는 이유는 위상정렬은 진입차수가 0인 것을 기준으로 풀이하므로 [ 1 - 3 ]에서 3에 진입차수가 +1된것이다. 그래야 위에서 말했듯이 작은 키 순서대로 출력이된다.
4. 모든 정보를 기록하고 indegress의 값이 0인 인덱스를 찾아서 queue에 넣어준다
->진입차수가 0인 인덱스들이 순서가 먼저임을 뜻하므로 queue에 넣어준다.
5.queue에서 하나씩 빼면서 뺀 인덱스 값은 정답에 기록한다
6. queue에서 뺀 인덱스에 연결된 노드들을 순회한다.
7. 그 노드들의 연결된 간선을 제거한다. ->진입차수를 빼줌
8. 제거하면서 만약 제거된 노드의 indegrees값이 0이 됐다면 queue에 그 노드를 넣어준다.
9. 넣어준 노드는 다음 순서가 된다.
10. 이를 queue가 빌 때까지 반복한다.
🤟내 제출
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim();
input = input.replace(/\r/g, "").split("\n");
let [N, M] = input[0].split(" ").map(Number);
let arr = [];
let queue = [];
let answer = [];
for (var i = 0; i < M; i++) {
arr[i] = input[i + 1].split(" ").map(Number);
}
const graph = Array.from({ length: N + 1 }, () => Array().fill(0));
const indegrees = Array(N + 1).fill(0);
for (let i = 0; i < M; i++) {
let [a, b] = arr[i];
graph[a].push(b);
indegrees[b]++;
}
for (let i = 1; i < N + 1; i++) {
if (indegrees[i] == 0) queue.push(i);
}
while (queue.length) {
let x = queue.shift();
answer.push(x);
for (let next of graph[x]) {
indegrees[next]--;
if (indegrees[next] == 0) queue.push(next);
}
}
console.log(answer.join(" "));
'알고리즘 > 그래프 이론' 카테고리의 다른 글
[JS] 백준 1520번 : 내리막 길 - 구현, 그래프이론, DFS, 다이나믹프로그래밍(DP) (0) | 2023.08.16 |
---|---|
[JS] 백준 1916번 : 최소비용 구하기 - 그래프이론, 다익스트라 (0) | 2023.08.13 |
[JS] 백준 1717번 - 집합의 표현 - [런타임 에러 (EACCES)], 자료구조, 분리집합, 서로소집합 알고리즘, 그래프이론 (0) | 2023.08.10 |
[JS] 백준 11404번 : 플로이드 - 그래프이론, 플로이드-와샬 (0) | 2023.08.05 |
[JS] 백준 2206 : 벽 부수고 이동하기 - 그래프, 이론그래프, 탐색너비 우선 탐색 (0) | 2023.08.03 |