백준 3098 - 소셜 네트워크

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

3098번: 소셜네트워크

 

* 문제 요약

소셜 네트워크는 이제 우리 삶의 일부가 되어버렸다. 이러한 소셜 네트워크를 분석하는 김동규 석사과정은 흥미로운 현상을 발견했다. 바로 친구 관계의 수가 급속도로 증가한다는 것이다.

예로부터 우리의 조상님들은 "친구의 친구는 나의 친구" 라고 했다. 사람들은 매일 조상님들의 말씀을 따르기 위해서 자신의 친구의 친구 목록을 확인하고, 이를 모두 자신의 친구로 추가한다. 친구관계는 상대방이 수락을 해야되고, 총 1일이 걸린다.

 

예를 들어 A와 B가 친구라면,  A는 B가 어제 또는 그 이전에 만든 친구만 볼 수 있다.

모든 친구관계는 대칭이다. 즉, A가 B의 친구라면 B도 A의 친구이다.

김동규가 분석하는 소셜 네트워크에서는 한 번 친구 관계가 맺어졌으면 이것을 깰 수 없다.

사람의 수와 지금 친구관계가 주어졌을 때, 모든 사람이 서로 친구가 되는데 며칠이 걸리는지 구하는 프로그램을 작성하시오. 또한, 매일매일 새로운 친구 관계가 얼마나 생기는지 구해서 출력하시오.

 

* 입력

첫째 줄에 사람의 수 N과 처음 친구 관계의 수M이 주어진다. (1 <= N <= 50, 1 <= M <= N * (N - 1) / 2)

둘째 줄부터 M개의 줄에는 두 정수 A와 B가 주어진다. (1 <= A <= N, 1 <= B <= N, A < B) 이것은 A와 B가 친구라는 것을 의미한다. 항상 모든 사람이 서로 친구가 될 수 있는 경우만 입력으로 주어진다.

 

* 출력

첫째 줄에 모든 사람이 서로 친구가 되는데 며칠이 걸리는지 출력한다. 이 값을 K라고 하자.

다음 K개의 줄에는 몇 명의 새로운 친구 관계가 생기는지 첫째날부터, K번째 날까지 한 줄에 하나씩 출력한다.

 

* 예시

 

* 해결 과정

처음엔 이 문제를 어떻게 풀어야 할 지 몰라 헤매다가 결국 다른 사람의 풀이를 보고 힌트를 얻어서 직접 로직을 설계한 후 코드를 작성해서 푼 문제이다.

 

입력받은 친구관계 정보를 토대로 2차원 배열을 만든다.

서로 친구관계인 경우 관계가 대칭이어야 하기 때문에 해당 쌍의 인덱스 값을 모두 1로 초기화한다.

예를 들어 1 2 라는 입력이 들어왔을 경우 (1, 2), (2, 1) 두 인덱스의 값을 1로 초기화한다.

이후 2차원 배열의 모든 값이 1이 될 때까지 다음과 같이 반복문을 진행한다.

1. 이중 반복문을 통해 2차원 배열을 탐색한다.

2. 현재 인덱스 쌍이 (i, j) 일 때 i != j 인 동시에 현재 인덱스 값이 1인 경우 bfs(int i, int j) 메소드를 호출한다.

3. bfs(int i, int j) 메소드는 다음과 같이 동작한다.

  - i행의 친구인 j행의 각 열 정보(친구의 친구 리스트) 를 탐색하기 위해 반복문을 수행한다.

  - index 값이 i 또는 j 와 일치할 경우 아무 로직도 수행하지 않는다. j와 같을 경우엔 자기자신을 탐색 중이라는 뜻이고 i 와 같을 경우엔 이미 i행과 j행은 서로 친구인 것을 확인한 상태로 bfs() 메소드를 호출한 것이기 때문에 로직을 수행해줄 것이 없다.

  - 2차원 배열에서 (j, index) 쌍의 값이 1이고, (i, index) 쌍의 값이 0인 경우. 즉, 현재 탐색중인 위치가 j행의 친구이면서 i행의 친구가 아닌 경우 i와 index 의 크기를 비교하여 i가 index 보다 작을 경우 (i, index), i 가 index 보다 클 경우 (index, i) 쌍을 문자열 형태로 만들어준 다음(requestForm 변수) 미리 만들어둔 Set 자료구조에 저장한다.

  - Set 자료구조에 저장하는 이유는 이미 친구등록 요청이 들어와 있는 인덱스 쌍에 대해 중복 요청을 피해주기 위해서이다.

  - j행에 대한 탐색이 끝나면 bfs(int i, int j) 메소드가 종료된다.

4. 현재 인덱스 쌍이 (i, j) 일 때 i != j 인 동시에 현재 인덱스 값이 0인 경우 2차원 배열 내부에서 0의 갯수를 나타내는 변수 zeroCount 변수값을 1 증가시킨다.

