[백준 1389] 케빈 베이컨의 6단계 법칙

[백준] PS/Java

[백준 1389] 케빈 베이컨의 6단계 법칙 - JAVA

SH3542 2024. 5. 31. 20:03

BOJ Link

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

개요

정점간 최단 경로를 찾는 문제이다.

(정확히는 다른 모든 정점까지의 최단 경로 가중치 합이 가장 작은 노드를 찾는)

그러므로, 플로이드-워셜이나 다익스트라 N번 반복으로 답을 찾을 수 있다.

간선별 가중치가 동일하며, 시작 노드로부터 다른 모든 노드에 도달 가능하므로 일반적인 bfs 풀이도 가능하다.

삽질 이후 이를 깨닫고 제출하여 통과했다.

제출 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.StringTokenizer;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[][] cost = new int[N + 1][N + 1];
        boolean[][] adj = new boolean[N + 1][N + 1];


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

            adj[from][to] = true;
            adj[to][from] = true;
        }

        for (int[] row : cost) Arrays.fill(row, Integer.MAX_VALUE);

        for (int i = 1; i <= N; i++) {
            boolean[] visited = new boolean[N + 1];
            Queue<int[]> q = new ArrayDeque<>();
            q.offer(new int[]{i, 1});
            visited[i] = true;

            while (!q.isEmpty()) {
                int[] info = q.poll();
                int nv = info[0];
                int dis = info[1];

                for (int j = 1; j <= N; j++) {
                    if (!visited[j] && adj[nv][j]) {
                        visited[j] = true;
                        q.offer(new int[]{j, dis + 1});
                        cost[i][j] = Math.min(cost[i][j], dis + 1);
                    }
                }
            }
        }
        int ansP = -1;
        int ansV = Integer.MAX_VALUE;
        
        for (int i = N; i > 0; i--) {
            int sum = 0;
            for (int j = 1; j <= N; j++) {
                sum += cost[i][j];
            }
            if (ansV == sum) {
                ansP = i;
            } else if (ansV > sum) {
                ansV = sum;
                ansP = i;
            }
        }

        System.out.println(ansP);
    }
}

헤맨 부분

같은 방문체크 배열을 쓴다면, dis=1인 탐색에서 이미 2번 노드가 visited 되므로, 빨간색 경로에서 3번->2번으로 가는 경우가 사라지게 된다.

물론 문제는 최단 경로를 찾는 것이기 때문에, 이를 고려하지 않아도 된다. 고려하는 코드를 짜도 어차피 파란색 경로로 갱신될 것이다. 이를 몰랐기 때문에 탐색 중인 각 노드마다 별도의 방문체크 배열을 가지는 코드를 짰다. (아주 안좋은 방법이였다.)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.StringTokenizer;

class Main {
    static int N, M, cost[][];
    static boolean adj[][];

    static class Node {
        int now, dis;
        boolean[] visited;

        public Node(int now, int dis, boolean[] visited) {
            this.now = now;
            this.dis = dis;
            this.visited = visited;
        }
    }

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        cost = new int[N + 1][N + 1];
        adj = new boolean[N + 1][N + 1];

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

            adj[from][to] = true;
            adj[to][from] = true;
        }

        for (int[] row : cost) Arrays.fill(row, Integer.MAX_VALUE);

        for (int i = 0; i < N; i++) {
            int np = i + 1;
            Queue<Node> q = new ArrayDeque<>();
            q.offer(new Node(np, 0, new boolean[N + 1]));

            while (!q.isEmpty()) {
                Node node = q.poll();
                int p = node.now;
                int dis = node.dis;
                cost[np][p] = Math.min(dis, cost[np][p]);

                for (int j = 1; j < N + 1; j++) {
                    if (!node.visited[j] && adj[p][j]) {
                        node.visited[j] = true;
                        // 경로 체크 컨테이너 따로 있어야 함
                        q.offer(new Node(j, dis + 1, deepClone(node.visited)));
                    }
                }
            }
        }

        int ansP = -1;
        int ansV = Integer.MAX_VALUE;
        
        for (int i = N; i > 0; i--) {
            int sum = 0;
            for (int j = 1; j <= N; j++) {
                sum += cost[i][j];
            }
            if (ansV == sum) {
                ansP = i;
            } else if (ansV > sum) {
                ansV = sum;
                ansP = i;
            }
        }

        System.out.println(ansP);
    }

    public static boolean[] deepClone(boolean[] oa) {
        boolean na[] = new boolean[N + 1];

        for (int i = 1; i < N + 1; i++) {
            na[i] = oa[i];
        }

        return na;
    }

}

이 때 든 생각은 이렇다.

N은 100이하니까

1~32

33~64

65~96

97~100번 정점의 방문 여부를 체크하는

비트마스킹 변수를 4개 쓰자!

이렇게 하면, N=100일 때 기준으로

탐색 횟수 * 100 * 4Byte를 탐색 횟수 * 4 * 4Byte로 줄일 수 있었다.

다음은 N값을 고려하여 visited[1~4]를 만들어 비트마스킹 하는 코드이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
import java.util.StringTokenizer;

class Main {
    static int N, M, vlen, intBit = 32, cost[][];
    static boolean adj[][];

    static class Node {
        int now, dis;
        Integer[] visited;

        public Node(int now, int dis, Integer[] visited) {
            this.now = now;
            this.dis = dis;
            this.visited = visited;
        }
    }

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        cost = new int[N + 1][N + 1];
        adj = new boolean[N + 1][N + 1];
        // visited 배열 길이
        vlen = N % intBit == 0 ? N / intBit : N / intBit + 1;

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

