[백준] 알고리즘 분류(그래프 이론,JAVA)14938번, 서강그라운드

문제 링크

14938번: 서강그라운드

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

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

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 예은이는 수색범위만큼 시작 지점에서 이동할 수 있습니다.

2. 주어지는 길은 양방향이며, 거리가 주어집니다.

3. 예은이가 1 ~ n 지역에서 시작할 때 아이템을 얻을 수 있는 최대값을 결과로 출력합니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 각 지점에서 태어나는 것을 기준으로 아이템을 얻을 수 있는 최대값을 탐색합니다.

 

3. 탐색이 끝난 뒤 아이템을 얻을 수 있는 최대값을 결과로 출력합니다.

 

예은이의 지역 탐색!

 

예은이는 수색범위만큼 시작 위치에서 길을 이동하여 먹는 길을 탐색합니다.

 

각 시작 지역에서 BFS탐색을 했을 때 아이템을 먹은 최대 개수를 계산합니다.

 

다른 지역을 탐색할 때에는 최단 거리로 이동하는 경로로 탐색합니다.

 

지역 1에서 지역 3으로 이동할 때

 

지역 1 ▶ 지역 3 : 4

 

지역 1 ▶ 지역 2 ▶ 지역 3 : 3

 

지역 3을 이동할 때 지역 2를 거치는 것이 거리가 더 짧으므로 해당 방법으로 지역 3까지 탐색합니다.

 

이와 같이 다른 지역을 탐색할 때 최단 거리로 탐색해야 더 멀리 탐색이 가능합니다.

 

 

예제입력 1.

 

1. 입력된 정보를 저장합니다.

 

n : 5

m : 5

r : 4

 

 

2. 각 지점에서 태어나는 것을 기준으로 아이템을 얻을 수 있는 최대값을 탐색합니다.

 

 

시작 지역 1번으로 탐색!

 

 

1번 지역 : 5

2번 지역 : 7

4번 지역 : 2

5 + 7 + 2 = 14

 

시작 지역 2번으로 탐색!

 

1번 지역 : 5

2번 지역 : 7

3번 지역 : 8

5번 지역 : 3

5 + 7 + 8 + 2 = 23

 

시작 지역 3번으로 탐색!

 

2번 지역 : 7

3번 지역 : 8

7 + 8  = 15

 

시작 지역 4번으로 탐색!

 

1번 지역 : 5

4번 지역 : 2

5 + 2  = 7

 

시작 지역 5번으로 탐색!

 

2번 지역 : 7

5번 지역 : 3

7 + 3  = 10

 

3. 탐색이 끝난 뒤 아이템을 얻을 수 있는 최대값을 결과로 출력합니다.

 

지역 2번으로 탐색 : 23

23 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 이용하여 지역 및 길에 대한 정보를 띄어쓰기 기준 나누었습니다.
• search함수를 이용하여 각 지역을 시작으로 먹을 수 있는 아이템을 구합니다.
• 먹을 수 있는 최대 아이템 개수를 결과로 BufferedWriter에 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• search함수는 BFS를 이용해서 각 지역에서 출발했을 때 먹을 수 있는 아이템 개수를 구합니다.

 

결과코드

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
    //BFS 지역 이동 정보 클래스
    static class node implements Comparable<node>{
        int position, value;
        public node(int position, int value) {
            this.position = position;
            this.value = value;
        }
        //거리 기준 오름차순 정렬
        @Override
        public int compareTo(node o) {
            return this.value - o.value;
        }
    }
    static int answer = Integer.MIN_VALUE;
    public static void main(String[] args) throws IOException{
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        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 r = Integer.parseInt(st.nextToken());
        int[] score = new int[n+1];
        ArrayList<ArrayList<node>> graph = new ArrayList<>();
        for(int i=0;i<=n;i++)
            graph.add(new ArrayList<>());

        st = new StringTokenizer(br.readLine()," ");
        //각 지역 아이템 개수 배열에 저장
        for(int i=1;i<=n;i++)
            score[i] = Integer.parseInt(st.nextToken());
        //양방향 길에 대한 정보 저장
        for(int i=0;i<r;i++) {
            st = new StringTokenizer(br.readLine()," ");
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int l = Integer.parseInt(st.nextToken());

            graph.get(a).add(new node(b, l));
            graph.get(b).add(new node(a, l));
        }
        //각 지역에서 출발했을 때 최대로 먹을 수 있는 아이템 탐색
        for(int i=1;i<=n;i++) 
            answer = Math.max(search(i, graph, score, n, m), answer);
        
        bw.write(answer + "");	//최대 아이템 개수 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
    //BFS탐색을 통해 각 지역에서 탐색범위 안에 먹을 수 있는 아이템 개수 탐색하는 함수
    static int search(int start, ArrayList<ArrayList<node>> graph, int[] score, int size, int max) {
        PriorityQueue<node> q = new PriorityQueue<>();
        boolean[] visited = new boolean[size+1];
        q.add(new node(start, 0));	//출발 지역 저장
        int result = 0;		//먹은 아이템 개수
        //탐색 진행!
        while(!q.isEmpty()) {
            node cur = q.poll();
            if(visited[cur.position] == true)	//이미 최단 거리로 방문한 경우
                continue;
            result += score[cur.position];	//해당 지역 아이템 개수 증가
            visited[cur.position] = true;	//해당 지역 방문 확인
            //인접한 길 탐색!
            for(node next : graph.get(cur.position)) {
                if(!visited[next.position] && max - (cur.value + next.value) >= 0) {
                    q.add(new node(next.position, cur.value + next.value));
                }
            }
        }
        return result;		//먹은 아이템 개수 반환

    }
}