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

문제

https://www.acmicpc.net/problem/18352

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

 

 

풀이

 

모든 간선의 비용이 동일하기 때문에 bfs 탐색을 통해 최단 거리를 찾을 수 있다. 시작점 x에서부터 bfs 탐색을 통해 모든 도시까지의 최단 거리를 구한 후에 k 값과 비교하여 답을 구한다. 

 

 

코드

 

java

 
import java.util.*;
 
public class Main {
 
    static Scanner sc = new Scanner(System.in);
    static List<List<Integer>> graph = new ArrayList<>();
    static int[] distance;
    static boolean[] visited;
 
    public static void main(String[] args) {
        int n, m, k, x;
 
        n = sc.nextInt();
        m = sc.nextInt();
        k = sc.nextInt();
        x = sc.nextInt();
 
        distance = new int[n + 1];
        visited = new boolean[n + 1];
        for (int i=0; i<=n; i++) {
            graph.add(new ArrayList<>());
        }
 
        for (int i=0; i<m; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            graph.get(a).add(b);
        }
 
        List<Integer> result = solve(n, k, x);
        for (int i : result) {
            System.out.println(i);
        }
    }
 
    private static List<Integer> solve(int n, int k, int x) {
        List<Integer> result = new ArrayList<>();
 
        bfs(x);
        boolean check = false;
        for (int i=1; i<=n; i++) {
            if (distance[i] == k) {
                result.add(i);
                check = true;
            }
        }
 
        if (!check) {
            result.add(-1);
        }
 
        return result;
    }
 
    private static void bfs(int x) {
        Queue<Integer> q = new LinkedList<>();
        q.add(x);
        visited[x] = true;
 
        while (!q.isEmpty()) {
            int cur = q.poll();
 
            for (int n : graph.get(cur)) {
                if (!visited[n]) {
                    q.add(n);
                    visited[n] = true;
                    distance[n] = distance[cur] + 1;
                }
            }
        }
    }
}
 

 

python

n, m, k, x = map(int, input().split())
 
graph = [[] for _ in range(n + 1)]
visited = [False] * (n + 1)
distance = [0] * (n + 1)
 
for i in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
 
from collections import deque
 
def bfs(s):
    q = deque()
    q.append(s)
    visited[s] = True
 
    while q:
        cur = q.popleft()
 
        for n in graph[cur]:
            if not visited[n]:
                visited[n] = True
                q.append(n)
                distance[n] = distance[cur] + 1
    
bfs(x)
check = False
for i in range(1, n+1):
    if distance[i] == k:
        print(i)
        check = True
 
if not check: 
    print(-1)