[JAVA] BOJ 백준 2617번 - 구슬 찾기

목차

• 문제
• 내가 푼 방법
• 자바 코드
• 결과 및 회고

---

1. 문제

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

---

2. 내가 푼 방법

플로이드 와샬을 사용해서 가중치를 가져야 하는 방법까지 딱 거기까지만 생각해 냈다. 그 후에 가중치를 어떻게 카운팅해서 정답을 구하는지가 관건이었던 것 같다.

 

먼저 단방향 그래프로 v1이 v2보다 더 무거우므로 v2에서 v1으로 갈 때 더 무거운 가중치를 가지도록 설정했다.

그 후, 플로이드 와샬 알고리즘을 이용해 가중치를 합해주었다.

int[][] arr = new int[N+1][N+1];

for (int i = 0; i < M; i++) {
    st = new StringTokenizer(br.readLine());
    int v1 = Integer.parseInt(st.nextToken());
    int v2 = Integer.parseInt(st.nextToken());

    arr[v2][v1] = 1;
}

for (int k = 1; k <= N; k++) {
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            if (i == j) continue;
            if (arr[i][k] == 0 || arr[k][j] == 0) continue;

            if (arr[i][j] == 0 || arr[i][j] > arr[i][k] + arr[k][j]) {
                arr[i][j] = arr[i][k] + arr[k][j];
            }
        }
    }
}

 

이제 2중 for문을 돌면서 i에서 j로 갈 때 더 무거운 구슬인지를 확인하면 되는데, 이때 핵심은 가벼운 구슬인지까지도 확인해주어야하는 것이다. 당연하게 생각하면 i에서 j로 갈 때 더 무거운 구슬이면, j에서 i로 갈 때 더 가벼운 구슬임을 떠올릴 수 있다.

int[] big = new int[N+1];
int[] small = new int[N+1];

for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= N; j++) {
        if (arr[i][j] == 0) continue;
        
        big[i]++;
        small[j]++;
    }
}

 

이제 마지막으로 구한 구슬마다 구한 큰 구슬 개수, 작은 구슬 개수가 절반 이상일 경우, 중간 구슬에서 제외되므로 result++를 해주면 된다.

int result = 0;

int mid = (N + 1) / 2;
for (int i = 1; i <= N; i++) {
    if (big[i] >= mid) result++;
    else if (small[i] >= mid) result++;
}

bw.write(result+"");

---

3. 자바 코드

깃허브 풀이 주소

https://github.com/geujeog/BOJ/blob/main/B2617.java

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

class Main {
    public static void main (String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[][] arr = new int[N+1][N+1];

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());

            arr[v2][v1] = 1;
        }

        for (int k = 1; k <= N; k++) {
            for (int i = 1; i <= N; i++) {
                for (int j = 1; j <= N; j++) {
                    if (i == j) continue;
                    if (arr[i][k] == 0 || arr[k][j] == 0) continue;

                    if (arr[i][j] == 0 || arr[i][j] > arr[i][k] + arr[k][j]) {
                        arr[i][j] = arr[i][k] + arr[k][j];
                    }
                }
            }
        }

        int[] big = new int[N+1];
        int[] small = new int[N+1];

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (arr[i][j] == 0) continue;
                big[i]++;
                small[j]++;
            }
        }

        int result = 0;

        int mid = (N + 1) / 2;
        for (int i = 1; i <= N; i++) {
            if (big[i] >= mid) result++;
            else if (small[i] >= mid) result++;
        }

        bw.write(result+"");

        br.close();
        bw.flush();
        bw.close();
    }
}

---

4. 결과 및 회고

단방향 그래프에 대해서 고민하면서 풀었던 것 같다. 그래프 문제 더 많이 풀어보장.