코딩 테스트(Coding Test)/백준

[백준] 1240번 : 노드사이의 거리 - 자바(Java)

다문다뭉 2024. 11. 14. 23:37

Problem 🔒

문제

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

 

N개의 노드로 이루어진 트리가 주어지고 M개의 두 노드 쌍을 입력받을 때 두 노드 사이의 거리를 출력하라.

입력

첫째 줄에 노드의 개수 N과 거리를 알고 싶은 노드 쌍의 개수 M이 입력되고 다음 N−1개의 줄에 트리 상에 연결된 두 점과 거리를 입력받는다. 그 다음 줄에는 거리를 알고 싶은 M개의 노드 쌍이 한 줄에 한 쌍씩 입력된다.

출력

M개의 줄에 차례대로 입력받은 두 노드 사이의 거리를 출력한다.

제한

  • 2≤N≤1000
  • 1≤M≤1000
  • 트리 상에 연결된 두 점과 거리는 10000 이하인 자연수이다.
  • 트리 노드의 번호는 1부터 N까지 자연수이며, 두 노드가 같은 번호를 갖는 경우는 없다.
더보기

예제 입력 1

4 2
2 1 2
4 3 2
1 4 3
1 2
3 2

예제 출력 1

2
7

 

Approach ❌

  • 처음 문제를 읽고, 출발 노드에서 도착 노드까지 최소 거리를 구하는 문제인가 싶었다.
  • 하지만, 트리(tree)는 사이클이 없는 무방향 그래프이기 때문에 거리는 단 하나만 존재한다.

Approach ⭕

  1. DFS 풀이
    • 시작 노드에서 끝 노드까지 깊이 우선 탐색을 수행한다.
    • 현재 노드에서 도착 노드까지 도달하면 누적거리를 추가하고 종료한다.
  2. BFS 풀이
    • 시작 노드에서 끝 노드까지 너비 우선 탐색을 수행한다.
    • 큐에 노드와 누적 거리를 넣어 탐색을 진행한다.
    • 현재 노드에서 도착 노드까지 도달하면 해당 거리를 더해 추가하고 종료한다.
  3. 2차원 배열 vs ArrayList<> 차이
    • DFS와 BFS를 2차원 배열로 풀어보고, ArrayList로도 풀어보았다.
    • DFS와 BFS 간에 시간 차이도 존재했지만, ArrayList를 사용하는 것이 배열을 사용하는것보다 훨~씬 빨랐다.
    • 배열을 N이 최대 1000크기라면 1000000까지 탐색 범위가 넓어져 시간이 매우 오래 걸린다.

Solution 💡

DFS 풀이(2차원 배열)

import java.util.Scanner;

public class 노드사이의거리 {
    static int N, M, tree[][], u, v, d, start, end;
    static boolean visit[];
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        tree = new int[N+1][N+1];
        visit = new boolean[N+1];
        for(int i=0; i<N-1; i++){
            u = sc.nextInt();
            v = sc.nextInt();
            d = sc.nextInt();
            tree[u][v] = d;
            tree[v][u] = d;
        }
        for(int i=0; i<M; i++){
            start = sc.nextInt();
            end = sc.nextInt();
            DFS(start, 0);
            visit = new boolean[N+1];
        }
        System.out.println(sb);

    }

    public static void DFS(int start, int d){
        visit[start] = true;
        // 도착 노드와 간선이 있다면
        if(tree[start][end]!=0){
            sb.append(d+tree[start][end]).append("\\n");
            return;
        }
        // 연결된 간선이 없다면
        for(int i=1; i<N+1; i++){
            if(tree[start][i]!=0 && !visit[i]){
                DFS(i, d+tree[start][i]);
            }
        }
    }
}

DFS 풀이(ArrayList)

import java.util.ArrayList;
import java.util.Scanner;

