문제 링크

Java 문제풀이

Level3에 해당하는 그래프 문제이다.

입력

• int n
  • 권투 경기에 참가하는 총 인원
• int[][] results
  • 2차원 배열로 경기 결과가 주어짐
  • 각 행 {A, B}는 A 선수가 B 선수를 이겼다는 의미

출력

정확하게 순위를 매길 수 있는 선수의 수

풀이

문제를 보면 아래와 같은 설명이 있다.

"만약 A 선수가 B 선수보다 실력이 좋다면 A 선수는 B 선수를 항상 이깁니다."

때문에 A가 B를 이기고, B가 C를 이겼다면, A는 C를 무조건 이기게 된다.

문제를 풀 때 입력 parameter인 results 로 인접 행렬 또는 그래프를 초기화한 뒤, 위 조건을 따라 적절한 간선들을 추가해주면 된다.

아래 풀이는 DFS(solution1), 플로이드-와샬 알고리즘(solution2) 두가지 방법으로 풀어보았다.
플로이드-와샬 알고리즘을 사용한 것이 코드도 훨씬 간단하고 실행시간도 적게 걸리니 반드시 알고 넘어가도록 해야겠다.

package programmers.그래프.순위;

import java.util.ArrayList;
import java.util.LinkedList;

public class Solution {
    public static void main(String[] args) {
        int n = 5;
        int[][] results = {{4, 3}, {4, 2}, {3, 2}, {1, 2}, {2, 5}};
        System.out.println(solution2(n, results));
    }

    // dfs 활용
    public static int solution1(int n, int[][] results) {
        ArrayList<LinkedList<int[]>> adjList = new ArrayList<>(n + 1);
        for (int i = 0; i <= n; i++) {
            adjList.add(new LinkedList<>());
        }
        // win : 1, lose : 0
        for (int[] result : results) {
            adjList.get(result[0]).offer(new int[]{result[1], 1});
            adjList.get(result[1]).offer(new int[]{result[0], 0});
        }

        for (int i = 1; i <= n; i++) {
            boolean[] visited = new boolean[n + 1];
            dfs(adjList, visited, i, i);
        }

        int answer = 0;
        for (int i = 1; i <= n; i++) {
            if (adjList.get(i).size() == n - 1) {
                answer++;
            }
        }

        return answer;
    }

    public static void dfs(ArrayList<LinkedList<int[]>> adjList, boolean[] visited, int root, int cur) {
        if (visited[cur])
            return;
        else
            visited[cur] = true;

        LinkedList<int[]> rootAdj = adjList.get(root);
        LinkedList<int[]> curAdj = adjList.get(cur);
        if (root != cur) {
            boolean isContains = false;
            for (int[] edge : rootAdj) {
                if (edge[0] == cur) {
                    isContains = true;
                    break;
                }
            }
            if (!isContains) {
                rootAdj.offer(new int[]{cur, 1});
                curAdj.offer(new int[]{root, 0});
            }
        }

        int adjSize = curAdj.size();
        for (int i = 0; i < adjSize; i++) {
            int[] edge = curAdj.get(i);
            if (edge[1] == 1) {
                dfs(adjList, visited, root, edge[0]);
            }
        }
    }

    // Floyd Warshall 알고리즘 활용
    public static int solution2(int n, int[][] results) {
        boolean[][] adj = new boolean[n + 1][n + 1];
        for (int[] result : results) {
            adj[result[0]][result[1]] = true;
        }
        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (adj[i][k] && adj[k][j])
                        adj[i][j] = true;
                }
            }
        }

        int answer = 0;
        for (int i = 1; i <= n; i++) {
            int count = 0;
            for (int j = 1; j <= n; j++) {
                if (adj[i][j] || adj[j][i])
                    count++;
            }
            if (count == n - 1)
                answer++;
        }
        return answer;
    }
}

참고

• https://mungto.tistory.com/58 : 플로이드-워샬(c++) boolean 배열로 구현
• https://easybrother0103.tistory.com/131 : 플로이드-워샬(java) int 배열로 구현
• https://chanhuiseok.github.io/posts/algo-50/ : 플로이드-워샬 알고리즘 설명 (무방향 그래프)
• https://blog.naver.com/ndb796/221234427842 : 플로이드-워샬 알고리즘 설명 (방향 그래프)