[ Baekjoon - 10/02 ] - 2610번: 회의준비

• 문제 링크 : https://www.acmicpc.net/problem/2610

2610번: 회의준비

 

• 소요 시간 : 2시간

 

1. 문제를 읽고 이해하기
   • 제한
     • 시간 : 1초
     • 메모리 : 128MB
   • 문제
     • 회의에 참석하는 사람의 수(1≤N≤100), 서로 알고있는 관계의 수 M (관계이니까 최대 N-1개임)
     • 서로 알고있는 사람은 같은위원회에 속해야하고, 위원회의 수는 최대가 되어야함
     • 위원회마다 대표가 한명씩 있는데 각 위원회 회원들이 대표에게 의견전달이 가장 효율적으로 될수있도록 대표를 선정하는 문제
   • 이해
     • 서로알고있는 사람은 같은 위원회이도록, 주변인맥을 통해도 모르는 사람은 다른 위원회이도록 위원회를 구성(==위원회의 수가 최대가 됨)하고, 각 위원회 일원 중 관계가 가장 많고, 만약 관계수가 같다면 가장 인맥을 덜 거쳐 올 수 있는 일원이 대표가 되면된다.
2. 문제를 익숙한 용어로 재정의와 추상화

   • 

   • 입력예시 형태와 문제예시를 그려보며 이해했다.
   • 처음엔 위원회수는 당연히 결정되는데 왜 최대가 되어야한다고 조건을 준건지 이해가 안되서 고민했다.
   • 결국은, 모르는사람 아는 사람을 다 한 위원회에 넣어버리면, 아는사람끼리는 같은 위원회가 되었으니 조건이 만족될 수 있어서, 아는사람만 같은위원회가 되도록 조건을 저렇게 줬다는 것을 깨달았다. (국어가 어렵네..)
3. 문제를 어떻게 해결할 것인가

   • 

   • 우선 입력예시를 이용해 위원회를 설립하기 전의 상황을 그려보았다. (1~8번의 사람과 각 관계)
   • 관계가 이어지지않으면 다른 위원회이도록 그룹을 묶어보았다 (1~3, 4~7, 8)
   • 첫번째 위원회그룹의 경우 2번이 가장 많은 관계를 가졌으므로 2번이 대표가 된다
   • 두번째 위원회그룹의 경우 4,6번이 가장 많은 관계이고 각각 본인을 제외한 모두와 연결되어있어 둘다 가능하다.
     만약 둘다 2명씩만 연결되어있다면 가장 인맥을 덜 통해 갈수있는 일원을 선택해야할 것이다. (최단거리)
   • 세번째 위원회그룹의 경우 1명뿐이므로 8번이 대표가 된다.
   • 그리고 아마 눈치챘겠지만, 위 자료구조는 위원회 일원이 노드이고 관계가 양방향 간선인, 양방향 그래프 형태이다.
   • 1st 접근 - 인접리스트와  이를 탐색할 BFS, 최단경로를 구할.. 알고리즘 )
     • 위 그림처럼 인접리스트로 구현하면 최대 인맥을 가진 일원을 고를 수 있다 생각하여 이를 선택했다.
     • 인접리스트는 BFS를 활용하여 위원회 그룹을 나눌 수 있고, 각 리스트의 사이즈가 인맥의 수 이므로 최댓값을 고르면 된다. (블로그 쓰면서 생각해보니.. 인맥의 수가 최대가 아니어도 가능할 수도 있을 것 같다.. 좀더 생각해봐야지)
     • 최대 인맥을 가진 일원을 골랐을때 1명이면 바로 답이겠지만, 1명이 아니라면 둘중 누가 더 인맥을 덜 통해서 대표와 소통할 수 있을지 선택해야한다.  
     • 플로이드 알고리즘을 생각하긴했지만, N의3승이라는 아주 거대한 시간복잡도를 가져서 전체를 플로이드로 돌리는 것보단, 최대인 사람들만 구하면 좀더 효율적이지 않을까 생각했다
     • 구현력이 부족해서(...) 구현은 못했다..ㅋㅋ 그렇지만 다시 생각해보니 위 방법으로는 답이 나오지 않을것같긴하다..
   • 2nd 접근 - 인접행렬과 이를 탐색할 DFS, 최단경로를 구할 플로이드 알고리즘)
     •  플로이드 알고리즘 자체가 모든 노드에 대해 최단경로를 구하는 식이므로, 인접리스트보다는 인접행렬이 적합하다.
     • 여기서 DFS는 최단경로를 구하기 위함이 아니라 위원회(그룹)을 나누기 위함이므로 끝까지 가는 DFS를 선택했다.
     •  최단경로는 모든 회원들간(자신과 자신은 제외) 구하면되므로 전체를 플로이드로 돌려주면 된다. 
   • 3rd 접근 - 인접행렬과 최단경로를 구할 플로이드 알고리즘, 그리고 BFS를 활용한 대표뽑기)
     • 분명 플로이드 알고리즘이 아닌 다른 알고리즘을 쓰고싶어서 좀더 생각해보았는데.. 결국은 플로이드를 활용했지만 뒤에서 좀 더 줄일수있는 방법을 생각하게된것같다...ㅎㅎ 
       혹시나해서.. 위 문제를 검색해봤지만 플로이드를 쓰지않은 방법은 보이지 않았다..ㅜㅠ 
     • 첫번째 접근에서 인접리스트가 인접행렬로 바뀌었을 뿐이지만.. 그래도 좀더 코드가 간결해진것같아 만족한다!
4. 위 계획을 검증
   • 두번째 접근의 경우 사실상 완탐이라 크게 검증은 필요해 보이지 않는다.
