[Algorithm]🐿️99클럽 코테 스터디 3일차 TIL : 백준 2660 회장뽑기

🔍문제

https://www.acmicpc.net/problem/2660

월드컵 축구의 응원을 위한 모임에서 회장을 선출하려고 한다. 이 모임은 만들어진지 얼마 되지 않았기 때문에 회원 사이에 서로 모르는 사람도 있지만, 몇 사람을 통하면 모두가 서로 알 수 있다. 각 회원은 다른 회원들과 가까운 정도에 따라 점수를 받게 된다.

예를 들어 어느 회원이 다른 모든 회원과 친구이면, 이 회원의 점수는 1점이다. 어느 회원의 점수가 2점이면, 다른 모든 회원이 친구이거나 친구의 친구임을 말한다. 또한 어느 회원의 점수가 3점이면, 다른 모든 회원이 친구이거나, 친구의 친구이거나, 친구의 친구의 친구임을 말한다.

4점, 5점 등은 같은 방법으로 정해진다. 각 회원의 점수를 정할 때 주의할 점은 어떤 두 회원이 친구사이이면서 동시에 친구의 친구사이이면, 이 두사람은 친구사이라고 본다.

회장은 회원들 중에서 점수가 가장 작은 사람이 된다. 회장의 점수와 회장이 될 수 있는 모든 사람을 찾는 프로그램을 작성하시오.

🤔발상

친구의 친구, 친구의 친구의 친구는 주어진 연결관계 내에서 경유를 통해 연결될 수 있는가를 물어보는 문제로 파악했습니다.
플로이드 워셜로 최단경로를 업데이트 하면 연결관계를 알 수 있고, 이를 이용해 가장 작은 점수, 그리고 그 점수에 해당하는 사람들을 찾으면 되며, 이를 위해 자료구조와 정렬이 필요합니다.

정렬 문제는 정렬이 문제의 핵심키워드일 경우엔 추가적인 시간복잡도, 공간복잡도 고려가 필요하지만 입력수가 50처럼 작은 경우에는 자바에서 기본적으로 제공하는 라이브러리나 스트림 등을 사용해도 큰 이슈 없이 해결되는 경우가 많습니다.

최적화를 위해선 다소 코드가 복잡해도 for문이나 배열을 이용해 직접 조작하는게 좋지만, 간단하게 해결할 수 있는 경우엔 쉬운 방법을 택하는 것도 괜찮은 전략입니다.

🔦입출력

최대 회원의 입력 수는 50이며 종료 입력을 받아 입력을 종료해야 합니다.
100 미만이므로 O(N ^ 3)에 적합합니다.

📃의사코드

- 데이터 입력받기
- 연결관계 업데이트(플로이드 워셜)
- 점수 계산
- 결과 출력(정렬된 결과)

👨‍💻코드

import java.util.*;
import java.util.stream.*;
import java.io.*;

public class Main {
  public static void main(String args[]) throws IOException {
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out))) {
            int n = Integer.parseInt(br.readLine());
            Election election = new Election(n);

            while (true) {
                String[] input = br.readLine().split(" ");
                int a = Integer.parseInt(input[0]);
                int b = Integer.parseInt(input[1]);
                if (a == -1 && b == -1) {
                    break;
                }
                election.addConnection(a, b);
            }

            election.floydWarshall();
            election.calculateScore();
            bw.write(election.getResult() + "\n");      
        }
  }
}

class Election {

    static final int INF = 10000000;

    int[][] graph;
    Candidate[] candidates;
    int minScore;
    int n;

    public Election(int n) {
        this.n = n;
        this.graph = new int[n + 1][n + 1];
        this.candidates = new Candidate[n + 1];
        this.minScore = INF;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i != j) {
                    graph[i][j] = INF;
                }
            }
        }
    }


    public void addConnection(int a, int b) {
        graph[a][b] = 1;
        graph[b][a] = 1;
    }

    public void floydWarshall() {
        for (int k = 1; k <= n; k++) {
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= n; j++) {
                    if (graph[i][j] > graph[i][k] + graph[k][j]) {
                        graph[i][j] = graph[i][k] + graph[k][j];
                    }
                }
            }
        }
    }

    public void calculateScore() {
        for (int i = 1; i <= n; i++) {
            int max = 0;
            for (int j = 1; j <= n; j++) {
                if (graph[i][j] < INF) {
                    max = Math.max(max, graph[i][j]);
                }
            }
            candidates[i] = new Candidate(max, i);
            minScore = Math.min(minScore, max);
        }
    }

    public String getResult() {
        StringBuilder sb = new StringBuilder();
        List<Candidate> list = Arrays.stream(candidates).filter(candidate -> {
            if (candidate == null) {
                return false;
            }
            return candidate.score == minScore;
        }).sorted().collect(Collectors.toList());

        sb.append(minScore).append(" ").append(list.size()).append("\n");
        for (Candidate candidate : list) {
            sb.append(candidate.number).append(" ");
        }
        return sb.toString().trim();
    }
}

class Candidate implements Comparable<Candidate> {

    int score;
    int number;

    public Candidate(int score, int number) {
        this.score = score;
        this.number = number;
    }

    @Override
    public int compareTo(Candidate o) {
        return this.number - o.number;
    }
}

🚀TIL

• 최저 점수인 사람들을 찾고 정렬하는게 번거로워 보여 별도 클래스를 만들고 Comparable을 구현하여 필터링, 정렬을 동시에 해결을 시도했습니다.
• 개인 IDE에선 java 17 을 사용하고 있는데, 문제 사이트는 java 11이다보니, 스트림 api의 toList() 메서드를 지원하지 않아(자바 16부터 지원) 컴파일 에러가 발생하는 이슈가 있었습니다.
• Try-with-resource 문법은 꽤 괜찮았으며, 반복문의 변수를 의미변수로 명명하는 것은 IDE를 사용할 땐 편리하지만 IDE 도움 없이 라이브코딩하는 경우 코드작성이 번거롭고 오타의 위험이 있어 안쓰는게 더 좋을 것 같습니다.