[알고리즘] 순위 (프로그래머스 Level3)

코딩테스트 연습 - 순위

 그래프 탐색 문제이다. 순위라고 했으므로 현재 그래프 내에서의 각 노드들의 위치를 알아내야 하는 문제이다. 즉, 각 선수마다 해당 선수보다 강한 선수 + 약한 선수의 수를 구해서 합쳐서 n이 된다면 랭킹을 정확하게 구할 수 있는 선수이다.

 예전에도 비슷한 문제를 풀어본 기억이 있는데 'DFS + 역그래프 + DP + Set'을 적절히 활용하면 쉽게 풀 수 있다.

 

Solution

 예시 input을 단방향 그래프로 그린 모습이다. 보다시피 2번 선수 뒤에는 1, 3, 4번, 앞에는 5번 선수가 있으므로 다른 모든 선수와의 관계를 명확히 할 수 있다. 5번 또한 본인 뒤에 1, 2, 3, 4번이 다 있기에 관계가 명확하다.

 하지만 1번과 4번, 1번과 3번은 서로 간의 관계가 불분명한 상황이다.

 

 우선 DFS의 특성상 나보다 앞에 있는 노드들의 개수는 구할 수 있다. 하지만 나보다 뒤에 있는 노드를 구하긴 쉽지 않다. 그렇다면 그래프 edge들의 방향을 거꾸로 해서 한 번 더 탐색하면 된다.

 즉, 정방향 그래프 탐색 1번 + 역방향 그래프 탐색 1번을 하면 각 노드마다 앞 뒤에 있는 노드들의 개수를 다 구할 수 있다. 이 때, 앞 뒤 노드들의 개수를 보관하는 저장소는 반드시 Set을 써야지 중복이 일어나지 않는다.

import java.util.*;


class Solution {

	ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
	ArrayList<ArrayList<Integer>> reverse_graph = new ArrayList<>();

	HashSet[] hashSets1, hashSets2;


	public int solution(int n, int[][] results) {
		int answer = 0;

		//[i]번보다 약한 선수들
		hashSets1 = new HashSet[n+1];
		//[i]번보다 강한 선수들
		hashSets2 = new HashSet[n+1];

		for(int i = 0;i <= n;i++)
		{
			hashSets1[i] = new HashSet();
			hashSets1[i].add(i);

			hashSets2[i] = new HashSet();
			hashSets2[i].add(i);

			graph.add(new ArrayList<>());
			reverse_graph.add(new ArrayList<>());
		}

		for(int i = 0;i < results.length;i++)
		{
			graph.get(results[i][0]).add(results[i][1]);
			reverse_graph.get(results[i][1]).add(results[i][0]);
		}

		boolean[] visited = new boolean[n+1];
		boolean[] visited2 = new boolean[n+1];

		for(int i = 1;i <= n;i++)
		{
			if(!visited[i])
				dfs(i, visited, graph, hashSets1);

			if(!visited2[i])
				dfs(i, visited2, reverse_graph, hashSets2);

			if(hashSets1[i].size() + hashSets2[i].size() == n + 1)
				answer++;
		}

		return answer;
	}

	public HashSet<Integer> dfs(int now, boolean[] visited, ArrayList<ArrayList<Integer>> graph, HashSet[] hashSets)
	{
		visited[now] = true;

		for(int i = 0;i < graph.get(now).size();i++)
		{
			int next = graph.get(now).get(i);

			if(!visited[next])
			{
				hashSets[now].addAll(dfs(next, visited, graph, hashSets));
			}
			else
			{
				hashSets[now].addAll(hashSets[next]);
			}
		}

		return hashSets[now];
	}
}