[BOJ] - 최단경로 / 1753번 (Java)

[BOJ] - 최단경로 / 1753번 (Java)

[BOJ] - 최단경로 / 1753번 (Java)

1. 문제 접근

시작 정점에서 모든 정점까지의 최단거리를 구하면 되는 문제다.

 

간선의 가중치를 의미하는 w값이 10이하의 "자연수"이므로, 음의 가중치를 갖지 않는다.

 

따라서, 다익스트라(Dijkstra)알고리즘을 사용하여 구현하면 된다.

 

현재 위치한 노드에서 방문할 수 있는 노드를 선별하는 것이 핵심이다.

Node adNode = adList[currNodeNum];
while (adNode != null) {
    // 방문한 노드는 PASS, 도달하는 비용이 업데이트 되지 않으면 PASS
    if (!isVisited[adNode.nodeNum] && currCost + adNode.weight < dist[adNode.nodeNum]) {
        dist[adNode.nodeNum] = currCost + adNode.weight;
        pq.offer(new Node(adNode.nodeNum, dist[adNode.nodeNum]));
    }
    adNode = adNode.next;
}

현재 노드까지의 가중치의 합(`currCost`)과 간선의 가중치를 더했을 때, 기존 경로보다 가중치가 작을 경우 값을 갱신하고, 우선 순위 큐에 넣게 된다.

 

추가적으로 실행 시간을 줄이기 위해 라이브러리를 사용하지 않고, 연결 리스트 형태의 `Node`클래스를 만들어 사용했다.

// 정점 클래스
static class Node implements Comparable<Node> {
    Node next;
    int nodeNum, weight;

    public Node(Node next, int nodeNum, int weight) {
        super();
        this.next = next;
        this.nodeNum = nodeNum;
        this.weight = weight;
    }

    public Node(int nodeNum, int weight) {
        this.nodeNum = nodeNum;
        this.weight = weight;
    }

    @Override
    public int compareTo(Node o) {
        return Integer.compare(this.weight, o.weight);
    }
}

해당 클래스는 2가지로 사용되게 된다.

1. 특정 노드의 인접 리스트에 붙어 가중치의 정보를 함께 저장한다.
2. 다익스트라 알고리즘을 실행시키며, 특정 노드까지의 누적 가중치의 합을 저장한다.

---

2. 코드

package boj;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

/**
 * [BOJ] - 최단경로 / 1753번
 * @author JinHxxxxKim
 * 
 * 다익스트라 알고리즘
 * 
 * 1. dist[] 배열을 INF로 모두 초기화한다.
 * 2. 시작 정점의 dist값을 0으로 갱신하고, 우선순위 큐에 넣는다
 * 3. 우선순위 큐에서 꺼내서 인접 정점까지의 가중치를 확인하고 
 *    현재 자신의 dist값에 더하고 인접 정점의 dist를 갱신하고 우선순위 큐에 넣는다.
 * 4. 인접 정점 확인 시, 이미 방문한 정점은 PASS
 * 5. 모든 정점을 확인하였다면 break
 */
public class Sol_1753 {
	private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	private static StringBuilder sb = new StringBuilder();
	private static StringTokenizer st;

	private static final int INF = Integer.MAX_VALUE;

	static int V, E; // 정점, 간선 수
	static Node[] adList; // 인접 리스트
	static boolean[] isVisited; // 방문 여부 배열
	static int[] dist; // 각 노드까지의 최단 거리
	static int startNode; // 시작 정점

