접근
이러한 최단거리 문제를 풀 때, 현재 그래프의 데이터를 저장하는 데에는 두 가지 방식이 있다. 간단하게는 이차원 배열을 선언해서 연결된 곳에는 그에 해당하는 거리를, 갈 수 없는 노드라면 -1 혹은 INF값을 저장해놓는 방식이다. 다만 이 경우에는 NxN 으로 모든 노드의 연결 여부를 저장하므로, 간선의 개수가 적은 편이라면 메모리를 낭비하게 된다. 즉, N값이 커지면 메모리 초과가 날 수도 있다는 얘기다.
두 번째로는 이차원 ArrayList를 통해 서로 연결된 노드의 정보만을 저장하는 방식이다. 첫 번째 방식보다 코드 구현 측면에서는 더 복잡하지만, 노드 개수에 비해 간선의 개수가 적다면 이 방식이 더 효율적이다. 나는 두번째 방식으로 풀었다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class BJ18352 {
static class City {
int num, dist;
City(int num, int dist){
this.num = num;
this.dist = dist;
}
}
static int INF = -1;
static ArrayList<ArrayList<Integer>> graph;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = null;
ArrayList<Integer> answer = new ArrayList<>();
// 입력값 저장
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());
graph = new ArrayList<>();
int[] dist = new int[n+1];
for (int i = 0; i <= n; i++) {
graph.add(new ArrayList<>());
dist[i] = INF;
}
for (int i = 0; i < m; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
graph.get(a).add(b);
}
// 다익스트라
dijkstra(dist, x);
// 거리가 같은 도시의 개수 세기
for (int i = 1; i <= n; i++) {
if(dist[i] == k)
answer.add(i);
}
if(answer.size() == 0){
System.out.println(-1);
}
else{
Collections.sort(answer);
for (int i = 0, s = answer.size(); i < s; i++) {
System.out.println(answer.get(i));
}
}
}
static void dijkstra(int[] dist, int x){
Queue<City> q = new LinkedList<>();
// 시작 지점 처리
q.add(new City(x, 0));
dist[x] = 0;
while(!q.isEmpty()){
City cur = q.poll();
for(int node : graph.get(cur.num)){
if(dist[node] == INF || dist[node] > cur.dist+1) {
dist[node] = cur.dist+1;
q.add(new City(node, cur.dist+1));
}
}
}
}
}'Algorithm' 카테고리의 다른 글
| [백준] 1916: 최소비용 구하기 JAVA, C++ (0) | 2023.02.06 |
|---|---|
| [백준] 1446: 지름길 JAVA (0) | 2023.02.03 |
| [백준] 2812: 크게 만들기 JAVA (0) | 2023.01.31 |
| [백준] 1715: 카드 정렬하기 JAVA (0) | 2023.01.30 |
| [백준] 11000: 강의실 배정 JAVA (0) | 2023.01.29 |
