키 순서
📚 문제 설명
1번부터 N번까지 학생이 있다.
학생들의 키를 비교한 값이 주어졌을 때, 자신의 키가 몇등인지 아는 학생은 몇명인가?
예를 들어
- 1번 학생의 키 < 5번 학생의 키
- 3번 학생의 키 < 4번 학생의 키
- 5번 학생의 키 < 4번 학생의 키
- 4번 학생의 키 < 2번 학생의 키
- 4번 학생의 키 < 6번 학생의 키
- 5번 학생의 키 < 2번 학생의 키
라고 한다면, 4번은 자신의 키와 다른 모든 학생의 키를 비교할 수 있기 때문에 몇등인지 확인할 수 있다.
그러나 한가지 예시로 1번과 3번의 경우 서로 비교할 수가 없기 때문에 몇등인지 알 수 없다.
자세한 문제 설명은 문제 링크 확인
👨🏻💻 풀이 과정
이 문제의 경우 처음에는 DFS를 이용해 풀었고 그 후 플로이드 워셜 방식으로 풀었기 때문에
그 순서대로 하나씩 설명하고자 한다.
💡1차 제출 코드 (DFS)
자신의 등수를 알기 위해서는 해당 노드에서 몇번을 거치든 모든 노드와 연결이 되어있어야 한다.
이 생각을 기본으로 DFS문을 생각하면 된다.
1차 제출에서 사용한 로직의 원리는 트리를 정방향으로 한번, 역방향으로 한번 모든 노드를 확인하여
해당 노드의 번호 i에 해당하는 TreeCounter[i] 값을 +=1 을 했을 때
만약 모든 노드와 연결된 노드의 경우 TreeCounter[i] 의 값이 N 일 것이다.
전체 로직을 순서대로 설명하면 더 간단하다.
- DFS문을 이용해 정방향 트리의 각 노드 확인.
TreeCounter갱신.
- DFS문을 이용해 역방향 트리 각 노드 확인.
TreeCounter갱신.
TreeCounter[i]가N보다 큰 경우를 리턴.
DFS 이용 코드
let input = require("fs").readFileSync(0, 'utf-8').toString().trim().split("\n");
const [N, M] = input.shift().split(' ').map(Number);
input = input.map(v => v.split(' ').map(Number));
// 정방향 트리
let GoStraight = Array.from({length: N}, _ => []);
// 역방향 트리
let GoReverse = Array.from({length: N}, _ => []);
// 연결된 노드 갯수를 저장 할 배열.
let TreeCounter = Array.from({length: N}, _ => 0);
// 트리 생성.
input.forEach(v => {
const [Start, End] = v;
GoStraight[Start - 1].push(End);
GoReverse[End - 1].push(Start);
});
// DFS 함수.
const DFS = (now, lines, visited) => {
TreeCounter[now] += 1;
// 연결을 확인하며 재귀.
for (let i = 0; i < lines[now].length; i++) {
const NEXT = lines[now][i] - 1;
// 이미 왔던 경우를 제거하기 위해.
if (!visited[NEXT]) {
visited[NEXT] = true;
DFS(NEXT, lines, visited);
}
}
};
// 메인 함수.
const solution = (lines) => {
for (let i = 0; i < N; i++) {
let visited = Array.from({length: N}, _ => false);
visited[i] = true;
DFS(i, lines, visited);
}
};
// 정방향 진행
solution(GoStraight);
// 역방향 진행
solution(GoReverse);
// 정답 출력.
console.log(TreeCounter.filter(v => v > N).length);
💡2차 제출 코드 (Floyd-Warshall)
이렇게 제출한 뒤 플로이드워셜 방식으로도 풀 수 있다는 사실을 알게 되었다.
아직 한 번도 플로이드워셜 알고리즘을 사용해 본 적이 없어서 이번 기회에 한번 사용하고 싶어서 다시 풀었다.
이 문제의 트리 그림을 통해 Floyd-Warshall 알고리즘을 설명하겠다.
5에서 2로 가는 경우를 검사할 때,
기본적으로 5에서 바로 2로 가는 경우가 있다.
5 -> 2
그런데 여기서 중간 지점인 4를 검사하는 것이다.
5 -> 4 -> 2
이렇게 중간에 하나를 거치고 가는 것을 통해 5에서 6으로 가는 경우도 계산할 수 있다.
5 -> 4 -> 6
Floyd-Warshall 알고리즘은 이렇게 중간을 거치는 겅우를 계산하는 방식이다.
전체적인 로직은 이렇게 구성했다.
table을 이용해 노드의 연결 관계를 저장. (boolean)record를 이용해 각 노드와 연결된 노드의 갯수를 저장. (Number)- 시작 지점
j, 중간 지점i, 끝 지점k를 3중 for문으로 확인.- 만약
j->i->k가 가능하면table[j][k] = true;
- 만약
- 2중 for문으로
table을 돌며 확인.- i -> j 가 가능하거나 j -> i 가 가능하면 (역방향도 고려하기 위해)
record[i] += 1
record를 확인하여 정답 출력.
let input = require("fs").readFileSync(0, 'utf-8').toString().trim().split("\n");
const [N, M] = input.shift().split(' ').map(Number);
input = input.map(v => v.split(' ').map(Number));
// 연결 관계 확인용 배열.
let table = Array.from({length: N}, _ => Array.from({length: N}, _ => false));
// 연결된 노드의 갯수를 저장할 배열.
let record = Array.from({length: N}, _ => 0);
// 1차 연결 체크.
input.forEach(v => {
const [Start, End] = v;
table[Start - 1][End - 1] = true;
});
// j -> i -> k 연결 확인.
for (let i = 0; i < N; i++) {
for (let j = 0; j < N; j++) {
for (let k = 0; k < N; k++) {
if (table[j][i] && table[i][k]) {
table[j][k] = true;
}
}
}
}
// 연결된 노드 갯수 갱신.
for (let i = 0; i < N; i++) {
for (let j = 0; j < N; j++) {
if (table[i][j] || table[j][i]) {
record[i] += 1;
}
}
}
// 정답 출력.
console.log(record.filter(v => v >= N - 1).length);
🧐 후기
개인적으로 3중 for문에 대한 거부감 때문에 Floyd-Warshall 코드 구현이 어려웠고 특히나 마지막 2중 for문으로 테이블을 확인해야하는 부분도 머리속에서 생각하기가 힘들었다. 만약 나와 같은 사람이 있다면, 한번 table 배열을 출력해서 직접 눈으로 확인하며 트리 그림과 함꼐 확인하면 이해하기 좀 더 편할 것이다.
