2617번 : 구슬 찾기

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

2617번: 구슬 찾기

 

문제

모양은 같으나, 무게가 모두 다른 N개의 구슬이 있다. N은 홀수이며, 구슬에는 번호가 1,2,...,N으로 붙어 있다. 이 구슬 중에서 무게가 전체의 중간인 (무게 순서로 (N+1)/2번째) 구슬을 찾기 위해서 아래와 같은 일을 하려 한다.

우리에게 주어진 것은 양팔 저울이다. 한 쌍의 구슬을 골라서 양팔 저울의 양쪽에 하나씩 올려 보면 어느 쪽이 무거운가를 알 수 있다. 이렇게 M개의 쌍을 골라서 각각 양팔 저울에 올려서 어느 것이 무거운가를 모두 알아냈다. 이 결과를 이용하여 무게가 중간이 될 가능성이 전혀 없는 구슬들은 먼저 제외한다.

예를 들어, N=5이고, M=4 쌍의 구슬에 대해서 어느 쪽이 무거운가를 알아낸 결과가 아래에 있다.

1. 구슬 2번이 구슬 1번보다 무겁다.
2. 구슬 4번이 구슬 3번보다 무겁다.
3. 구슬 5번이 구슬 1번보다 무겁다.
4. 구슬 4번이 구슬 2번보다 무겁다.

위와 같이 네 개의 결과만을 알고 있으면, 무게가 중간인 구슬을 정확하게 찾을 수는 없지만, 1번 구슬과 4번 구슬은 무게가 중간인 구슬이 절대 될 수 없다는 것은 확실히 알 수 있다. 1번 구슬보다 무거운 것이 2, 4, 5번 구슬이고, 4번 보다 가벼운 것이 1, 2, 3번이다. 따라서 답은 2개이다.

M 개의 쌍에 대한 결과를 보고 무게가 중간인 구슬이 될 수 없는 구슬의 개수를 구하는 프로그램을 작성하시오.

 

입력

첫 줄은 구슬의 개수를 나타내는 정수 N(1 ≤ N ≤ 99)과 저울에 올려 본 쌍의 개수 M(1 ≤ M ≤ N(N-1)/2)이 주어진다. 그 다음 M 개의 줄은 각 줄마다 두 개의 구슬 번호가 주어지는데, 앞 번호의 구슬이 뒤 번호의 구슬보다 무겁다는 것을 뜻한다.

 

출력

첫 줄에 무게가 중간이 절대로 될 수 없는 구슬의 수를 출력 한다.

 

---

소스코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    private static int n, m;
    private static ArrayList<ArrayList<Integer>> arr1 = new ArrayList<>(); // 정점보다 큰 값
    private static ArrayList<ArrayList<Integer>> arr2 = new ArrayList<>(); // 정점보다 작은 값
    static boolean visited[];

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        for (int i = 0; i <= n; i++) {
            arr1.add(new ArrayList<>());
            arr2.add(new ArrayList<>());
        }
        
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            // a > b
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            arr1.get(b).add(a);
            arr2.get(a).add(b);
        }

        int result = 0;
        int mid = n / 2 + 1;
        for (int i = 1; i <= n; i++) {
            visited = new boolean[n + 1];
            int cnt = bfs(i, 1);
            if(cnt < mid) {
                visited = new boolean[n + 1];
                cnt = bfs(i, 2);
            }
            if(cnt >= mid) result++;
        }

        System.out.println(result);
    }

    static public int bfs(int x, int flag) {
        int cnt = 0;
        ArrayDeque<Integer> q = new ArrayDeque<>();
        q.add(x);

        while(!q.isEmpty()) {
            Integer now = q.poll();
            if(flag == 1) {
                for (int i = 0; i < arr1.get(now).size(); i++) {
                    Integer nx = arr1.get(now).get(i);
                    if (visited[nx]) continue;
                    visited[nx] = true;
                    cnt += 1;
                    q.add(nx);
                }
            } else {
                for (int i = 0; i < arr2.get(now).size(); i++) {
                    Integer nx = arr2.get(now).get(i);
                    if (visited[nx]) continue;
                    visited[nx] = true;
                    cnt += 1;
                    q.add(nx);
                }
            }
        }

        return cnt;
    }
}

 

해결방법

x > y의 경우, x와 y는 양방향으로 연결되어 있다고 가정한다.

 

연결된 두 값을 2가지 경우로 나눈다.

1. 현재 구슬의 값보다 큰 값들의 리스트

2. 현재 구슬의 값보다 작은 값들의 리스트

 

 

입력값이 아래와 같다면 (예제 1) 

5 4 // n m
2 1 // 2 > 1
4 3 // 4 > 3
5 1 // 5 > 1
4 2 // 4 > 2

 

중간 

mid = 5/2 = 2 + 1 = 3 

=> 현재 구슬에서 연결되어 있는 구슬의 개수가 3개 이상이라면 중간값이 될 수 없다!

=> 이때 연결은 "현재 값보다 큰 값들이 3개 이상" 또는 "현재 값보다 작은 값들이 3개 이상"을 의미한다.

 

현재 값보다 큰 값들의 리스트

1 -> 2 -> 5   

2 -> 4

3 -> 4

4 ->

5 ->

 

현재 값보다 작은 값들의 리스트

1 -> 

2 -> 1

3 ->

4 -> 3 -> 2

5 -> 1

 

이런 식으로 리스트 2개를 만들 수 있다.

 

판단

구슬 1보다 큰 값을 가진 구슬은 2, 5, 4 총 3개이므로 중간값이 될 수 없다! => 만족

구슬 1보다 작은 값을 가진 구슬은 없으므로 중간값이 될 수 있다! => 불만족

=> 만족 || 불만족 -> 만족

 

구슬 2보다 큰 값을 가진 구슬은 4 총 1개이므로 중간값이 될 수 있다! => 불만족

구슬 2보다 작은 값을 가진 구슬은 1 총 1개이므로 중간값이 될 수 있다! => 불만족

=> 불만족 || 불만족 -> 불만족

 

구슬 3보다 큰 값을 가진 구슬은 4 총 1개이므로 중간값이 될 수 있다! => 불만족

구슬 3보다 작은 값을 가진 구슬은 없으므로 중간값이 될 수 있다! => 불만족

=> 불만족 || 불만족 -> 불만족

 

구슬 4보다 큰 값을 가진 구슬은 없으므로 중간값이 될 수 없다! => 불만족

구슬 4보다 작은 값을 가진 구슬은 3, 2, 1 총 3개이므로 중간값이 될 수 없다! => 만족

=> 만족 || 불만족 -> 만족

 

구슬 5보다 큰 값을 가진 구슬은 없으므로 중간값이 될 수 있다! => 불만족

구슬 5보다 작은 값을 가진 구슬은 1 총 1개이므로 중간값이 될 수 있다! => 불만족

=> 불만족 || 불만족 -> 불만족

 

고로 구슬 1번과 구슬 4번은 무게가 중간인 구슬이 될 수 없으므로 답은 2가 되는 것이다.

 

위 풀이과정을 BFS를 사용해 코드로 구현하면 해결할 수 있다!