- 문제설명
- 예시
- 해결과정
문제파악
입력 그래프화
- 해당 예시에서 순위를 확정 지을 수 있는 선수는 2,5번 선수라고 명시되어 있다.
- 2번 선수의 입장에서 생각해보자. 1,3,4번 선수들이 이겼고 본인은 5번 선수를 이겼다. 순위는 4위이다.
- 5번 선수의 입장에서 생각해보자. 5번 선수는 모든 선수들에게 패배할 것이다. 순위는 5위이다.
- 순위를 특정할 수 없는 선수들을 생각해보자.
- 4번 선수의 경우 2,3,5번 선수들에게 무조건 승리하지만, 1번 선수와의 대결에서 승패를 장담할 수 없다.
- 3번 선수의 경우 2,5번 선수들에게 무조건 승리하고 4번 선수에게 패배하지만, 1번 선수와의 대결에서 승패를 장담할 수 없다.
- 1번 선수의 경우 2,5번 선수들에게 무조건 승리하지만 3,4번 선수들과의 대결에서 승패를 장담할 수 없다.
- 승패를 장담할 수 있는 조건이 무엇일까?
순위를 장담할 수 있는 조건
승패의 조건
- 2번 선수의 입장에서 보면 본인이 확실하게 이길 수 있는 상대는 5번, 확실하게 지는 상대는 1,3,4번 선수들이라는 사실을 주어진 경기결과를 통해 알 수 있다.
- 3번 선수의 입장에서 보면 본인이 확실하게 이길 수 있는 상대는 2,5번 선수들이고, 확실하게 지는 상대는 4번 선수이다.
- 여기서 포인트를 얻을 수 있었다.
- 내가 확실하게 이기는 상대가 몇 명인지, 확실하게 지는 상대가 몇 명인지 알면 그 사람들 끼리의 순위를 알 수 있다.
- 2번 선수의 경우, 자신을 제외한 모든 선수들의 승패 결과를 예측할 수 있다.
- 3번 선수의 경우, 1번 선수와의 접점이 없어 1번 선수를 제외한 선수들끼리의 승패 결과를 예측할 수 있다.
- 좋다! 그럼 본인을 이기는 선수가 총 몇 명인지 파악하고, 내가 이길 수 있는 선수가 총 몇 명인지 파악을해서 더한 숫자가 전체 선수의 숫자보다 1이 작으면 모든 선수들 사이에서 자신의 순위를 명시할 수 있는 것이다.
- 그렇다면 각각 몇 명인지 파악할 수 있는 방법이 뭐가 있을까?
방향 그래프 사용
- 나를 무조건 이기는 사람을 표현해야하고, 내가 무조건 이길 수 있는 사람을 표현해야하므로 관계가 섞여있는 무방향 그래프로는 문제를 풀 수 없다고 판단했다.
- 따라서 주어진 경기 결과를 바탕으로, 이긴 방향을 체크하는 그래프와 진 방향을 체크하는 그래프를 생성했다.
방향 그래프 사용
- 이렇게 서로 역방향을 가진 그래프를 하나씩, 총 두 개를 생성했다.
- 5번 선수부터 보자.
- 진 방향 그래프를 먼저 보면 5번 선수는 2번 선수에게 졌다.
- 그러면 2번 선수가 어떤 선수들에게 졌는지 판단해야 한다. 2번 선수는 1,3,4번 선수들에게 졌다.
- 1,3,4번 선수들은 또 누구에게 졌는지 판단해야 한다.
- 1번 선수는 지지 않았다.
- 4번 선수도 지지 않았다.
- 3번 선수는 4번 선수에게 졌다.
- 중복이 발생한다. 2번 선수도 4번 선수에게 졌고 3번 선수도 4번 선수에게 졌다.
- 생각했다. '아 5번 입장에서 무조건 지는 선수들의 번호를 중복 없이 파악하려면 HashSet을 사용해야겠군!'
- 결국 끝까지 타고 올라가면서 확인해야 하므로 dfs, bfs중 어떤걸 써도 상관이 없다고 판단했다.
- bfs선택!
- 진 방향 그래프에서 bfs를 돌고 나오면 5번 선수 입장에서 무조건 지는 선수들의 목록이 HashSet으로 반환이 된다.
- 반환된 HashSet은 {1,2,3,4}이다.
- 자 이제 반대로 이긴 방향 그래프를 보자.
- 5번 선수는 이긴 선수가 없다! 빈 HashSet이 반환될 것이다.
- 따라서 마지막에 두 개의 HashSet을 합치고, HashSet의 사이즈를 체크해보면 n-1, 즉 4이므로 통과이다.
- 메인문에서 모든 선수마다 이긴 방향 그래프, 진 방향 그래프에 대해서 각각 bfs를 돌려주고 결과로 나온 HashSet 두 개를 합친다. 합친 HashSet의 크기가 n-1 인 것이 총 몇 개인지 판단하면 문제 해결이다!
- 솔루션
import java.util.*;
class Solution {
public int solution(int n, int[][] results) {
ArrayList<Integer>[] posGraph = makePositiveGraph(n, results);
ArrayList<Integer>[] negGraph = makeNegativeGraph(n, results);
int answer = 0;
for(int i = 0; i < n + 1; i++) {
HashSet<Integer> posSet = bfs(i, posGraph);
HashSet<Integer> negSet = bfs(i, negGraph);
HashSet<Integer> allSet = new HashSet<>(posSet);
allSet.addAll(negSet);
if(allSet.size() == n-1) answer++;
}
return answer;
}
private ArrayList<Integer>[] makePositiveGraph(int n, int[][] results) {
ArrayList<Integer>[] posGraph = new ArrayList[n + 1];
for(int i = 0; i < n + 1; i++) posGraph[i] = new ArrayList<>();
for(int i = 0; i < results.length; i++) posGraph[results[i][0]].add(results[i][1]);
return posGraph;
}
private ArrayList<Integer>[] makeNegativeGraph(int n, int[][] results) {
ArrayList<Integer>[] negGraph = new ArrayList[n + 1];
for(int i = 0; i < n + 1; i++) negGraph[i] = new ArrayList<>();
for(int i = 0; i < results.length; i++) negGraph[results[i][1]].add(results[i][0]);
return negGraph;
}
private HashSet<Integer> bfs(int node, ArrayList<Integer>[] Graph) {
boolean[] visited = new boolean[Graph.length];
Queue<Integer> q = new LinkedList<>();
HashSet<Integer> set = new HashSet<>();
q.add(node);
visited[node] = true;
while(!q.isEmpty()) {
node = q.poll();
for(int a : Graph[node]) {
if(!visited[a]) {
visited[a] = true;
q.add(a);
set.add(a);
}
}
}
return set;
}
}
- 정리
- 무방향 그래프 문제만 풀다가 방향 그래프를 활용하는 방식으로 문제를 풀어봤다.