[Java] 백준 14938.서강그라운드

➡️문제 링크

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

 

 

💡아이디어

BFS

처음에는 각 정점마다의 가중치가 달라 다익스트라로 접근해야겠다고 생각했는데,

구현하는 과정에서 무엇을 미리 저장하는 건지 헷갈려서 일단 BFS로 풀었다

 

 

✏️문제 풀이

1. BFS  - 성공

출발지점을 1부터 N까지 돌며 수색범위 내에서 탐색을 진행한다

그리고 그 값들 중 가장 큰 값을 갱신하다.

 

그런데 이 풀이는 정말 운 좋게 맞은거다. 각 정점간의 거리마다 가중치가 다르므로 항상 최단거리를 보장해주지 못하는 로직이다.

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

public class Main {
	static int N, M;
	static int [] item;
	static List<List<int []>> graph = new ArrayList<>();
	static boolean [] visited;
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());	// 지역 수
		M = Integer.parseInt(st.nextToken());	// 수색범위
		int R = Integer.parseInt(st.nextToken());	// 길의 개수
		
		item = new int[N+1];
		st = new StringTokenizer(br.readLine());
		for(int i = 1; i <= N; i++) {
			item[i] = Integer.parseInt(st.nextToken());	// 각 구역별 아이템 수
		}
		
		for(int i = 0; i <= N; i++) graph.add(new ArrayList<>());
		
		for(int r = 0; r < R; r++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());	// 지역 번호 a
			int b = Integer.parseInt(st.nextToken());	// 지역 번호 b
			int c = Integer.parseInt(st.nextToken());	// 길이의 길이
			
			graph.get(a).add(new int [] {b, c});
			graph.get(b).add(new int [] {a, c});
		}
		
		// 구현
		int result = 0;
		for(int i = 1; i <= N; i++) {
			result = Math.max(result, bfs(i));	// 낙하 지점
		}
		
		// 정답
		System.out.println(result);

	}
	
	static int bfs(int start) {
		visited = new boolean[N+1];
		visited[start] = true;	// 출발지점 방문
		
		Queue<int []> que = new LinkedList<>();
		que.add(new int[] {start, 0});	// 정점, 도달 거리값
		
		while(!que.isEmpty()) {
			int [] point = que.poll();
			
			if(point[1] >= M) continue;	// 이미 수색범위 넘어감.
			
			for(int i = 0; i < graph.get(point[0]).size(); i++) {
				int [] arr = graph.get(point[0]).get(i);	// 정점 거리
				
				if(point[1] + arr[1] > M) continue;	// 넘어감
				
				visited[arr[0]] = true;
				que.add(new int [] {arr[0], point[1] + arr[1]});
				
			}
		}
		
		int count = 0;
		for(int i = 1; i <= N; i++) {
			if(visited[i]) count += item[i];
		}
		
		return count;
		
	}

}

 

 

 

2. 다익스트라 - 성공

각 정점을 출발 정점으로 두어, 모든 정점간의 "최소 거리"를 다익스트라를 이용해 구하고(왜냐하면 간선마다 가중치가 다르니까!)

마지막에 각 거리가 수색범위 이하인지 판단하며 최대 아이템을 갱신해나간다.

이렇게 보니 다익스트라를 어떻게 활용하는지 알게 됐다.

나는 처음부터 다익스트라를 돌리면서 바로 수색범위 m을 탐색하려고 했는데 그게 아니었

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

public class Main {
	static int N, M;
	static int [] item;
	static List<List<int []>> graph = new ArrayList<>();
	static int [] dist;
	public static void main(String[] args) throws IOException{
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());	// 지역 수
		M = Integer.parseInt(st.nextToken());	// 수색범위
		int R = Integer.parseInt(st.nextToken());	// 길의 개수
		
		item = new int[N+1];
		st = new StringTokenizer(br.readLine());
		for(int i = 1; i <= N; i++) {
			item[i] = Integer.parseInt(st.nextToken());	// 각 구역별 아이템 수
		}
		
		for(int i = 0; i <= N; i++) graph.add(new ArrayList<>());
		
		for(int r = 0; r < R; r++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());	// 지역 번호 a
			int b = Integer.parseInt(st.nextToken());	// 지역 번호 b
			int c = Integer.parseInt(st.nextToken());	// 길이의 길이
			
			graph.get(a).add(new int [] {b, c});
			graph.get(b).add(new int [] {a, c});
		}
		
		// 구현
		int result = 0;
		for(int i = 1; i <= N; i++) {
			result = Math.max(result, dijkstra(i));	// 낙하 지점
		}
		
		// 정답
		System.out.println(result);

	}
	
	static int dijkstra(int start) {
		dist = new int[N+1];
		Arrays.fill(dist, Integer.MAX_VALUE);
		dist[start] = 0;	// 출발지점 초기화
		
		// 짧은 거리 순으로 pq 정렬 
		PriorityQueue<int []> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
		pq.add(new int[] {start, 0});	// 정점, 도달 거리값
		
		while(!pq.isEmpty()) {
			int [] point = pq.poll();
			int curNum = point[0];	// 현재 정점
			int curDist = point[1];	// 현재 거리
			
			if(dist[curNum] < curDist) continue;	// 현재 경로보다 더 짧은 경로 존재 -> 넘어가기
			
			for(int i = 0; i < graph.get(curNum).size(); i++) {
				int [] next = graph.get(curNum).get(i);	// 정점 거리
				int nextDist = dist[curNum] + next[1];	// 다음 값
				
				if(dist[next[0]] > nextDist) {	// 새로운 정점의 거리가 더 작은경우
					dist[next[0]] = nextDist;
					pq.add(new int[] {next[0], nextDist});
				}
			}
		}
		
		// 수색 범위 M 이내
		int count = 0;
		for(int i = 1; i <= N; i++) {
			if(dist[i] <= M) count += item[i];
		}
		
		return count;
		
	}

}

 

 

 

가중치가 양수 + 간선마다 가중치 다름 

-> 다익스트라 잊지 말자!