[Java] 너비 우선 탐색 BFS| 백준 1240 노드사이의 거리

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

 

 

이 문제는 트리에서 두 노드 간의 거리를 구하는 문제로, BFS(너비 우선 탐색)를 활용하여 해결할 수 있었다. 

 

접근 방식

• 인접 리스트를 사용하여 트리를 표현
• 양방향 간선으로 처리 (트리는 양쪽으로 이동 가능)
• Edge 클래스를 정의하여 목적지 노드와 가중치 정보를 함께 저장

static class Edge {
    int to;
    int weight;

    public Edge(int to, int weight) {
        this.to = to;
        this.weight = weight;
    }
}

 

BFS를 이용한 거리 계산

 

• 시작 노드부터 BFS를 수행하여 각 노드까지의 거리를 계산
• distance 배열을 사용하여 각 노드까지의 누적 거리를 저장 
• 방문하지 않은 노드는 -1로 표시 => 별도 visited 배열을 만들지 않아 메모리 절약

static private int getDistance(int start, int end) {
    int[] distance = new int[N];
    Arrays.fill(distance, -1);
    distance[start] = 0;

    Queue<Integer> queue = new LinkedList<>();
    queue.offer(start);

    while (!queue.isEmpty()) {
        int currentNode = queue.poll();

        if (currentNode == end) {
            return distance[currentNode];
        }

        for (Edge e : graph[currentNode]) {
            if (distance[e.to] == -1) {
                distance[e.to] = distance[currentNode] + e.weight;
                queue.offer(e.to);
            }
        }
    }

    return distance[end];
}

 

 

main 코드

static int N, M;
static ArrayList<Edge>[] graph;

public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());

    N = Integer.parseInt(st.nextToken());
    M = Integer.parseInt(st.nextToken());


    graph = new ArrayList[N];
    for (int i = 0; i < graph.length; i++) {
        graph[i] = new ArrayList<>();
    }

    for (int i = 0; i < N - 1; i++) {
        st = new StringTokenizer(br.readLine());
        int v1 = Integer.parseInt(st.nextToken()) - 1;
        int v2 = Integer.parseInt(st.nextToken()) - 1;
        int weight = Integer.parseInt(st.nextToken());

        graph[v1].add(new Edge(v2, weight));
        graph[v2].add(new Edge(v1, weight));
    }

    StringBuilder sb = new StringBuilder();
    for (int i = 0; i < M; i++) {
        st = new StringTokenizer(br.readLine());
        int v1 = Integer.parseInt(st.nextToken()) - 1;
        int v2 = Integer.parseInt(st.nextToken()) - 1;
        sb.append(getDistance(v1, v2)).append("\n");
    }

    System.out.print(sb);
}

 

시간 복잡도

각 노드를 방문하는데 O(N)의 시간 복잡도가 걸리고 각 간선을 방문하는데 O(E)의 시간 복잡도가 걸린다.

이 문제에서는 E = N-1 이므로 O(N + E) = O(N + (N-1)) = O(N)로 시간 복잡도는 O(N)이 된다.

전체 시간 복잡도는 M번의 거리구하는 요청이 있으므로 O(M * (N+E))=O(M * N) 이다.

 

이 문제를 통해 BFS의 활용과 그래프 자료구조에 다시 복습해볼 수 있었고, 다만 쿼리 수가 더 많은 경우에는 더 빠른 알고리즘이 필요할 것 같아 다른 사람들의 코드를 확인해보니 LCA 알고리즘을 적용하여 풀이하였다. 이를 추후 학습하고 정리해보아야겠다.