[백준 / BOJ] 1240 노드사이의 거리

문제

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

1240번: 노드사이의 거리

N개의 노드로 이루어진 트리가 주어지고, M개의 쿼리가 주어질때,

노드 사이의 거리를 구하는 프로그램을 만드는 문제다.

 

---

풀이

트리 + 완전탐색 문제다.

N이 1000, M이 1000으로,

한번탐색할때마다 최대 1000번 반복한다고 가정했을때, 최악의경우, 1000*1000번 반복하므로 시간복잡도는 O(NM)이 된다.

 

트리구조를 만든다음에 A위치에서 시작했을때, B위치에 도달했을때의 거리를 구하면된다.

 

거리구하는 소스코드

    private int getDis(ArrayList<ArrayList<Node>> tree, int nowIdx, int to, int nowDis, int checkCnt){
        int ret = 0;
        if(nowIdx == to) return nowDis;
        check[nowIdx] = checkCnt;
        for(int i = 0; i < tree.get(nowIdx).size(); i++){
            int nextIdx = tree.get(nowIdx).get(i).idx;
            int nextDis = nowDis + tree.get(nowIdx).get(i).dis;
            if(check[nextIdx] == checkCnt) continue;
            ret = Math.max(ret, getDis(tree, nextIdx, to, nextDis, checkCnt));
        }
        return ret;
    }

이때, 트리 구조를 양방향으로 만든후에, check배열을 따로 만들어서, 중복방문을 없애줘야한다.

 

M개의 쿼리가 다음과 같은과 같은 형태로 주어질수있기때문에,

 

root(1) -> A(2) ->B(3)

 

트리 구조를 양방향으로 만든후에, check배열을 따로 만들어서, 중복방문을 없애줘야한다.

 

---

전체 소스코드

https://github.com/devxb/JJUNalgo/blob/master/BOJ%20source%20code/1240%20%EB%85%B8%EB%93%9C%EC%82%AC%EC%9D%B4%EC%9D%98%20%EA%B1%B0%EB%A6%AC/Main.java

GitHub - devxb/JJUNalgo: 백준 알고리즘 소스코드🙃