[JAVA 알고리즘]BAEKJOON 1240번 노드사이의 거리

생각정리/코딩테스트

[JAVA 알고리즘]BAEKJOON 1240번 노드사이의 거리

생각중임 2023. 12. 21. 00:15

트리를 이용해서 문제를 해결하는 문제

노드사이의 거리

문제 설명

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

제한사항

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

입력

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

출력

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

입출력 예

input	return
4 2 2 1 2 4 3 2 1 4 3 1 2 3 2	2 7

나의 문제풀이

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));
        
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        int N = Integer.parseInt(stringTokenizer.nextToken());
        int M = Integer.parseInt(stringTokenizer.nextToken());
        
        // 노드의 연결에 사용할 리스트 배열
        List<Node>[] nodes = new ArrayList[N + 1];
        for (int i = 0; i <= N; i++) {
            nodes[i] = new ArrayList<>();
        }

		// 노드 쌍을 입력받아 노드별 연결된 노드 및 거리 표시
        for (int i = 0; i < N - 1; i++) {
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            int nodeA = Integer.parseInt(stringTokenizer.nextToken());
            int nodeB = Integer.parseInt(stringTokenizer.nextToken());
            int nodeLength = Integer.parseInt(stringTokenizer.nextToken());
            nodes[nodeA].add(new Node(nodeB, nodeLength));
            nodes[nodeB].add(new Node(nodeA, nodeLength));
        }

		// 연결된 노드를 입력받아 거리 계산
        for (int i = 0; i < M; i++) {
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            int nodeA = Integer.parseInt(stringTokenizer.nextToken());
            int nodeB = Integer.parseInt(stringTokenizer.nextToken());
            // 한번 지난 노드를 확인하기 위한 상태 배열 추가
            boolean[] visited = new boolean[N + 1];
            bufferedWriter.write(nodeLengthFind(nodes, visited, nodeA, nodeB, 0) + "\n");
        }
        bufferedReader.close();

        bufferedWriter.flush();
        bufferedWriter.close();
    }

    public static int nodeLengthFind(List<Node>[] nodes, boolean[] visited, int start, int end, int nodeLength) {
        // 도착 노드에 가지 않으면 거리를 0으로 고정
        int cnt = 0;
        // 도착 노드에 오면 누적 거리 출력
        if (start == end) {
            return nodeLength;
        }

		// 해당 노드 사용 표시
        visited[start] = true;
        for (int i = 0; i < nodes[start].size(); i++) {
        	// 통과한적 없는 노드 거리 산출 반복
            if (!visited[nodes[start].get(i).connectNode]) {
                cnt += nodeLengthFind(nodes, visited, nodes[start].get(i).connectNode, end, nodeLength + nodes[start].get(i).nodeLength);
            }
        }
        return cnt;
    }
}

class Node {
    int connectNode;
    int nodeLength;

    public Node(int connectNode, int nodeLength) {
        this.connectNode = connectNode;
        this.nodeLength = nodeLength;
    }
}

노드의 연결된 노드와 거리를 사용할 클래스를 생성해준다.
노드클래스로 리스트 배열을 주어진 N+1 크기의 배열로 선언해 주고 배열마다 리스트를 초기화해준다.
노드 쌍을 입력받아 노드별 연결된 노드 및 거리를 배열에 노드클래스로 입력한다.
연결된 노드를 입력받아 거리 계산을 반복한다.
- 노드 쌍마다 지난 노드를 확인하기 위해서 반복문 안에서 visited 배열을 초기화해준다.
- 거리 값을 한 번에 추가하기 위해서 재귀함수로 나온 값을 bufferedWriter에 작성해 준다.
- 주어진 시작 노드부터 도착 노드까지 반복을 하며 거리를 계산한다.

이제 무언가 노드로 된 문제들은 대강의 비슷한 형태를 보이는 것을 느낄 수 있었다. 다만 각 방법마다 반복하는 방법들이 다르고 주어지는 조건이 다르기 때문에 비슷한 형태에서 응용을 해야 하고 처음에는 클래스를 만들어서 사용하는데 적응이 안돼있어 리스트 안에 맵을 이용 해서 연결된 노드와 거리를 넣어서 사용을 하려고 했었는데, 정답이 나오 도록 구현이 되지만 효율성에서 큰 문제가 있어서 대안을 찾다 보니 클래스를 만들어서 사용하는 부분이 가장 효율적이고 먼가 자바스러워서 다음부터는 이 부분부터 고려를 해보고 다른 방법을 생각하는 것이 좋아 보였다.
필요함에 따라 클래스와 함수를 만들어서 사용하는 걸 자연스럽게 생각을 하게 되면 실제 코드를 작성할 때도 깔끔하고 좋은 코드를 작성할 수 있을 것 같다.