백준 18352번: 특정 거리의 도시 찾기

문제 설명

• https://www.acmicpc.net/problem/18352
• 시작점으로부터 최소거리가 K인 위치들을 찾는 문제입니다.

접근법

• A도시에서 나머지 도시로의 최소거리를 구하는 것이기 때문에 다익스트라를 사용했습니다.
• N이 300_000으로 매우 커 2차원 배열이 아닌 map을 사용했습니다.
• 시간초과가 많이났습니다.
  • 최종적으로 if(d[j]>K) continue;코드를 삽입해 아슬아슬하게 통과했습니다.

정답

import java.util.*;

import org.w3c.dom.Node;

import java.io.*;

public class Main {
	static int cnt = 0;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		int X = Integer.parseInt(st.nextToken());
		HashMap<Integer,List<Integer>> map = new HashMap<Integer,List<Integer>>();
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			if(map.containsKey(a)) {
				map.get(a).add(b);
			}else {
				List<Integer> temp = new ArrayList<Integer>();
				temp.add(b);
				map.put(a, temp);
			}			
		}
		List<Node> lst = Djk(N,K,X,map);
		if(lst.size() ==0) {
			System.out.println(-1);
		}else {			
			Collections.sort(lst);
			StringBuilder sb = new StringBuilder();
			for (int i = 0; i < lst.size(); i++) {
				sb.append(lst.get(i).order +"\n");
			}
			System.out.println(sb.toString());
		}
	}
	
	public static List<Node> Djk(int N, int K, int X, HashMap<Integer,List<Integer>>map) {
		int[] d = new int[N+1];
		boolean[] v = new boolean[N+1];
		PriorityQueue<Vertex> pq = new PriorityQueue<Vertex>();
		Arrays.fill(d, Integer.MAX_VALUE);
		d[X] = 0;
		pq.add(new Vertex(X,d[X]));
		while(!pq.isEmpty()) {
			Vertex current = pq.poll();
			if(v[current.no]) continue;
			v[current.no] = true;
			for (int j = 1; j <= N; j++) {
				if(!map.containsKey(current.no)) continue;
				if(!contain(map.get(current.no),j)) continue;
				if(!v[j] && d[j] > d[current.no] + 1) {
					d[j] = d[current.no] + 1;
					if(d[j]>K) continue; // 시간단축에 큰 도움
					pq.add(new Vertex(j,d[j]));
				}
			}
		}
		List<Node> temp = new ArrayList<Node>();
		for (int i = 1; i <= N; i++) {
			if(d[i] == K) {				
				temp.add(new Node((i),d[i]));
			}
		}
		return temp;
		
	}
	static class Node implements Comparable<Node>{
		int order;
		int dist;
		public Node(int order, int dist) {
			super();
			this.order = order;
			this.dist = dist;
		}
		@Override
		public String toString() {
			return "Node [order=" + order + ", dist=" + dist + "]";
		}
		@Override
		public int compareTo(Node o) {
			return this.order - o.order;
		}
		
	}
	
	public static boolean contain(List<Integer> lst,int a) {
		for (int i = 0; i < lst.size(); i++) {
			if(lst.get(i) == a) return true;
		}
		return false;
	}
	
	
	static class Vertex implements Comparable<Vertex>{
		int no;
		int minD;
		public Vertex(int no, int minD) {
			super();
			this.no = no;
			this.minD = minD;
		}
		@Override
		public String toString() {
			return "Vertex [no=" + no + ", minD=" + minD + "]";
		}
		@Override
		public int compareTo(Vertex o) {
			return this.minD - o.minD;
		}
		
	}
	
	
}