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

+ Recent posts

티스토리툴바