https://www.acmicpc.net/problem/18352
문제
> 어떤 나라에는 1번부터 N번까지의 도시와 M개의 단방향 도로가 존재한다.
> 모든 도로의 거리는 1이다.
> 이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서,
최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오.
> 또한 출발 도시 X에서 출발 도시 X로 가는 최단 거리는 항상 0이라고 가정한다.
> 예를 들어 N=4, K=2, X=1일 때 다음과 같이 그래프가 구성되어 있다고 가정하자.
> 이 때 1번 도시에서 출발하여 도달할 수 있는 도시 중에서,
최단 거리가 2인 도시는 4번 도시 뿐이다.
> 2번과 3번 도시의 경우, 최단 거리가 1이기 때문에 출력하지 않는다.
접근
문제에 주어진 도시들의 연결관게를 이용해 각 도시별로 시작점 X부터 갈 수 있는 최단거리를 구한다.
그래프 탐색을 이용하여 최단 거리를 구하고 주어진 k와 비교해서 같은 값을 가지는 도시를 출력한다.
문제해결
> 도시 수 N, 도로 수 M, 원하는 거리 K, 시작도시 X를 입력받는다.
> 각 도시별 최단거리를 저장할 dist배열을 선언한다.
> 최단거리로 갱신하기위해 초기값을 정수형 최대값으로 준다.
> 도시들의 관계를 저장할 이차원 리스트 city를 선언한다.
> M개의 도로의 관계를 입력받고 가중치 1로 앞선 city리스트에 저장한다.
> 최단거리를 구하는 메소드 BFS에 시작점을 넣고 호출한다.
> BFS에서 우선순위 큐로 가중치가 작은 거리부터 뽑아와서 다룬다.
> 시작점 -> 시작점은 0이므로 초기화 해주고, 시작점을 큐에 넣고 탐색한다.
> 큐의 맨 앞의 값을 매번 잡아와 현재 위치한 도시를 fdot, 현재까지 오는데 든 비용을 fcost에 담는다.
> 다음 경로를 탐색하기 전, 큐에서 가져온 해당 비용이 이미 해당 도시의 최소 값보다 큰 경우 볼 필요가 없으므로 continue한다.
> 현 도시와 관계된 도시와 가중치를 i로 가져오고 ndot, ncost에 저장한다.
> 최단거리 갱신을 위해, fcost에 다음 도시로 가는 비용을 더했을 때,
그 비용이 다음 도시에 저장된 비용보다 작으면 최단거리를 갱신해준다.
> 갱신되면 해당 도시에서 또 다음 도시로 가기위해 큐에 넣어준다.
> 위 과정을 큐가 빌때 까지 해주고 끝나면 dist에 각 도시별 최단거리가 저장된다.
> 모든 도시의 최단거리를 보며 K와 같은 도시를 출력한다.코드
import java.io.*;
import java.util.*;
import java.lang.*;
public class Main {
//18352번 특정 거리의 도시 찾기
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static StringBuilder sb = new StringBuilder();
static int N, M, K, X;
static List<List<int[]>> city;
static int[] dist;
static void BFS(int start) {
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[1], b[1]));
dist[start] = 0;
pq.add(new int[]{start, 0});
while(!pq.isEmpty()) {
int[] f = pq.poll();
int fdot = f[0];
int fcost = f[1];
if(dist[fdot] < fcost) continue;
for(int[] i : city.get(fdot)) {
int ndot = i[0];
int ncost = i[1];
if(dist[ndot] > fcost + ncost) {
dist[ndot] = fcost + ncost;
pq.add(new int[]{ndot, dist[ndot]});
}
}
}
}
public static void main(String[] args) throws IOException {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
X = Integer.parseInt(st.nextToken());
dist = new int[N+1];
Arrays.fill(dist, Integer.MAX_VALUE);
city = new ArrayList<>();
for(int i = 0; i <= N; i++) city.add(new ArrayList<>());
for(int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
city.get(Integer.parseInt(st.nextToken())).add(new int[]{Integer.parseInt(st.nextToken()), 1});
}
BFS(X);
for(int i = 1; i <= N; i++) {
if(dist[i] == K) sb.append(i).append('\n');
}
if(sb.length() == 0) sb.append(-1);
System.out.print(sb);
}
}
후기
가중치가 1이므로 BFS로 쉽게 풀 수 있는데 다익스트라를 연습하기위해 일부러 다익스트라로 풀었다. c++에선 꽤 쉬운데 자바는 복잡하고 어렵다 많이 연습해보자 문법을
