(JAVA) [BOJ]백준 14938번, 서강그라운드

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

14938번: 서강그라운드

 

 

14938, 서강그라운

📌 난이도 : Gold 4

📌 알고리즘 : 플로이드 와샬 (Floyd-Warshall)

이번 문제는 DFS 로 풀이를 시도했다가 처참하게 틀리고 플로이드 와샬로 재풀이를 진행하였다.

 

📚 Process

초기화 및 선언

: 지역의 개수 N, 수색범위 M, 길이개수 R 을 차례로 입력받고 아이템 개수를 받을 item[] 을 선언해서 차례로 채워준다.

수색 길이를 입력받을 int[][] distance 를 선언 후 자기자신 노드에서 자기자신 노드는 0, 나머지는 INF (987,654,321) 로 초기화 해준다. 그 후에 양방향으로 수색 길이를 넣어준다.

public static void input() throws IOException{
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());   // 지역의 개수
        M = Integer.parseInt(st.nextToken());   // 수색범위
        R = Integer.parseInt(st.nextToken());   // 길이개수

        item = new int[N+1];                // 아이템 개수
        distance = new int[N+1][N+1];       // 거리

        // [init] 자기자신은 0, 연결되는 노드가 없는 경우엔 INF=>987654321
        for(int i=1; i<=N; i++) {
            for(int j=1; j<=N; j++) {
                if(i==j) continue;
                distance[i][j] = INF;
            }
        }

        st = new StringTokenizer(br.readLine(), " ");
        for(int i=1; i<=N; i++) item[i] = Integer.parseInt(st.nextToken());

        while(R-->0) {
            st = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            distance[a][b] = distance[b][a] = c;
        }
    }

 

 

Floyd-Warshall

 

: j=>k 를 가는 것보다 j=>i=>k 로 가는 비용이 적게 든다면 초기화하는 과정이다.

// j->k 를 가는 것보다 j->i->k 로 가는 비용이 적게든다면 초기화
public static void fluid() {
    for(int i=1; i<=N; i++) {
        for(int j=1; j<=N; j++) {
            for(int k=1; k<=N; k++) {
                if(distance[j][k] > distance[j][i] + distance[i][k]) {
                    distance[j][k] = distance[j][i] + distance[i][k];
                }
            }
        }
    }
}

 

탐색

: 모든 지역까지의 최소 거리를 구했으면 수색 범위에서 가능한 아이템의 수를 카운트하며 max 값을 도출한다.

public static void pro() {
    // 최단 거리로 초기화
    fluid();

    int max = 0;
    int temp;
    for(int i=1; i<=N; i++) {
        temp = 0;
        for(int j=1; j<=N; j++) {
            if(distance[i][j] > M) continue;

            temp += item[j];
        }
        max = Math.max(max, temp);
    }

    System.out.println(max);
}

 

✅ 전체 코드

: 플로이드 와샬의 문제는 매 문제마다 새로워서 고통스럽다..

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int N,M,R;
    static int INF = 987654321;
    static int[][] distance;
    static int[] item;
    
    public static void main(String[] args) throws IOException{
        input();
        pro();
    }

    public static void input() throws IOException{
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());   // 지역의 개수
        M = Integer.parseInt(st.nextToken());   // 수색범위
        R = Integer.parseInt(st.nextToken());   // 길이개수

        item = new int[N+1];                // 아이템 개수
        distance = new int[N+1][N+1];       // 거리

        // [init] 자기자신은 0, 연결되는 노드가 없는 경우엔 INF=>987654321
        for(int i=1; i<=N; i++) {
            for(int j=1; j<=N; j++) {
                if(i==j) continue;
                distance[i][j] = INF;
            }
        }

        st = new StringTokenizer(br.readLine(), " ");
        for(int i=1; i<=N; i++) item[i] = Integer.parseInt(st.nextToken());

        while(R-->0) {
            st = new StringTokenizer(br.readLine(), " ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());

            distance[a][b] = distance[b][a] = c;
        }
    }

    public static void pro() {
        // 최단 거리로 초기화
        fluid();
        
        int max = 0;
        int temp;
        for(int i=1; i<=N; i++) {
            temp = 0;
            for(int j=1; j<=N; j++) {
                if(distance[i][j] > M) continue;
                
                temp += item[j];
            }
            max = Math.max(max, temp);
        }

        System.out.println(max);
    }

    // j->k 를 가는 것보다 j->i->k 로 가는 비용이 적게든다면 초기화
    public static void fluid() {
        for(int i=1; i<=N; i++) {
            for(int j=1; j<=N; j++) {
                for(int k=1; k<=N; k++) {
                    if(distance[j][k] > distance[j][i] + distance[i][k]) {
                        distance[j][k] = distance[j][i] + distance[i][k];
                    }
                }
            }
        }
    }
}