[JAVA] SWEA 1249 보급로
문제
사실상 백준 4485번 '녹색 옷 입은 애가 젤다지?' 문제와 동일하다.
https://www.acmicpc.net/problem/4485
입력
가장 첫 줄은 전체 테스트케이스의 수이다.
각 테스트 케이스마다 지도의 크기(N x N)가 주어진다. 지도의 크기는 최대 100 x 100이다.
그 다음줄 부터 지도의 크기만큼 2차원 배열 형태의 지도 정보가 주어진다.
출력
각 테스트 케이스의 답을 순서대로 출력하며, 각 케이스마다 줄의 시작에 “#C”를 출력하여야 한다. 이때 C는 케이스의 번호이다.
같은 줄에 빈 칸을 하나 두고, 주어진 입력에서 출발지에서 도착지까지 가는 경로 중에 복구 작업에 드는 시간이 가장 작은 경로의 복구 시간을 출력하시오.
풀이: 다익스트라
- N*N개의 가상의 지점을 가정하고, 각 노드의 소요 시간을 지점 간 이동 거리 간선으로 두는 그래프를 생성한다.
- 그래프에서 다익스트라 알고리즘을 적용한다.
코드
package swea;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
public class p보급로 {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static class Node implements Comparable<Node> {
int end, weight;
public Node(int end, int weight) {
super();
this.end = end;
this.weight = weight;
}
@Override
public int compareTo(Node o) {
// TODO Auto-generated method stub
return weight - o.weight;
}
}
public static void main(String[] args) throws NumberFormatException, IOException {
int testcase = Integer.parseInt(br.readLine());
for (int t = 1; t <= testcase; t++) {
int N = Integer.parseInt(br.readLine());
int[][] thief = new int[N][N];
for (int i = 0; i < N; i++) {
String input = br.readLine();
for (int j = 0; j < N; j++) {
thief[i][j] = input.charAt(j) - 48;
}
}
int node = (int) Math.pow(N, 2) + 1;
boolean[] visited = new boolean[node];
ArrayList<Node>[] adj = new ArrayList[node];
for (int i = 0; i < node; i++) {
adj[i] = new ArrayList<Node>();
}
adj[0].add(new Node(1, thief[0][0]));
for (int i = 1; i < node; i++) {
int posI = (i - 1) / N;
int posJ = (i - 1) % N;
if (posJ < N - 1) {
adj[i].add(new Node(i + 1, thief[posI][posJ + 1]));
}
if (posJ > 0) {
adj[i].add(new Node(i - 1, thief[posI][posJ - 1]));
}
if (posI < N - 1) {
adj[i].add(new Node(i + N, thief[posI + 1][posJ]));
}
if (posI > 0) {
adj[i].add(new Node(i - N, thief[posI - 1][posJ]));
}
}
PriorityQueue<Node> pq = new PriorityQueue<>();
int[] distance = new int[node];
Arrays.fill(distance, Integer.MAX_VALUE);
distance[0] = 0;
pq.offer(new Node(0, 0));
while (!pq.isEmpty()) {
Node cur = pq.poll();
if (visited[cur.end])
continue;
visited[cur.end] = true;
for (Node n : adj[cur.end]) {
if (distance[n.end] > distance[cur.end] + n.weight) {
distance[n.end] = distance[cur.end] + n.weight;
pq.offer(new Node(n.end, distance[n.end]));
}
}
}
System.out.println("#" + t + " "+distance[node-1]);
}
}
}
Author And Source
이 문제에 관하여([JAVA] SWEA 1249 보급로), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@taurus429/JAVA-SWEA-1249-보급로저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)