[JAVA] 백준 2617번 【G4.구슬 찾기】

문제

2617번: 구슬 찾기

 

풀이

1️⃣ bfs와 Marble 클래스 정의를 통한 풀이

💡 떠오른 Idea

문제를 해결하기 위한 방법은 문제에 거의 주어지다 싶이 나와있었다.

구슬이 총 5개일때는 특정 구슬보다 가벼운게 3개 이상인 경우 중간이 될 수 없고

무거운게 3개 이상인 경우는 중간이 될 수 없다.

처음에는 N이 짝수로도 주어지나 싶어서, 짝수인 경우에는 약간 기준이 달랐지만 홀수로만 주어진다고 했으므로

특정 구슬이, 상대적으로 가벼운 구슬이 (N+1)/2 개 이상이거나 무거운 구슬이 (N+1)/2 개 이상이라면 절대 중간이 될 수 없음을 알 수 있다.

따라서, 구슬끼리 연결을 맺어주고 특정 구슬보다 무거운 개수 혹은 가벼운 개수를 bfs를 이용하여 구하면 된다.

 

public class Main {
    static int N;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        N = Integer.parseInt(input[0]);
        int M = Integer.parseInt(input[1]);
        List<Marble> marbles = new ArrayList<>();
        
        // 각 구슬마다 무거운 혹은 가벼운 구슬을 저장할 수 있도록 Marble 클래스를 넣어준다.
        for (int i = 0; i < N; i++) {
            marbles.add(new Marble(i));
        }

        for (int i = 0; i < M; i++) {
            input = br.readLine().split(" ");
            Marble big = marbles.get(Integer.parseInt(input[0]) - 1);
            Marble small = marbles.get(Integer.parseInt(input[1]) - 1);

			// 큰 구슬의 작은 구슬 모음에는 작은 것들을 추가
            big.smallMarbles.add(small);
            // 작은 구슬의 큰 구슬 모음에는 큰 것들을 추가
            small.bigMarbles.add(big);
        }

        int ans = 0;
        
        for (int i = 0; i < N; i++) {
        	
            // 각 구슬 별로 무거운 개수 혹은 가벼운 개수를 체크해준다.
            Marble marble = marbles.get(i);
            if (getCntOfBigger(marble) >= (N + 1) / 2) {
                ans++;
                continue;
            }

            if (getCntOfSmaller(marble) >= ((N + 1) / 2)) {
                ans++;
            }
        }

        System.out.println(ans);
    }

	// bfs 를 이용
    private static int getCntOfBigger(Marble node) {
        int cnt = 0;
        Queue<Marble> q = new LinkedList<>();
        boolean[] checked = new boolean[N];
        q.offer(node);
        checked[node.idx] = true;
        while (!q.isEmpty()) {
            Marble poll = q.poll();
            for (Marble bigMarble : poll.bigMarbles) {
                if (!checked[bigMarble.idx]) {
                    q.offer(bigMarble);
                    checked[bigMarble.idx] = true;
                    cnt++;
                }
            }
        }
        return cnt;
    }

    private static int getCntOfSmaller(Marble node) {
        int cnt = 0;
        Queue<Marble> q = new LinkedList<>();
        boolean[] checked = new boolean[N];
        q.offer(node);
        checked[node.idx] = true;
        while (!q.isEmpty()) {
            Marble poll = q.poll();
            for (Marble smallMarble : poll.smallMarbles) {
                if (!checked[smallMarble.idx]) {
                    q.offer(smallMarble);
                    checked[smallMarble.idx] = true;
                    cnt++;
                }
            }
        }
        return cnt;
    }

    static class Marble {
        int idx;

        List<Marble> bigMarbles = new ArrayList<>();
        List<Marble> smallMarbles = new ArrayList<>();

        public Marble(int idx) {
            this.idx = idx;
        }
    }
}

 

결과

 

 

2️⃣ 플로이드 알고리즘 사용

💡 플로이드 알고리즘을 사용해서 풀 수도 있다고 하여 도전해보았다.

구슬 개수가 최대 100개로 3중 for문을 사용하는 플로이드 알고리즘을 충분히 사용할 수 있음을 판단하였다.

플로이드 알고리즘을 사용할 수 있는 일종의 힌트로서 잘 캐치해봐야겠다.

플로이드 알고리즘을 통해서 구슬이 큰 관계 끼리만 연결하는 그래프와 구슬이 작은 경우 연결하는 그래프 2개를 준비해서 플로이드 알고리즘을 연결해준다.

결과로 나온 그래프가 초기값이나 MAX 값이 아니라면 어찌됐든 연결이 되었다는 의미이므로

카운팅을해줘서 개수가 (N+1)/2 이상인지 체크해주면 된다.

public class Main {
    static int N;
    static final int MAX = 100;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        N = Integer.parseInt(input[0]);
        int M = Integer.parseInt(input[1]);
        int[][] smalls = new int[N][N];
        int[][] bigs = new int[N][N];
        
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                if (r != c) {
                    smalls[r][c] = MAX;
                    bigs[r][c] = MAX;
                }
            }
        }


        for (int i = 0; i < M; i++) {
            input = br.readLine().split(" ");
            int big = Integer.parseInt(input[0]) - 1;
            int small = Integer.parseInt(input[1]) - 1;
			
            // 작은 관계 그래프
            smalls[small][big] = 1;
            
            // 큰 관계 그래프
            bigs[big][small] = 1;

        }

		//플로이드 알고리즘 사용
        for (int m = 0; m < N; m++) {
            for (int u = 0; u < N; u++) {
                for (int v = 0; v < N; v++) {
                    smalls[u][v] = Math.min(smalls[u][v], smalls[u][m] + smalls[m][v]);
                    bigs[u][v] = Math.min(bigs[u][v], bigs[u][m] + bigs[m][v]);
                }
            }
        }

        int ans = 0;
        for (int i = 0; i < N; i++) {
            int cntOfSmall = getCount(smalls, i);
            if (cntOfSmall >= (N + 1) / 2) {
                ans++;
                continue;
            }

            int cntOfBig = getCount(bigs, i);
            if (cntOfBig >= (N + 1) / 2) {
                ans++;
            }
        }
        System.out.println(ans);

    }

    private static int getCount(int[][] graph, int i) {
        int cnt = 0;
        for (int c = 0; c < N; c++) {
            if (graph[i][c] != MAX && graph[i][c] != 0) {
                cnt++;
            }
        }
        return cnt;
    }

}

 

결과