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

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

문제

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

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

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

풀이

트리 + 완전탐색 문제다.

N이 1000, M이 1000으로,

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

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

거리구하는 소스코드

private int getDis(ArrayList> 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

from http://dlwnsdud205.tistory.com/245 by ccl(A) rewrite - 2021-08-07 15:26:22