            adj[from][to] = true;
            adj[to][from] = true;
        }

        for (int[] row : cost) Arrays.fill(row, Integer.MAX_VALUE);

        for (int i = 0; i < N; i++) {
            int np = i + 1;
            Queue<Node> q = new ArrayDeque<>();

            Integer[] visited = new Integer[vlen];
            for (int j = 0; j < vlen; j++) {
                visited[j] = 0;
            }

            int initIdx = N % intBit == 0 ? N / intBit - 1 : N / intBit;
            int initVal = (np % intBit) - 1;
            int initBit = 1 << initVal;
            visited[initIdx] |= initBit;

            q.offer(new Node(np, 0, visited));

            while (!q.isEmpty()) {
                Node node = q.poll();
                int p = node.now;
                int dis = node.dis;
                cost[np][p] = Math.min(dis, cost[np][p]);

                for (int j = 1; j < N + 1; j++) {
                    // 몇번 째 visited의 수를 쓸지
                    int bitIdx = j % intBit == 0 ? j / intBit - 1 : j / intBit;
                    // n번째에 담긴 실제 비트마스킹용 int 값
                    int bitVal = node.visited[bitIdx];
                    // j에서 bitIdx를 제외하고, 1번 비트를 움직여야 할 횟수
                    int jVal = (j % intBit) - 1;
                    // Node j를 비트로 변환
                    int jBit = 1 << jVal;

                    if ((bitVal & jBit) == 0 && adj[p][j]) {
                        node.visited[bitIdx] |= jBit;
                        // 경로 체크 컨테이너 따로 있어야 함
                        q.offer(new Node(j, dis + 1, deepClone(node.visited)));
                    }
                }
            }
        }

        int ansP = -1;
        int ansV = Integer.MAX_VALUE;
        
        for (int i = N; i > 0; i--) {
            int sum = 0;
            for (int j = 1; j <= N; j++) {
                sum += cost[i][j];
            }
            if (ansV == sum) {
                ansP = i;
            } else if (ansV > sum) {
                ansV = sum;
                ansP = i;
            }
        }

        System.out.println(ansP);
    }

    public static Integer[] deepClone(Integer[] oa) {
        return Arrays.stream(oa).toArray(Integer[]::new);
    }

}

역시나,

이후 모든 경로를 고려할 필요 자체가 없다는 것을 깨닫고 위에 작성한 일반적인 bfs 코드를 제출해서 성공했다.

배운 점

1. Integer은 초기화 안하면 0이 아니라 null이 들어간다.

2. Integer i = new Integer(0); 과 같은 초기화 방식은 폐기되었다.

Integer i = Integer.valueOf(0);
Integer i2 = 0;

와 같이 static method나 오토언박싱을 통한 방식을 써야한다. (후자의 2번 방식은 어차피 내부적으로 valueOf() 메서드를 호출한다.)

전자의 방식을 폐기하고 후자의 방식을 쓰는 이유는, 자바는 내부적으로 -128~127 사이의 값을 캐싱한다. valueOf()메서드는 해당 범위의 값이라면 이를 사용한다.

class Main {
    public static void main(String[] args) {

        Integer i = Integer.valueOf(127);
        Integer i2 = Integer.valueOf(127);

        Integer i3 = Integer.valueOf(128);
        Integer i4 = Integer.valueOf(128);

        System.out.println(i==i2); // true
        System.out.println(i3==i4); // false

    }
}

레퍼런스 타입끼리 "==" 동등성 비교는 주소 비교이다. 그럼에도 -128~127 범위는 (같은) 캐싱된 값을 이용하므로 true이다.

이는 Stritng의 경우 JVM이 String pool에 캐싱하여 사용하기 때문에 일어나는 동작과 유사하다.

import java.util.Scanner;

class Main {
    public static void main(String[] args) {

        String s = "hello";
        String s2 = "hello";

        String s3 = new Scanner(System.in).nextLine();
        String s4 = "hi";

        System.out.println(s == s2); // true
        System.out.println(s3 == s4); // false, when s3 = hi
    }
}

3. 컬렉션 라이브러리의 컨테이너에 레퍼런스 값은 넣을 수 있지만, 프리미티브 타입은 안된다.

프티미티브 값 배열은 된다. 단편적인 이유는 제너릭 T값을 넣어야 하게 선언되어 있고, 배열은 레퍼런스 타입이기 때문이다.

class Main2 {

    public static void main(String[] args) {
        Queue<Integer> q = new ArrayDeque<>(); // o
        Queue<int[]> q2 = new ArrayDeque<>(); // o
        Queue<int> q3 = new ArrayDeque<>(); // x
    }
}

'[백준] PS > Java' 카테고리의 다른 글

[백준 1991] 트리 순회 - JAVA (0)	2024.06.10
[백준 1497] 기타콘서트 - JAVA (0)	2024.06.09
[백준 17471] 게리맨더링 - JAVA (0)	2024.06.06
[백준 17136] 색종이 붙이기 - JAVA (1)	2024.06.05
[백준 18137] 나이트의 경로 - JAVA (0)	2024.05.28

현재글[백준 1389] 케빈 베이컨의 6단계 법칙 - JAVA

끄적끄적

고통 끝의 성취가 좋아서 개발합니다

Today :
Yesterday :

끄적끄적