https://www.acmicpc.net/problem/18352
18352번: 특정 거리의 도시 찾기
첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개
www.acmicpc.net
코드설명
다익스트라(Dijkstra) 혹은 BFS(너비우선탐색) 를 통해 해결할 수 있는 문제입니다.
다익스트라(Dijkstra)를 활용하여 풀경우에는 시간초과가 납니다.
시간복잡도를 비교해보겠습니다.
다익스트라의 시간복잡도는 O(ELogV) 입니다.
E는 간선의 개수, V는 노드의 개수입니다.
문제에 주어진 조건은
- 노드의 개수는, 2 ≤ N ≤ 300,000개입니다.
- 간선의 개수는 1 ≤ M ≤ 1,000,000개 입니다.
시간복잡도는 O( 1,000,000 * Log ( 300,000 ) )
BFS의 시간복잡도는 O(E + V)의 시간복잡도를 가집니다.시간복잡도는 O( 300,000 + 1,000,000 ) 입니다.
그렇기에, BFS를 활용하여 진행합니다.
코드
BFS를 활용한코드입니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static int N, M, K, X;
public static int[] arr;
public static int answer = 0;
public static ArrayList<ArrayList<Node>> graph = new ArrayList<ArrayList<Node>>();
public static boolean[] visited;
public static ArrayList<Integer> arrstr = new ArrayList<Integer>();
public static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer 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());
visited = new boolean[N+1];
for(int i=0;i<=N;i++) {
graph.add(new ArrayList<Node>());
}
for(int i=0;i<M;i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
//a번 노드에서 b노드로 가는 비용이 1 입니다.
graph.get(a).add(new Node(b, 1));
}
BFS(X);
Collections.sort(arrstr);
if(arrstr.size() == 0) {
System.out.println("-1");
}else {
for(int i=0;i<arrstr.size();i++) {
System.out.println(arrstr.get(i));
}
// System.out.println(sb.toString());
}
}
public static void BFS(int start) {
Queue<Node> q = new LinkedList<>();
q.offer(new Node(start, 0));
visited[start] = true;
while(!q.isEmpty()) {
Node temp = q.poll();
if(temp.cnt == K) {
// sb.append(temp.nodeB).append("\n");
arrstr.add(temp.nodeB);
}else if(temp.cnt > K) {
return ;
}
for(int i=0;i<graph.get(temp.nodeB).size();i++) {
Node next = graph.get(temp.nodeB).get(i);
if(visited[next.nodeB]) continue;
visited[next.nodeB] = true;
q.offer(new Node(next.nodeB, temp.cnt + 1));
}
}
}
}
class Node {
int nodeB;
int cnt;
public Node(int nodeB, int cnt) {
this.nodeB = nodeB;
this.cnt = cnt;
}
}
정답코드 2입니다.
qSize를 조절해서 처리하는 코드입니다.
정답코드 1번이 더 로직이 줄어들어 구현하기에 편합니다. BFS상에서 애초에 너비우선탐색이기에 이동한 횟수를 같이 처리한다면 몇번째까지가 BFS인지 쉽게 알 수 있습니다.
package Main;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
public class Main {
static int N, M, S, P, K, A, B, X;
// static int answer = 0;
static int[][] matrix;
static ArrayList<Integer> answer = new ArrayList<Integer>();
static ArrayList<Integer>[] arr;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer 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());
arr = new ArrayList[N];
for(int i=0;i<N;i++) {
arr[i] = new ArrayList<Integer>();
}
for(int i=0;i<M;i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken()) - 1;
int b = Integer.parseInt(st.nextToken()) - 1;
arr[a].add(b);
}
BFS(X-1);
Collections.sort(answer);
if(answer.size() == 0) {
System.out.println(-1);
return ;
}
for(int v : answer) {
System.out.println(v + 1);
}
}
static void BFS(int now) {
Queue<Integer> q = new LinkedList<>();
boolean[] visited = new boolean[N];
visited[now] = true;
q.offer(now);
int qSize = q.size();
int depth = 0;
while(qSize-- > 0) {
int temp = q.poll();
for(int next = 0; next < arr[temp].size(); next++) {
int nextNode = arr[temp].get(next);
if(visited[nextNode] == true) continue;
visited[nextNode] = true;
q.offer(nextNode);
}
if(qSize == 0) {
depth += 1;
qSize = q.size();
if(depth == K) {
while(!q.isEmpty()) {
answer.add(q.poll());
}
return ;
}
}
}
}
}
다익스트라 시간초과 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static int N, M, K, X;
public static int[] arr;
public static int answer = 0;
public static ArrayList<ArrayList<Node>> graph = new ArrayList<ArrayList<Node>>();
public static int[] d = new int[300001];
public static StringBuilder sb = new StringBuilder();
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer 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());
Arrays.fill(d, Integer.MAX_VALUE);
for(int i=0;i<=N;i++) {
graph.add(new ArrayList<Node>());
}
for(int i=0;i<M;i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
//a번 노드에서 b노드로 가는 비용이 1 입니다.
graph.get(a).add(new Node(b, 1));
}
dijkstra(X);
boolean flag = false;
for(int i=1; i<=N;i++) {
if(d[i] == K) {
sb.append(i).append("\n");
flag = true;
}else {
}
}
if(flag == false) {
System.out.println("-1");
}else {
System.out.println(sb.toString());
}
}
public static void dijkstra(int start) {
PriorityQueue<Node> pq = new PriorityQueue<>();
pq.offer(new Node(start, 0));
d[start] = 0;
while(!pq.isEmpty()) {
Node temp = pq.poll();
int dist = temp.weight;
int now = temp.nodeB;
//현재 노드가 이미 처리된적이 있는 노드라면 무시
if(d[now] < dist) continue;
for(int i=0;i<graph.get(now).size();i++) {
int cost = d[now] + graph.get(now).get(i).weight;
if(cost < d[graph.get(now).get(i).nodeB]) {
d[graph.get(now).get(i).nodeB] = cost;
pq.offer(new Node(graph.get(now).get(i).nodeB, cost));
}
}
}
}
}
class Node implements Comparable<Node>{
int nodeB;
int weight;
@Override
public int compareTo(Node other) {
if(this.weight < other.weight) {
return 1;
}else if(this.weight == other.weight) {
return 0;
}else {
return -1;
}
}
public Node(int nodeB, int weight) {
this.nodeB = nodeB;
this.weight = weight;
}
}
DFS를 활용하여 틀린 코드입니다. 최단거리일경우에만 작동해야하지만 그렇지 않습니다.
즉, 만약 3번 위치의 최단거리로 갔을때 1->3번이 1번이라고 가정합니다.
그런데 1->2->3 번으로도 갈 수 있다고 3번의 최단거리가 2가 아닙니다. 그렇기에 BFS를 활용합니다.
package Main;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
public class Main {
static int N, M, S, P, K, A, B, X;
// static int answer = 0;
static int[][] matrix;
static ArrayList<Integer> answer = new ArrayList<Integer>();
static ArrayList<Integer>[] arr;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer 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());
arr = new ArrayList[N];
for(int i=0;i<N;i++) {
arr[i] = new ArrayList<Integer>();
}
for(int i=0;i<M;i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken()) - 1;
int b = Integer.parseInt(st.nextToken()) - 1;
arr[a].add(b);
}
boolean[] visited = new boolean[N];
visited[X-1] = true;
dfs(0, X - 1, visited);
Collections.sort(answer);
if(answer.size() == 0) {
System.out.println(-1);
return ;
}
for(int v : answer) {
System.out.println(v);
}
}
static void dfs(int depth, int now, boolean[] visited) {
if(depth == K) {
answer.add(now + 1);
return ;
}
for(int connected = 0; connected < arr[now].size(); connected++) {
int nextNode = arr[now].get(connected);
if(visited[nextNode] == false) {
visited[nextNode] = true;
dfs(depth + 1, nextNode, visited);
visited[nextNode] = false;
}
}
}
}'알고리즘 > Shortest Path' 카테고리의 다른 글
| [백준] 1254 팰린드롬 만들기 - 문자열(String) + 브루트포스(BruteForce) JAVA (0) | 2024.10.11 |
|---|---|
| [백준] 14938 서강그라운드 - 다익스트라(Dijkstra) JAVA (0) | 2023.08.31 |
| [백준] 1753 최단경로 - 다익스트라(Dijkstra) JAVA (0) | 2023.08.28 |
| [백준] 1504 특정한 최단 경로 - 다익스트라(Dijkstra) JAVA (0) | 2023.08.27 |
| [백준] 1238 파티 - 다익스트라(Dijkstra) JAVA (0) | 2023.08.12 |