[devmoon]백준 14938 - 서강그라운드

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

14938번: 서강그라운드

1. 유형

shotest path

 

2. 시뮬레이션

최단거리 구하는 문제입니다.

추가적인 조건 없이 정석적인 다익스트라, 플로이드와샬을 구현할 수 있다면 어려울거 없는 문제입니다.

시간복잡도가 100^3이기 때문에 플로이드와샬도 사용가능합니다.

 

다익스트라

• 인접리스트 구현
• 1~N번 노드까지 시작노드 설정하고 다익스트라 돌리기

---

플로이드 와샬

• 2차원 배열 구현
• 플로이드와샬 알고리즘 돌리기

 

3. 코드

다익스트라

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

public class Main {
	static int N, M, R, arr[], INF = 987654321, maxvalue = 0;
	static List<Pair> list[];
	static PriorityQueue<Pair> pq;

	static class Pair {
		int node, dist;

		Pair(int node, int dist) {
			this.node = node;
			this.dist = dist;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		N = stoi(st.nextToken());
		M = stoi(st.nextToken());
		R = stoi(st.nextToken());
		init();
		st = new StringTokenizer(in.readLine());
		for (int i = 0; i < N; i++) {
			arr[i] = stoi(st.nextToken());
			list[i] = new ArrayList<>();
		}
		for (int i = 0; i < R; i++) {
			st = new StringTokenizer(in.readLine());
			int u = stoi(st.nextToken()) - 1;
			int v = stoi(st.nextToken()) - 1;
			int w = stoi(st.nextToken());
			list[u].add(new Pair(v, w));
			list[v].add(new Pair(u, w));
		}
		for (int target = 0; target < N; target++) {
			int shortest[] = new int[N];
			Arrays.fill(shortest, INF);
			pq = new PriorityQueue<>((e1, e2) -> {
				return e1.dist - e2.dist;
			});
			pq.add(new Pair(target, 0));
			boolean visit[] = new boolean[N];
			shortest[target] = 0;
			int sum = 0;
			while (!pq.isEmpty()) {
				Pair cur = pq.poll();
				if (visit[cur.node])
					continue;
				visit[cur.node] = true;
				sum += arr[cur.node];
				for (Pair nextnode : list[cur.node]) {
					if (!visit[nextnode.node] && shortest[nextnode.node] > shortest[cur.node] + nextnode.dist
							&& shortest[cur.node] + nextnode.dist <= M) {
						shortest[nextnode.node] = shortest[cur.node] + nextnode.dist;
						pq.add(nextnode);
					}
				}
			}
			maxvalue = Math.max(sum, maxvalue);
		}
		System.out.println(maxvalue);
	}

	static void init() {
		arr = new int[N];
		list = new ArrayList[N];
	}

	static int stoi(String s) {
		return Integer.valueOf(s);
	}
}

---

플로이드와샬

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

public class Main {
	static int N, M, R, arr[], INF = 987654321, maxvalue = 0;
	static int map[][];

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(in.readLine());
		N = stoi(st.nextToken());
		M = stoi(st.nextToken());
		R = stoi(st.nextToken());
		init();
		st = new StringTokenizer(in.readLine());
		for (int i = 0; i < N; i++) {
			arr[i] = stoi(st.nextToken());
		}
		for (int i = 0; i < R; i++) {
			st = new StringTokenizer(in.readLine());
			int u = stoi(st.nextToken()) - 1;
			int v = stoi(st.nextToken()) - 1;
			int w = stoi(st.nextToken());
			map[u][v] = w;
			map[v][u] = w;
		}
		for (int mid = 0; mid < N; mid++) {
			for (int start = 0; start < N; start++) {
				for (int end = 0; end < N; end++) {
					if (start!=end && map[start][mid] + map[mid][end] < map[start][end]) {
						map[start][end] = map[start][mid] + map[mid][end];
					}
				}
			}
		}
		for(int i=0;i<N;i++) {
			int sum=arr[i];
			for(int j=0;j<N;j++) {
				if(map[i][j]<=M) {
					sum+=arr[j];
				}
			}
			maxvalue=Math.max(maxvalue, sum);
		}
		System.out.println(maxvalue);
	}

	static void init() {
		arr = new int[N];
		map = new int[N][N];
		for (int i = 0; i < N; i++) {
			Arrays.fill(map[i], INF);
		}
	}

	static int stoi(String s) {
		return Integer.valueOf(s);
	}
}