백준 14938 java - 서강 그라운드(플루이드와샬, 다익스트라)

문제, 입출력, 테스트케이스

해당 문제는 35분여간 bfs로 풀다가 밑에 문제 분류 보고 플루이드와샬, 다익스트라인 걸 보고 바로 플루이드와샬로 돌려서 풀었다. 그 과정에서 문제를 입력값을 제대로 안봐서 m, r를 혼동하는 바람에 이왜틀 3분간 시전...

<문제 풀이/접근과정>
1. A에서 B까지 가는 거리가 m(수색가능 범위) 이내면 아이템 회수 가능
2. BFS돌리면서 계속 합해줘서 MAX값 찾아야 겠다.
3. 이왜틀???? 아! bfs로 방문처리하면 더 최단거리가 될 수 있음에도 불구하고 방문처리돼서 최단거리로 가는 게 아닐 수 있겠구나
4. 다익스트라 구현보다 플루이드와샬이 구현할 때 더 빠르니까 플와 써야겠다.
5. 문제 접근, 풀이, 제출, pass까지 약 50분 소요

<틀린 코드 - BFS>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static int n, m, r, item[], max;
	static List[] v;
	static boolean visited[];
	public static void main(String[] args) throws IOException {
		
		//입력
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stz = new StringTokenizer(br.readLine());
		n = Integer.parseInt(stz.nextToken());
		m = Integer.parseInt(stz.nextToken());
		r = Integer.parseInt(stz.nextToken());
		v = new ArrayList[n+1];// 0번째 패딩
		item = new int[n+1];
		stz = new StringTokenizer(br.readLine());
		
		// 아이템 수 입력
		for (int i = 1; i <= n; i++) {
			item[i] = Integer.parseInt(stz.nextToken());
		}
		
		// 간선 리스트 초기화 node, distance
		for (int i = 0; i <= n; i++) {
			v[i] = new ArrayList<int[]>();
		}
		
		for (int i = 0; i < r; i++) {
			stz = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(stz.nextToken());
			int to = Integer.parseInt(stz.nextToken());
			int dist = Integer.parseInt(stz.nextToken());
			
			v[from].add(new int[] {to, dist});
			v[to].add(new int[] {from, dist});
		}
		
		max = 0;
		//처리
		for (int i = 1; i <= n; i++) {
			visited = new boolean[n+1];
			visited[i] = true;
			bfs(i, m);
		}
		
		
		//출력
		System.out.println(max);
	}
	private static void bfs(int start, int spareDist) {
		int totalItemCnt = item[start];
		
		Queue<int[]> q = new LinkedList<>();
		q.add(new int[] {start, spareDist});
		while(!q.isEmpty()) {
			int size = q.size();
			for (int j = 0; j < size; j++) {
				int temp[] = q.poll();
				int from = temp[0];
				
				List<int[]> tmpL = v[from];
				for (int i = 0; i < tmpL.size(); i++) {
					int to = tmpL.get(i)[0];
					int dist = tmpL.get(i)[1];
					int spareD = temp[1];
					
					if(visited[to])continue;
					
					if(dist <= spareD) {
//						System.out.println("from : " + from +", to : " + to +", dist : " + dist);
						totalItemCnt += item[to];
						spareD -= dist;
						visited[to] = true;
						q.add(new int[] {to, spareD});
					}
				}
			}
		}
		max = Math.max(max, totalItemCnt);
	}
}

<맞은 코드 - 플루이드 와샬>

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
	static int n, m, r, item[], max;
	static boolean visited[];
	public static void main(String[] args) throws IOException {
		
		//입력
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stz = new StringTokenizer(br.readLine());
		n = Integer.parseInt(stz.nextToken());
		m = Integer.parseInt(stz.nextToken());
		r = Integer.parseInt(stz.nextToken());
		item = new int[n+1];
		stz = new StringTokenizer(br.readLine());
		
		// 아이템 수 입력
		for (int i = 1; i <= n; i++) {
			item[i] = Integer.parseInt(stz.nextToken());
		}
		
		int distance[][] = new int[n+1][n+1];
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if(i == j)continue;
				distance[i][j] = 10000000;
			}
		}
		
		for (int i = 0; i < r; i++) {
			stz = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(stz.nextToken());
			int to = Integer.parseInt(stz.nextToken());
			int dist = Integer.parseInt(stz.nextToken());
			distance[from][to] = dist;
			distance[to][from] = dist;
		}
		//처리
		max = 0;
		
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if(i == j)continue;
				for (int k = 1; k <= n; k++) {
					if(j == k)continue;
					distance[j][k] = Math.min(distance[j][k], distance[j][i] + distance[i][k]);
				}
			}
		}
		int dp[] = new int[n+1];
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if(distance[i][j] <= m) {
					dp[i] += item[j];
				}
			}
			max = Math.max(dp[i], max);
		}
		
		//출력
		System.out.println(max);
	}
}