[자바] 백준 18352 - 특정 거리의 도시 찾기 (java)

목차

문제 : boj18352

 

 

필요 알고리즘

• 너비 우선 탐색(BFS)
  
  • 일반적인 BFS 탐색에서, 최단 거리에 목적지를 도착하는게 아니고 특정 거리인 지점을 찾는다는점만 다르다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  BFS를 잘 모른다면 'BFS 알고리즘 (너비 우선 탐색)' 글을 참고해보자.

일반적인 BFS 알고리즘으로 구현해주면 되는데, 목적지까지의 최단 거리를 구하는게 아니라 특정 거리인 위치를 찾는다는 점이 다르다. 거리 데이터만 잘 관리해주면 되고, K를 초과한 경우 더이상 BFS를 진행하지 않고 종료해주면 된다.

while (!q.isEmpty()) {	// BFS 진행
    int cur = q.poll();
    if (dist[cur] > k) break;	// 현재 거리가 K를 넘으면 종료
    if (dist[cur] == k) answer.add(cur);	// 출발지점에서 거리가 K라면 결과 리스트에 추가

    for (int next : edges[cur]) {	// 간선 순회
        if (dist[next] != INF) continue;	// 방문 체크
        dist[next] = dist[cur]+1;	// 다음 위치는 현재 지점의 거리+1
        q.add(next);	// 다음 위치 진행
    }
}

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static final int INF = -1;

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    private void solution() throws Exception {
        StringTokenizer 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());

        List<Integer>[] edges = new List[n+1];
        for (int i = 1; i <= n; i++) edges[i] = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            edges[a].add(b);
        }

        int[] dist = new int[n+1];
        Arrays.fill(dist, INF);
        Queue<Integer> q = new ArrayDeque<>();
        q.add(x);
        dist[x] = 0;

        List<Integer> answer = new ArrayList<>();

        while (!q.isEmpty()) {
            int cur = q.poll();
            if (dist[cur] > k) break;
            if (dist[cur] == k) answer.add(cur);

            for (int next : edges[cur]) {
                if (dist[next] != INF) continue;
                dist[next] = dist[cur]+1;
                q.add(next);
            }
        }

        Collections.sort(answer);
        StringBuilder sb = new StringBuilder();
        for (int cur : answer) {
            sb.append(cur).append('\n');
        }

        System.out.print(answer.isEmpty() ? -1 : sb);
    }
}