5. 이중 반복문을 통해 이번 반복에서의 2차원 배열에 대한 탐색이 끝나고 나면 zeroCount  변수의 값을 확인한다.

6. zeroCount 의 값이 0인 경우 2차원 배열의 모든값이 1이라는 뜻. 즉, 모든 사람들이 친구관계로 연결되었다는 뜻이므로 반복문을 종료한다.

7. 그렇지 않을 경우 반복횟수를 세는 변수 count 를 1 증가시킨다. 여기서 반복횟수 값의 증가는 하루가 지났음을 의미한다.

8. 해당 반복 회차에서의 친구등록 요청횟수 (Set 자료구조의 크기) 를 미리 만들어둔 setSize 큐에 삽입해준다.

9. 친구등록 요청을 저장해둔 Set 자료구조에 있는 데이터들을 반복문을 통해 하나하나 꺼낸 다음, 2차원 배열상에서 해당하는 인덱스 쌍의 값을 1로 초기화 시켜준다. 예를 들어 Set 에서 꺼낸 문자열이 "1, 2" 였다면 (1, 2), (2, 1) 인덱스 쌍을 1로 초기화 시켜준다.

10. 모든 요청에 대한 친구등록이 완료되고 나면 Set 자료구조를 초기화해주고 다음 반복 회차로 넘어간다.

11. 2차원 배열상에서 0 이 발견되지 않아서 반복문이 종료되고 나면 count 변수 값을 먼저 출력시켜준다.

12. 마지막으로 setSize 큐에 저장되어 있는 값들을 순서대로 출력시켜 준다.

 

* 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

public class Main {
    public static void main(String[] args) throws IOException {
        new Main().solution();
    }

    static int[][] snsArray;
    static Set<String> registerSet = new HashSet<>();
    static int n;

    private void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] input = br.readLine().split(" ");
        n = Integer.parseInt(input[0]);
        int m = Integer.parseInt(input[1]);
        snsArray = new int[n + 1][n + 1];

        // 자기자신에 대한 처리
        for (int i = 1; i < n + 1; i++) {
            snsArray[i][i] = 1;
        }
        // 친구관계 입력정보 처리
        for (int i = 0; i < m; i++) {
            input = br.readLine().split(" ");
            int x = Integer.parseInt(input[0]);
            int y = Integer.parseInt(input[1]);

            snsArray[x][y] = 1;
            snsArray[y][x] = 1;
        }

        int count = 0;
        Queue<Integer> setSize = new LinkedList<>();
        while (true) {
            int zeroCount = 0;

            for (int i = 1; i < n + 1; i++) {
                for (int j = 1; j < n + 1; j++) {
                    if (i != j && snsArray[i][j] == 1) {
                        // 현재 행의 친구관계에 해당되는 행 탐색
                        bfs(i, j);
                    } else if (i != j && snsArray[i][j] == 0) {
                        zeroCount++;
                    }
                }
            }
            // 2차원 배열에서 0이 한번도 나오지 않았을 경우 반복문 중지
            if (zeroCount == 0) {
                break;
            } else {
                count++;
                setSize.offer(registerSet.size());
                Iterator<String> iterator = registerSet.iterator();
                while (iterator.hasNext()) {
                    String registerRequest = iterator.next();
                    String[] registerArray = registerRequest.split(",");

                    int x = Integer.parseInt(registerArray[0]);
                    int y = Integer.parseInt(registerArray[1]);

                    snsArray[x][y] = 1;
                    snsArray[y][x] = 1;
                }
                registerSet.clear();
            }
        }

        bw.write(count + "\n");
        while (!setSize.isEmpty()) {
            bw.write(setSize.poll() + "\n");
        }
        bw.flush();
        bw.close();
        br.close();
    }

    // j행에서 i행과 친구관계가 아닌 열이 발견될 경우 해당 열과 i행에 대한 친구등록 신청
    private void bfs(int i, int j) {
        for (int index = 1; index < n + 1; index++) {
            if (index == i || index == j) {
                continue;
            } else {
                if (snsArray[j][index] == 1 && snsArray[i][index] == 0) {

                    // 친구의 친구 리스트중에서 i행과 서로 친구가 아닌 경우
                    String registerForm = "";
                    if (i < index) {
                        registerForm = String.valueOf(i) + "," + String.valueOf(index);
                    } else if (i > index) {
                        registerForm = String.valueOf(index) + "," + String.valueOf(i);
                    }

                    registerSet.add(registerForm);
                }
            }
        }
    }
}

 

2차원 배열에서 BFS 알고리즘을 활용해서 풀 수 있었던 문제이다. 지금까지 BFS 문제는 인접 리스트만 활용해서 풀어왔는데, 이젠 2차원 배열로 BFS 문제를 푸는 연습을 좀 더 해야할 것 같다.