[JAVA] 그래프와 다익스트라

DFS를 쓰면 시간 초과가 나고, BFS를 쓰면 메모리 초과가 나서 문제 분류를 보면 DP거나 다익스트라였던 적이 있는가?

고통받은 김에 정리해봤다.

 

class Graph {
		Deque<Node>[] dqArr; // 연결 노드를 저장할 자료구조
		int nodeCount; // 노드 개수

		public Graph(int nodeCount) { // 그래프 선언
			this.nodeCount = nodeCount;
			dqArr = new Deque[nodeCount + 1];
			for (int i = 0; i < dqArr.length; i++)
				dqArr[i] = new ArrayDeque<>();
		}

		void addEdge(int start, int dest, int cost) { // 그래프에 간선 추가
			dqArr[start].add(new Node(dest, cost));
		}

		public int dijkstra(int start, int dest) { // 다익스트라
			PriorityQueue<Node> pq = new PriorityQueue<Node>();
			boolean visited[] = new boolean[nodeCount + 1];
			int dist[] = new int[nodeCount + 1]; // 거리 저장 배열
			Arrays.fill(dist, Integer.MAX_VALUE); // 모두 최댓값으로 초기화
			dist[start] = 0; // 출발지 거리 = 0
			pq.add(new Node(start, 0));

			while (!pq.isEmpty()) {
				int cur = pq.poll().index;

				if (visited[cur]) // 이미 방문한 노드라면
					continue;
				visited[cur] = true;

				for (Node next : dqArr[cur]) { // 현재 노드와 인접한 노드 리스트
					if (dist[next.index] > dist[cur] + next.cost) { // 현재 next의 가중치가 cur을 경유하는 값보다 크다면
						dist[next.index] = dist[cur] + next.cost;

						pq.add(new Node(next.index, dist[next.index])); // 여기서 next가 다음의 cur이 됨
					}
				}
			}
			return dist[dest];
		}

		class Node implements Comparable<Node> {
			int index, cost;

			public Node(int index, int cost) {
				this.index = index;
				this.cost = cost;
			}

			@Override
			public int compareTo(Graph.Node o) { // PriorityQueue 비교 조건
				return Integer.compare(this.cost, o.cost);
			}
		}
	}