public class 노드사이의거리 {
    static int N, M, u, v, d, start, end;
    static ArrayList<ArrayList<int[]>> list = new ArrayList<>();
    static boolean visit[];
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        for(int i=0; i<N+1; i++){list.add(new ArrayList<>());}
        visit = new boolean[N+1];
        for(int i=0; i<N-1; i++){
            u = sc.nextInt();
            v = sc.nextInt();
            d = sc.nextInt();
            list.get(u).add(new int[]{v, d});
            list.get(v).add(new int[]{u, d});
        }
        for(int i=0; i<M; i++){
            start = sc.nextInt();
            end = sc.nextInt();
            DFS(start, 0);
            visit = new boolean[N+1];
        }
        System.out.println(sb);

    }

    public static void DFS(int start, int d){
        visit[start] = true;
        // 도착 노드와 간선이 있다면
        if(start==end){
            sb.append(d).append("\\n");
            return;
        }
        // 연결된 간선이 없다면
        for(int[] n : list.get(start)){
            if(!visit[n[0]]){
                DFS(n[0], d+n[1]);
            }
        }
    }
}

BFS 풀이(2차원 배열)

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class 노드사이의거리 {
    static int N, M, tree[][], u, v, d, start, end;
    static boolean visit[];
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        tree = new int[N+1][N+1];
        visit = new boolean[N+1];
        for(int i=0; i<N-1; i++){
            u = sc.nextInt();
            v = sc.nextInt();
            d = sc.nextInt();
            tree[u][v] = d;
            tree[v][u] = d;
        }
        for(int i=0; i<M; i++){
            start = sc.nextInt();
            end = sc.nextInt();
            BFS(start);
            visit = new boolean[N+1];
        }
        System.out.println(sb);

    }

    public static void BFS(int start){
        Queue<int[]> q = new LinkedList<>();
        visit[start] = true;
        q.add(new int[]{start, 0});

        while(!q.isEmpty()){
            int[] tmp = q.poll();
            int n = tmp[0]; // 노드 번호
            int d = tmp[1]; // 지금까지 이동한 거리
            // 현재 노드와 도착점이 연결되어 있다면
            if(tree[n][end]!=0){
                sb.append(d+tree[n][end]).append("\\n");
                break;
            }
            // 도착점이랑 연결되어있지 않다면
            for(int i=1; i<N+1; i++){
                if(tree[n][i]!=0 && !visit[i]){
                    visit[i] = true;
                    q.add(new int[]{i, d+tree[n][i]});
                }
            }
        }
    }
}

BFS 풀이(ArrayList)

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class 노드사이의거리 {
    static int N, M, u, v, d, start, end;
    static ArrayList<ArrayList<int[]>> list = new ArrayList<>();
    static boolean visit[];
    static StringBuilder sb = new StringBuilder();
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();
        for(int i=0; i<N+1; i++){list.add(new ArrayList<>());}
        visit = new boolean[N+1];
        for(int i=0; i<N-1; i++){
            u = sc.nextInt();
            v = sc.nextInt();
            d = sc.nextInt();
            list.get(u).add(new int[]{v, d});
            list.get(v).add(new int[]{u, d});
        }
        for(int i=0; i<M; i++){
            start = sc.nextInt();
            end = sc.nextInt();
            BFS(start);
            visit = new boolean[N+1];
        }
        System.out.println(sb);

    }

    public static void BFS(int start){
        Queue<int[]> q = new LinkedList<>();
        visit[start] = true;
        q.add(new int[]{start, 0});

        while(!q.isEmpty()){
            int[] tmp = q.poll();
            int n = tmp[0]; // 노드 번호
            int d = tmp[1]; // 지금까지 이동한 거리
            // 현재 노드와 도착점이 연결되어 있다면
            if(n==end){
                sb.append(d).append("\\n");
                break;
            }
            // 도착점이랑 연결되어있지 않다면
            for(int[] u : list.get(n)){
                if(!visit[u[0]]){
                    visit[u[0]] = true;
                    q.add(new int[]{u[0], u[1]+d});
                }
            }
        }
    }
}