[BOJ][JAVA] 1753번: 최단경로

 

 

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

1753번: 최단경로

 

 

---

오답노트(푸는 동안 사고과정 및 개선점)

다익스트라로 풀면 된다.

 

내가 그래프를 익히는 데 시간이 좀 걸리는 편이라 한줄 한줄 분해해서 작성하겠다.

static class Node {
		int end, w;

		Node(int end, int w) {
			this.end = end;
			this.w = w;
	}
}

다익스트라는 시작정점에서 목표정점까지의 최단 거리다. 각 정점별 Node를 갖는 리스트를 만들 것이기 때문에, 출발 지점은 필요없다. end까지 가는 간선의 가중치가 w다.

static int v, e;
static List<Node>[] list;
static int[] dist;
static PriorityQueue<Node> pq;

정점 정보를 받을(start로 사용할) v - e(end로 사용할)가 있고, Node를 원소로하는 list를 만든다.

각 출발지점 에서 현재 노드까지의 최단 거리를 기록할 dist, 최단거리를 갖는 정점을 쉽게 제어하기 위한 우선순위 큐를 선언해준다.

int INF = 100000000;
list = new ArrayList[v + 1];
dist = new int[v + 1];

Arrays.fill(dist, INF);
for (int i = 1; i <= v; i++) {
	list[i] = new ArrayList<>(); // 각 노드(정점)에 연결된 리스트 생성
}

pq = new PriorityQueue<Node>((o1, o2) -> {
	return o1.w - o2.w;
});

초기화 작업이다. INF는 다익스트라 이론에서 볼수있는 무한대 값을 넣는다고 생각하면 된다. 갈 수 없는 길을 표시하기 위한 초기화 작업이다. 정점 번호를 그대로 index로 쓰기 위해서 v+1로 사이즈를 잡아준다. 참고로 list의 원소 각각은 Node를 원소로 하는 list가 된다. 인접리스트 개념과 동일하다.

각 리스트의 원소에도 ArrayList를 초기화 해줘야 사용이 가능하다. 이걸 하지않으면 null로 남아있다.

// 간선 개수
for (int i = 0; i < e; i++) {
	st = new StringTokenizer(br.readLine(), " ");
	int from = Integer.parseInt(st.nextToken());
	int to = Integer.parseInt(st.nextToken());
	int w = Integer.parseInt(st.nextToken());
	// from에서 to로 가는 weight 가중치
	list[from].add(new Node(to, w));
}

 시작 정점의 리스트에 인접한 노드를 가중치와 함께 담는다. 이게 제일 중요하다. 

이제 다익스트라 구현 코드를 보겠다. 

private static void dijkstra(int start) {
		boolean[] check = new boolean[v + 1]; // 확정된 노드를 표시함
		pq.add(new Node(start, 0));
		dist[start] = 0;

		while (!pq.isEmpty()) {
			Node curNode = pq.poll();
			int cur = curNode.end;

			if (check[cur] == true)
				continue;
			check[cur] = true;

			for (Node node : list[cur]) {
				if (dist[node.end] > dist[cur] + node.w) {
					dist[node.end] = dist[cur] + node.w;
					pq.add(new Node(node.end, dist[node.end]));
				}
			}
		}
	}

 

check 배열도 dist와 동일한 크기로 만들어주고, 시작 정점을 pq에 넣으면서 시작한다. 

시작 정점에서 시작정점으로 가는 가중치는 0이다. 반드시 모든 정점이 경유지라는 생각을 해야 이해가 빨라진다.

다익스트라에 가중치를 없애면 일반 BFS가 된다. 그래서 구조 자체는 비슷하다. 

 

현재 노드에서 도착할 정점을 end로 갖고온다. 만약 방문한 정점이라면 loop를 continue하고 다음 노드를 뽑는다.

방문지않았으면 방문 표시를 하고, 도착할 정점과 인접한 정점들을 다 돌면서, 현재 정점을 경유해서 간 거리(가중치)가 더 가깝다면 갱신해주고 pq에 현재 도착한 정점과 인접한 정점, 그리고 거기까지의 거리를 넣어준다.

---

정답코드

import java.io.*;
import java.util.*;

public class Main {
	static class Node {
		int end, w;

		Node(int end, int w) {
			this.end = end;
			this.w = w;
		}
	}

	static int v, e;
	static List<Node>[] list;
	static int[] dist;
	static PriorityQueue<Node> pq;

	public static void main(String[] args) throws Exception {
		// System.setIn(new FileInputStream("res/boj.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		v = Integer.parseInt(st.nextToken());
		e = Integer.parseInt(st.nextToken());
		int s = Integer.parseInt(br.readLine());
		int INF = 100000000;
		list = new ArrayList[v + 1];
		dist = new int[v + 1];

		Arrays.fill(dist, INF);
		for (int i = 1; i <= v; i++) {
			list[i] = new ArrayList<>(); // 각 노드(정점)에 연결된 리스트 생성
		}

		pq = new PriorityQueue<Node>((o1, o2) -> {
			return o1.w - o2.w;
		});

		// 간선 개수
		for (int i = 0; i < e; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			// from에서 to로 가는 weight 가중치
			list[from].add(new Node(to, w));
		}
		dijkstra(s);
		StringBuilder sb = new StringBuilder();
		for(int i = 1; i <= v; i++){
            if(dist[i] == INF) sb.append("INF\n");
            else sb.append(dist[i]).append("\n");
        }
		System.out.println(sb);
		
	}


	private static void dijkstra(int start) {
		boolean[] check = new boolean[v + 1]; // 확정된 노드를 표시함
		pq.add(new Node(start, 0));
		dist[start] = 0;

		while (!pq.isEmpty()) {
			Node curNode = pq.poll();
			int cur = curNode.end;

			if (check[cur] == true)
				continue;
			check[cur] = true;

			for (Node node : list[cur]) {
				if (dist[node.end] > dist[cur] + node.w) {
					dist[node.end] = dist[cur] + node.w;
					pq.add(new Node(node.end, dist[node.end]));
				}
			}
		}
	}
}

 

 

 

도움이 됐다면 댓글이나 공감 버튼 한 번씩 누르고 가주세요! 로그인 안해도 됩니다 ^_^