[백준BOJ] 14221번 편의점.java

 

백준 저지에서 편의점을 자바를 통해 풀어 보았다. 

 

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

14221번: 편의점

 

14221번 편의점.java

GitHub - tomy9729/Algorithm: 🐗 내가 직접 작성한 내 코드 🐗

 

14221번 편의점

문제

영선이는 이사할 일이 생겨 집을 알아보고 있다. 영선이는 혼자 살기 때문에, 편의점에서 대충 때울 때가 많아, 집을 고르는 기준을 편의점과의 거리가 가장 가까운 곳으로 하려한다.
영선이가 이사할 도시는 정점과 간선으로 표현할 수 있는데, 이사가려 하는 집의 후보들과 편의점은 정점들 위에 있다.
영선이는 캠프 강사 준비로 바쁘므로, 대신하여 집을 골라주자. 만약 거리가 같은 지점이 여러 개라면 정점 번호가 가장 낮은 곳으로 골라주자.

설명

다익스트라 알고리즘을 활용해서 푼다.

 

집 후보들을 출발점으로 하여 다익스트라를 통해 각 편의점에 대한 거리를 구한다. 각 거리들과 집이 있는 정점번호들을 비교하여 문제의 조건에 맞는 답을 도출한다. 

코드

//14221번 편의점.java
package boj20211213;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class 편의점_14221 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    static final int maxNum = Integer.MAX_VALUE;
    
    public static void main(String[] args) throws IOException {
    	st = new StringTokenizer(br.readLine()," ");
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		ArrayList<ArrayList<edge>> graph = new ArrayList();
		for(int i=0;i<=N;i++) {
			graph.add(new ArrayList<edge>());
		}
		
		for(int i=0;i<M;i++) {
			st = new StringTokenizer(br.readLine()," ");
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			int value = Integer.parseInt(st.nextToken());
			graph.get(from).add(new edge(to, value));
			graph.get(to).add(new edge(from, value));
		}
		
		st = new StringTokenizer(br.readLine()," ");
		int houseCount = Integer.parseInt(st.nextToken());
		int[] house = new int[houseCount];
		int cuCount = Integer.parseInt(st.nextToken());
		int[] cu = new int[cuCount];
		
		st = new StringTokenizer(br.readLine()," ");
		for(int i=0;i<houseCount;i++) {
			house[i] = Integer.parseInt(st.nextToken());
		}
		
		st = new StringTokenizer(br.readLine()," ");
		for(int i=0;i<cuCount;i++) {
			cu[i] = Integer.parseInt(st.nextToken());
		}
		
		int from=0;
		int dis=Integer.MAX_VALUE;
		
		for(int i=0;i<houseCount;i++) {
			int[] root = new int[N+1];
			Arrays.fill(root,Integer.MAX_VALUE);
			dijkstra(graph, root, house[i]);
			for(int j=0;j<cuCount;j++) {
				//도착 편의점 cu[j]
				//출발 집 house[i]
				if(dis > root[cu[j]] || (dis==root[cu[j]] && from > house[i])) {
					from = house[i];
					dis = root[cu[j]];
				}
			}
		}
		System.out.println(from);
	}
    
    static void dijkstra(ArrayList<ArrayList<edge>> graph,int[] root, int start) {
		root[start]=0;
		PriorityQueue<edge> pq = new PriorityQueue<>();
		pq.add(new edge(start,0));
		
		while(!pq.isEmpty()) {
			edge now = pq.poll();
			if(root[now.to] < now.value)continue;
			
			for(int i=0;i<graph.get(now.to).size();i++) {
				edge next = graph.get(now.to).get(i);
				if(now.value+next.value < root[next.to]) {
					root[next.to] = now.value+next.value;
					pq.add(new edge(next.to,root[next.to]));
				}
			}
		}
	}
    static class edge implements Comparable<edge>{
    	int to;
    	int value;
    	edge(int to, int value){
    		this.to=to;
    		this.value=value;
    	}
		@Override
		public int compareTo(edge o) {
			return Integer.compare(this.value, o.value);
		}
    }
}