[문제 풀이] 백준 1240번 노드사이의 거리 JAVA

문제

 

  문제접근 방법   

해당 문제는 제목 그대로 노드사이의 거리를 구하는 문제이다. 노드의 개수와 거리를 알고 싶은 노드의 쌍의 수를 입력받은 후

연결된 노드와 노드의 길이, 알고 싶은 노드 쌍을 입력받으면 노드쌍의 거리가 출력되는 것이다. 

위의 설명이 조금 난해할 수도 있다 간단하게 말해서 a-b사이의 거리를 알고 싶은데 a에서 b로 바로 연결되어 있는 것이

아니라 a-c-b라고 한다면 a-c 거리 + c-b거리 = a-b 거리 이런 식으로 노드사이 거리를 구하라는 것이다.

문제에서 제시한 입력대로 그래프를 연결해 그림으로 나타내면 아래와 같다.

 

1~4까지의 노드가 존재하고 각각 2와 1, 1과 4, 3과 4 노드끼리 연결되어 있고 각각의 거리는 간선 위에 작성하였다.

그럼 3과 2 사이의 거리는 3 - 4 -1 - 2 = 2+3+2 = 7이라는 것을 확인할 수 있다. 

이렇게 문제를 분석하고 나서 인접리스트를 통해 노드와 연결 관계를 저장하고 이중 배열을 통해 각각의 길이를 저장해야겠다는 생각이 들어 아래와 같이 코드를 작성하였다. 

 

 

< 초기 코드  >

import java.util.*;

public class Main{
    public static List<ArrayList<Integer>> list=new LinkedList<>();
    public static int len[][];
    public static StringBuilder sb=new StringBuilder();
    public static boolean visited[];
    public static void main(String args[]){
        Scanner s=new Scanner(System.in);
        
        int n=s.nextInt();
        int m=s.nextInt();
        len=new int[n+1][n+1];
        for(int i=0;i<=n;i++){
            list.add(new ArrayList<>());
        }
        for(int i=1;i<n;i++){
            int a=s.nextInt();
            int b=s.nextInt();
            int l=s.nextInt();
            list.get(b).add(a);
            list.get(a).add(b);
            len[a][b]=l;
            len[b][a]=l;
        }
        for(int i=0;i<m;i++){
            int a=s.nextInt();
            int b=s.nextInt();
            visited=new boolean[n+1];
            dfs(a,b,0);
        }
        System.out.println(sb);
        
    }
    public static void dfs(int x,int y,int l){
        if(x==y){
            sb.append(l).append("\n");
            return;
        }
        
        for(int i:list.get(x)){
            if(!visited[i]){
                visited[i]=true;
                dfs(i,y,l+len[i][x]);
                //visited[i]=false;
            }
        }
        
    }
}

문제를 보자마자 dfs를 통해 접근해야겠다는 생각이 들었고 처음에는 백트레킹이 필요하다 판단해 bfs는 적절하지 않다고 생각하였다. 하지만 이는 틀린 판단이었다. 잘 생각해 보면 한번 간 노드에서 다시 돌아갈 필요는 없고 경로가 유일하기 때문에 백트래킹은 필요 없는 것이다. 하지만 본 코드는 방문처리를 밖에 해줘야 하는데 백트래킹만 신경 쓰다가 안에 선언하고 코드를 제출해 틀렸다는 결과를 받았다.

< 최종 코드 >

import java.util.*;

public class Main{
    public static List<ArrayList<Integer>> list=new LinkedList<>();
    public static int len[][];
    public static StringBuilder sb=new StringBuilder();
    public static boolean visited[];
    public static void main(String args[]){
        Scanner s=new Scanner(System.in);
        
        int n=s.nextInt();
        int m=s.nextInt();
        len=new int[n+1][n+1];
        for(int i=0;i<=n;i++){
            list.add(new ArrayList<>());
        }
        for(int i=1;i<n;i++){
            int a=s.nextInt();
            int b=s.nextInt();
            int l=s.nextInt();
            list.get(b).add(a);
            list.get(a).add(b);
            len[a][b]=l;
            len[b][a]=l;
        }
        for(int i=0;i<m;i++){
            int a=s.nextInt();
            int b=s.nextInt();
            visited=new boolean[n+1];
            dfs(a,b,0);
        }
        System.out.println(sb);
        
    }
    public static void dfs(int x,int y,int l){
        if(x==y){
            sb.append(l).append("\n");
            return;
        }
        visited[x]=true;
        for(int i:list.get(x)){
            if(!visited[i]){
                dfs(i,y,l+len[i][x]);
                
            }
        }
        
    }
}

위에서 방문처리 실수한 부분을 수정하여 최종 코드를 완성하였다.

 

  마무리  

문제를 보고 bfs/dfs 모두 가능할 것이라 판단했다가 백트래킹이 필요할 것 같다 생각했지만 본 문제는 모든 경우를 열거 거나 경로를 찾는 것이 아니고 n-1의 쌍만 연결관계가 존재하기 때문에 직선상으로만이 가능해 백트래킹은 필요가 없다.

다음에는 문제를 조금 더 읽고 분석해 둘 다 가능한지 불가능한지에 대한 여부를 확실하게 해야겠다.

 

  추가 코드 분석 및 풀이  

본인은 이차원 배열을 활용해 거리 정보를 저장하였지만 여러 블로그의 글을 읽어본 결과 

클래스를 통해 값을 저장하는 방식도 존재하는 것을 확인하였다. 두 방법 중 편한 방법으로 코드를 구현하면 되겠다.