백준 1240 노드사이의 거리 Java

백준 1240 노드사이의 거리 Java

728x90

solved.ac = 골드 4

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

1. 접근

가장 기본적인 탐색이 각 노드마다의 거리를 누적하여 x ~ y까지 몇 번 이동해야 하는가? 를 물었다면

이번엔 각 간선마다 비용이 있어 그 비용을 누적하면 되는 문제다!

DFS를 활용하여 각 정점까지의 거리를 누적하는 방법과

다익스트라 알고리즘을 활용하는 두 가지의 방법이 있는데

둘 다 구현해보도록 하자!

그림으로 살펴보자!

2번 정점에서 출발할 때의 예시이다.

그림 속 표를 글로 쓰면

2번 정점에서 1번 정점까지의 비용 = 2

2번 정점에서 4번 정점까지의 비용 = 5 ( 2 -> 1 -> 4)

2번 정점에서 3번 정점까지의 비용 = 7 ( 2 -> 1 -> 4 -> 3)

이런식으로 시작 지점부터 각 정점까지의 이동비용을 누적해주고

목적지 정점에 도착했을 때의 비용을 출력해주면 끝이다!

2. 풀이

변수 세팅

static int N, M; static int[] dist; static ArrayList[] graph; public static void main(String[] args) throws IOException { st = new StringTokenizer(br.readLine()); N = Integer.parseInt(st.nextToken()); M = Integer.parseInt(st.nextToken()); dist = new int[N + 1]; graph = new ArrayList[N + 1]; for (int i = 1; i <= N; i++) graph[i] = new ArrayList<>(); for (int i = 1; i < N; i++) { st = new StringTokenizer(br.readLine()); // x좌표 y좌표 이동비용(cost) int x = Integer.parseInt(st.nextToken()), y = Integer.parseInt(st.nextToken()), c = Integer.parseInt(st.nextToken()); // 무방향 그래프 생성 graph[x].add(new Edge(y, c)); graph[y].add(new Edge(x, c)); } while (M --> 0) { st = new StringTokenizer(br.readLine()); int x = Integer.parseInt(st.nextToken()), y = Integer.parseInt(st.nextToken()); solution(x, y); } }

배열 초기화 및 함수 호출

static void solution(int x, int y) { //DFS(x, -1, y, 0); Arrays.fill(dist, Integer.MAX_VALUE); // 비교를 위해 최대값으로 세팅 dijkstra(x, y); }

DFS 풀이 방법

static void DFS(int x, int prev, int goal, int cost) { if (x == goal) { // 목적지에 도착했다! System.out.println(cost); return; } for (Edge edge : graph[x]) { if (edge.y == prev) continue; // 이전 노드는 방문하지 않는다! DFS(edge.y, x, goal, cost + edge.c); // 이동 비용 누적 } }

다익스트라 풀이 방법

static void dijkstra(int x, int y) { PriorityQueue pq = new PriorityQueue<>(); pq.offer(new Edge(x, 0)); dist[x] = 0; while (!pq.isEmpty()) { Edge tmp = pq.poll(); int now = tmp.y; // 정점번호 int nowCost = tmp.c; // now로 이동시의 비용 if (nowCost > dist[now]) continue; // 이미 계산되어 있는 비용보다 크다면 굳이 볼 필요 없다! for (Edge edge : graph[now]) { if (dist[edge.y] > nowCost + edge.c) { // 이미 계산되어 있는 비용보다 더 적은 비용인가? dist[edge.y] = nowCost + edge.c; // 해당 정점까지의 비용을 기록한다! pq.offer(new Edge(edge.y, nowCost + edge.c)); // 새로 offer 할 때 비용을 누적하자! } } } System.out.println(dist[y]); }

3. 전체 코드

728x90

from http://dhbang.tistory.com/37 by ccl(A) rewrite - 2021-12-20 21:00:37