출처
해당 게시글은 [Java] 어서와! 자료구조 알고리즘은 처음이지?https://programmers.co.kr/learn/courses/13577를 간략히 요약한 게시글이며 모든 출처는 해당강의에 있습니다
문제
문제 분석
정확한 순위를 알 수 있는 선수의 수를 구하는 문제입니다. 구하기에 앞서 정확한 순위를 알 수 있는 기준을 먼저 생각해보고 문제에 접근해야 합니다.
순위가 높은 선수는 순위가 낮은 선수에 대해 항상 이깁니다.(2위는 4위를 무조건 이김)
3위가 4위를 이기고 4위가 6위를 이긴다면 3위는 5위와 6위와의 경기에도 항상 이깁니다.
풀이
나의 풀이
문제에서 설명하는 정확한 순위를 알 수 있는 선수는 어떤 기준을 충족해야 하는지 생각해내지 못하였었습니다.
단순히 BFS로 풀어서 해결하려 하였지만, BFS를 사용하더라도 노드들 간의 비교는 하여야 했었습니다.
강의의 풀이
import java.util.*;
class Node{
int n;
int win = 0, lose = 0; //승, 패
boolean visit = false;
List<Node> links = new LinkedList<>();
Node(int n) {this.n = n;}
}
class Solution {
public int solution(int n, int[][] results) {
//A가 B를 이기고 B가 C를 이기면 A는 C를 이긴것과 마찬가지
//각 노드마다 BFS를 수행
//제대로 알 수 있는 선수 : 승 + 패 == 선수수 - 1
List<Node> list = new ArrayList<>();
for(int i =0; i<n; i++) list.add(new Node(i+1));
for(int[] result : results){
Node winner = list.get(result[0] - 1);
Node loser = list.get(result[1] - 1);
winner.links.add(loser); //방향성을 가지므로 한쪽만
}
for(Node winner : list){
//BFS
for(Node node : list) node.visit = false;
Queue<Node> queue = new LinkedList<>();
winner.visit = true;
queue.offer(winner);
while(!queue.isEmpty()){
Node now = queue.poll();
for(Node loser : now.links){
if(loser.visit) continue;
loser.visit = true;
winner.win += 1;
loser.lose += 1;
queue.offer(loser);
}
}
}
//제대로 알 수 있는 선수 : 승 + 패 == 선수수 - 1
int answer = 0;
for(Node node : list){
if(node.win + node.lose == n - 1) answer++;
}
return answer;
}
}강의에서는 2가지의 원리를 핵심으로 짚고 넘어갔었습니다.
- A가 B를 이기고 B가 C를 이기면 A는 C를 이긴다.
- 정확한 순위를 알수 있는 선수는 승,패가 선수의 수 - 1이다.
선수의 순위에 따라 순위는 항상 높으면 승, 낮으면 패하는것이 참이어야 한다는 뜻이므로 경기기록이 없더라도 결과를 유추할 수 있습니다.
그리고 자기자신을 제외한 모든 선수와 1번씩 경기를 했다면, 전체 선수의 수 - 1이 되므로 순위가 확실하게 됩니다.(자기자신과 경기는 할 수 없으므로)
선수의 정보를 가지고있는 Node 객체는 선수번호와 승리횟수 win 패배횟수 lose 변수를 가집니다.
모든 선수끼리 비교해야 하므로 BFS를 이용하지만, 여태 해온 것과는 다르게 모든 선수를 한번씩 비교해야 하므로(모든 선수를 루트로 세워봐야 하므로) 반복문을 한번 더 감싸 줍니다.
같은 끼리 경기를 2번 이상 하는 경우가 없으므로 선수의 수 - 1만큼 경기를 치르게 되면 모든 선수와 경기를 치르고 순위는 고정되게 됩니다.
GitHub
