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

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

1240번: 노드사이의 거리

 

 

트리 구조이므로 사이클 없는 직선 거리 = 노드 사이의 거리 가 된다.

처음에는 플로이드-와샬 알고리즘을 적용하는 방식도 생각했지만, 이 알고리즘의 시간복잡도는 O(N^3)이고, N=1,000이므로 시간 초과가 발생함

 

따라서 각 노드에 대한 연결 리스트를 만들어 준 후, 다음의 bfs를 통하여 노드 사이의 거리를 구함

	private static int bfs(int n, int start, int end) {
		int cost = 0;

		boolean[] isVisited = new boolean[n + 1];
		Queue<int[]> queue = new LinkedList<>();
		isVisited[start] = true;
		queue.add(new int[] {start, 0});	//current vertex,  cost 저장
		while(!queue.isEmpty()){
			int[] currNode = queue.poll();
			int currVertex = currNode[0];
			int currCost = currNode[1];
			if (currVertex == end) {
				cost = currCost;
				break;
			}

			//연결 리스트를 통하여 다음에 방문할 노드를 queue에 삽입
			for (int i = 0; i < linkedlist[currVertex].size(); i++) {
				Edge nextEdge = linkedlist[currVertex].get(i);
				if (!isVisited[nextEdge.dest]) {
					queue.add(new int[] {nextEdge.dest, currCost + nextEdge.cost});
					isVisited[nextEdge.dest] = true;
				}
			}
		}
		return cost;
	}

 

 

 

👇 전체 풀이

https://github.com/kkj0419/code_test/pull/23

[2022.12.08] 1240 노드사이의 거리 by kkj0419 · Pull Request #23 · kkj0419/code_test