5. 계획 수행 (실제코드 작성)
   1. Java 11

      • import java.io.*;
        import java.util.*;
        
        public class Main {
            static final int MAX_VALUE = 1000000000; // 정수 최댓값을 넣어두면 오버플로우로 연산이 이상해질 수 있음
            static int N, M;
            static int[][] dist;
            static int[] mdist;
            static PriorityQueue<Integer> pq;
        
            public static void main(String[] args) throws IOException {
                //System.setIn(new FileInputStream("src/input.txt"));
                BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                N = Integer.parseInt(br.readLine());
                M = Integer.parseInt(br.readLine());
        
                mdist = new int[N + 1];
                dist = new int[N + 1][N + 1];
        
                // 인접행렬 - 본인과 본인과의 거리는 0이니 pass하고, 그게 아니라면 거리를 무한대로 초기화 한다.
                for(int n=1;n<=N;n++) {
                    Arrays.fill(dist[n], MAX_VALUE);
                    dist[n][n]=0;
                }
        
                // 문제에서 주어진 관계는 바로(1번만에) 갈수있다는 것이므로 1을 넣는다.
                for (int m = 0; m < M; m++) {
                    StringTokenizer st = new StringTokenizer(br.readLine());
                    int x = Integer.parseInt(st.nextToken());
                    int y = Integer.parseInt(st.nextToken());
                    // 양방향
                    dist[x][y] = 1;
                    dist[y][x] = 1;
                }
        
                //플로이드
                for(int k=1;k<=N;k++)
                    for(int i=1;i<=N;i++)
                        for(int j=1;j<=N;j++)
                            // K를 경유한 경우가 바로 간 경우보다 빠르다면
                            if(dist[i][j]>dist[i][k]+dist[k][j]) {
                                //거리(비용) 대입
                                dist[i][j]=dist[i][k]+dist[k][j];
                            }
        
                // mdist 만들기 - 한 행에서 MAX_VALUE 가 아닌 가장 큰수를 담은 배열
                for(int i=1;i<=N;i++)
                    for(int j=1;j<=N;j++)
                        if(dist[i][j]<MAX_VALUE && dist[i][j]>mdist[i])
                            mdist[i]=dist[i][j];
        
                pq = new PriorityQueue<>(); // 순서대로 꺼내기 위함
                boolean[] vis = new boolean[N+1];
                //1.연결되어있는가
                for(int i=1;i<=N;i++) {
                    //2. 갈수있는가 - 방문하지 않았으면 가능
                    if(!vis[i]) {
                        int d=mdist[i];
                        int cm=i;
                        for(int j=1;j<=N;j++) {
                            //3. 갈수있는가 - 거리가 MAX_VALUE 가 아니라면 가능
                            if(dist[i][j]<MAX_VALUE) {
                                // 현재 사람보다 j번째 사람이 비용이 적다면
                                if(d>mdist[j]) {
                                    // 대표는 j로 교체
                                    d=mdist[j];
                                    cm=j;
                                }
                                //4.체크인
                                vis[j]=true;
                            }
                        }
                        //5. 큐에넣음
                        pq.add(cm);
                    }
                }
        
                System.out.println(pq.size());
                while (!pq.isEmpty()) {
                    System.out.println(pq.poll());
                }
            }
        }

   2. Python 3

      • import sys
        import heapq
        # 정수 최댓값을 넣어두면 오버플로우로 연산이 이상해질 수 있음. 2배해도 무난한 10억으로 설정
        MAX_VALUE = 1000000000
        
        N = int(sys.stdin.readline())
        M = int(sys.stdin.readline())
        
        # 인접행렬 생성 - 본인과의 거리는 0, 나머지는 MAX_VALUE 로 초기화
        dist = [[MAX_VALUE for _ in range(N+1)] for _ in range(N+1)]
        for n in range(1,N+1):
            dist[n][n]=0
        
        # 인접행렬 생성 - 양방향으로 거리 넣기
        for m in range(M):
            x,y = map(int, (sys.stdin.readline().split()))
            dist[x][y] = dist[y][x] = 1
        
        # 플로이드
        for k in range(1,N+1):
            for i in range(1,N+1):
                for j in range(1,N+1):
                    # K를 경유한 경우가 바로 간 경우보다 빠르다면
                    if dist[i][j] > dist[i][k] + dist[k][j]:
                        # 거리(비용) 대입
                        dist[i][j] = dist[i][k] + dist[k][j]
        
        # mdist 만들기 - 한 행에서 MAX_VALUE 가 아닌 가장 큰수를 담은 배열
        mdist = [0 for _ in range(N+1)]
        for i in range(1,N+1):
            for j in range(1,N+1):
                if MAX_VALUE > dist[i][j] > mdist[i]:
                    mdist[i] = dist[i][j]
        
        pq = []
        vis = [False for _ in range(N+1)]
        # 1.연결되어있는가
        for i in range(1,N+1):
            # 2-1.갈수있는가 - 방문하지 않았으면 가능
            if not vis[i]:
                d = mdist[i]
                cm = i
                for j in range(N+1):
                    # 2-2. 갈수있는가 - 거리가 MAX_VALUE 가 아니라면 가능
                    if dist[i][j]<MAX_VALUE:
                        # 현재 사람보다 j번째 사람이 비용이 적다면
                        if d>mdist[j]:
                            # 대표는 j로 교체
                            d=mdist[j]
                            cm=j
                        # 3.체크인
                        vis[j]=True
                # 4. 큐에넣음
                heapq.heappush(pq, cm)
        
        print(len(pq))
        while len(pq)!=0:
            print(heapq.heappop(pq))

• 결과