	public static void main(String[] args) throws Exception {
		st = new StringTokenizer(br.readLine().trim());
		V = Integer.parseInt(st.nextToken());
		E = Integer.parseInt(st.nextToken());
		startNode = Integer.parseInt(br.readLine().trim());

		// 정점 번호는 1번부터 시작
		adList = new Node[V + 1];
		isVisited = new boolean[V + 1];
		dist = new int[V + 1];
		Arrays.fill(dist, INF);
		dist[startNode] = 0;

		// 인접 리스트 생성
		for (int edgeCnt = 0; edgeCnt < E; ++edgeCnt) {
			st = new StringTokenizer(br.readLine().trim());
			int srcNode = Integer.parseInt(st.nextToken());
			int destNode = Integer.parseInt(st.nextToken());
			int weight = Integer.parseInt(st.nextToken());

			adList[srcNode] = new Node(adList[srcNode], destNode, weight);
		}

		// 다익스트라 알고리즘 시작
		PriorityQueue<Node> pq = new PriorityQueue<>();
		// 시작정점과, 해당 노드로 도달하는데의 최소비용
		pq.add(new Node(startNode, 0));
		int visitCnt = 0; // 방문 정점개수 카운팅
		while (!pq.isEmpty()) {
			Node currNode = pq.poll();
			int currNodeNum = currNode.nodeNum;
			int currCost = currNode.weight;

			// 방문한 적이 있다면 PASS
			if (isVisited[currNodeNum])
				continue;

			visitCnt++;
			// 방문한 정점의 수가 V개라면 모든 정점을 방문했다 판단
			if (visitCnt == V)
				break;
			isVisited[currNodeNum] = true;

			// 인접 노드 탐색
			Node adNode = adList[currNodeNum];
			while (adNode != null) {
				// 방문한 노드는 PASS, 도달하는 비용이 업데이트 되지 않으면 PASS
				if (!isVisited[adNode.nodeNum] && currCost + adNode.weight < dist[adNode.nodeNum]) {
					dist[adNode.nodeNum] = currCost + adNode.weight;
					pq.offer(new Node(adNode.nodeNum, dist[adNode.nodeNum]));
				}
				adNode = adNode.next;
			}
		}
		// 출력
		for (int idx = 1; idx <= V; ++idx) {
			if (dist[idx] == Integer.MAX_VALUE)
				sb.append("INF").append("\n");
			else
				sb.append(dist[idx]).append("\n");
		}
		System.out.println(sb);
	}

	// 정점 클래스
	static class Node implements Comparable<Node> {
		Node next;
		int nodeNum, weight;

		public Node(Node next, int nodeNum, int weight) {
			super();
			this.next = next;
			this.nodeNum = nodeNum;
			this.weight = weight;
		}

		public Node(int nodeNum, int weight) {
			this.nodeNum = nodeNum;
			this.weight = weight;
		}

		@Override
		public int compareTo(Node o) {
			return Integer.compare(this.weight, o.weight);
		}
	}
}

---

3. 디버깅

처음 코드를 짤 때, 최적화 시키기 위해, 방문한 정점의 개수가 총 정점의 개수와 동일하다면 탐색을 종료하는 방식으로 짰다.

 

문제는 해당 노드의 방문 여부를 확인하지 않고, 우선 순위 큐에서 뽑는 즉시 방문한 정점의 개수를 증가시켰다는 것이다.

visitCnt++;
// 방문한 정점의 수가 V개라면 모든 정점을 방문했다 판단
if (visitCnt == V)
    break;

하지만 위와같이 처리할 경우, 우선순위 큐에서 뽑는 노드가 반드시 방문하지 않은 노드라는 보장이 없으므로 틀린 코드가 되었다.

 

예시 그래프

위와 같은 그래프의 경우, 우선 순위 큐에서 뽑는 순서는 (1), (2), (3), (3), (4) 가 된다.

 

기존에 1번과 3번 사이의 간선에 대한 가중치가 1번과 4번 사이 간선의 가중치보다 작기에 3번을 한번 더 뽑게 되고, 기존 나의 코드에서는 4번을 탐색하지 않고 종료하게 된다.

 

따라서 방문 여부를 확인한 후에 해당 조건을 걸었다.

// 방문한 적이 있다면 PASS
if (isVisited[currNodeNum])
    continue;

visitCnt++;
// 방문한 정점의 수가 V개라면 모든 정점을 방문했다 판단
if (visitCnt == V)
    break;
isVisited[currNodeNum] = true;

 

---

4. 결과