자바 코딩테스트 강좌, 특정 거리의 도시 찾기

안녕하세요, 여러분! 오늘은 자바를 활용한 취업 준비를 위한 알고리즘 문제를 다루어 보겠습니다. 이번 주제는 “특정 거리의 도시 찾기”로, 그래프 이론과 BFS(너비 우선 탐색) 알고리즘을 활용할 것입니다. 이 문제를 풀면서 알고리즘의 바탕이 되는 개념들과 자바의 유용한 자료구조를 어떻게 활용할 수 있는지 심도 깊게 알아보겠습니다.

문제 설명

주어진 도시들이 서로 길로 연결되어 있고, 각 도시는 번호로 표시됩니다. 만약 1번 도시에서 출발하여 특정 거리 K를 이동했을 때 도달할 수 있는 도시를 모두 찾아 반환하는 문제입니다. 즉, 입력으로는 도시의 수 N, 도로의 수 M, 출발 도시 X, 그리고 목표 거리 K가 주어지며, 도달할 수 있는 도시 번호를 오름차순으로 정렬하여 출력해야 합니다.

입력

  • 첫 번째 줄: 도시의 수 N (1 ≤ N ≤ 30000), 도로의 수 M (1 ≤ M ≤ 200000)
  • 두 번째 줄: 출발 도시 번호 X (1 ≤ X ≤ N)와 목표 거리 K (0 ≤ K ≤ 30000)
  • 다음 M줄: 연결된 두 도시 A, B (1 ≤ A, B ≤ N, A ≠ B)

출력

목표 거리 K에 도달할 수 있는 도시의 번호를 오름차순으로 출력합니다. 만약 도달할 수 있는 도시는 없다면 -1을 출력합니다.

풀이 접근법

이 문제를 해결하기 위해 우리는 그래프를 구성하고 BFS 알고리즘을 사용하여 주어진 거리 K에 도달 가능한 도시를 찾아야 합니다. BFS는 그래프의 모든 정점을 레벨 순서대로 방문하기 때문에 특정 거리의 도시에 도달하는 데 적합한 방법입니다.

1단계: 그래프 표현

도시 간의 도로 관계를 표현하기 위해 인접 리스트를 사용합니다. 자바에서는 ArrayList를 활용하여 각 도시의 인접 도시를 저장할 수 있습니다. 이렇게 하면 메모리 사용을 최소화하고 도시 간의 관계를 쉽게 관리할 수 있습니다.

2단계: BFS 구현

BFS를 구현하기 위해 큐를 사용합니다. 큐는 현재 도시와 현재 거리를 저장하며, 이 거리가 K에 도달할 때까지 탐색을 계속합니다. 탐색 과정에서 이미 방문한 도시는 다시 방문하지 않도록 주의해야 합니다. 또한 목표 거리를 정확히 K와 비교해야 합니다.

3단계: 결과 출력

목표 거리 K에 도달한 도시를 수집하여 오름차순으로 정렬한 후 출력합니다. 만약 아무 도시도 도달하지 못했다면 -1을 출력합니다.

자바 코드 예시


import java.util.*;

public class SpecificDistanceCity {
    static ArrayList[] graph;
    static boolean[] visited;
    static int[] distance;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt(); // 도시의 수
        int M = sc.nextInt(); // 도로의 수
        int X = sc.nextInt(); // 출발 도시
        int K = sc.nextInt(); // 목표 거리

        // 그래프 초기화
        graph = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            graph[i] = new ArrayList<>();
        }

        // 도로 정보 입력받기
        for (int i = 0; i < M; i++) {
            int A = sc.nextInt();
            int B = sc.nextInt();
            graph[A].add(B);
        }

        // 결과 출력
        List result = bfs(X, K);
        if (result.isEmpty()) {
            System.out.println(-1);
        } else {
            Collections.sort(result);
            for (int city : result) {
                System.out.println(city);
            }
        }

        sc.close();
    }

    private static List bfs(int start, int targetDistance) {
        List reachableCities = new ArrayList<>();
        Queue queue = new LinkedList<>(); // 도시와 현재 거리
        visited = new boolean[graph.length];
        distance = new int[graph.length];

        queue.offer(new int[]{start, 0}); // (도시, 거리)
        visited[start] = true;

        while (!queue.isEmpty()) {
            int[] current = queue.poll();
            int currentCity = current[0];
            int currentDistance = current[1];

            // 목표 거리일 때 도시 추가
            if (currentDistance == targetDistance) {
                reachableCities.add(currentCity);
            }

            // 다음 거리로 이동
            for (int neighbor : graph[currentCity]) {
                if (!visited[neighbor] && currentDistance + 1 <= targetDistance) {
                    visited[neighbor] = true;
                    queue.offer(new int[]{neighbor, currentDistance + 1});
                }
            }
        }

        return reachableCities;
    }
}

코드 설명

위 코드는 크게 세 부분으로 나눌 수 있습니다. 메인 함수에서 그래프를 초기화하고 도로 정보를 입력받은 후, BFS를 통해 도달 가능한 도시를 탐색합니다. BFS 함수는 큐를 이용하여 현재 도시와 거리를 관리하며, 목적지에 도달했을 때 그 도시를 결과 리스트에 추가합니다. 모든 BFS 탐색이 끝난 후에는 도달 가능한 도시를 정렬하여 출력합니다.

직접 해보기

이제 여러분이 직접 코드를 실행해 보세요. 다양한 입력 데이터로 테스트하여 원하는 출력이 나오는지 확인해보세요. 더불어 코드의 각 부분에 대해 주석을 추가하거나, 조건문을 변경해 보면서 코드의 동작을 실험해 보는 것도 좋습니다. 이를 통해 알고리즘에 대한 이해가 더욱 깊어질 것입니다.

마무리

이번 강좌를 통해 특정 거리의 도시를 찾는 문제를 해결하기 위한 기초적인 BFS 알고리즘과 그래프의 구현 방법을 배웠습니다. 취업이 목표인 만큼 이러한 문제들을 많이 풀어보며 실력을 쌓아가시길 바랍니다. 다음 강좌에서는 더 어려운 주제를 다루기로 하겠습니다. 감사합니다!

작성자: 자바 코딩테스트 강좌

연락처: example@example.com