백준 16118번 JAVA : 달빛 여우
February 07, 2022
문제
백준 문제 링크 : https://www.acmicpc.net/problem/16118
풀이전략
-
다익스트라 알고리즘을 사용한다.
- 여우와 늑대의 한 지점으로부터 다른 모든 지점으로의 거리를 구해야하기 때문
- 거리 즉 가중치가 항상 양의 정수이기 때문에 다익스트라로 해결할 수 있다.
-
늑대는 속도가 빨라지고 느려진다.
- 나누기 2 를 할경우 이때 소수점을 사용해야한다. 하지만 소수점을 사용하면 느려지기 때문에 처음 input받는 것을 *2를 해서 받아와 나누기를 해도 정수선에서 처리가 되도록 해준다.
- 값의 최대는 N-1 _ Value이므로 4000 _ 100000 즉 400,000,000으로 int 타입으로 충분하다.
-
늑대와 여우의 속도가 다르기때문에 각각 다익스트라 알고리즘을 적용해야한다.
- 늑대는 속도가 빨라지고 느려지기 때문에, 늑대의 상태에 따라 거리를 저장해야하므로, 늑대의 거리 배열은 2D배열로 한다.
- 한번에 적용할 수도 있다.
코드
늑대, 여우 각각 Priority Queue를 만드는 방법
import java.io.*;
import java.util.*;
public class Main {
static int N, M;
static ArrayList<Node>[] graph;
static int[] foxDistance;
static int[][] wolfDistance;
static class Node{
public int v, cnt;
public int dis;
public Node(int v, int dis, int cnt){
this.v = v;
this.dis = dis;
this.cnt = cnt;
}
}
public static void wolfDijkstra(){
//compare 이렇게하면 오름차순이 됌
// compare(e1.dis, e2.dis) 하면 내림차순
PriorityQueue<Node> pq = new PriorityQueue<>((e1,e2)-> e1.dis - e2.dis);
wolfDistance[0][1] = 0;
pq.add(new Node(1, 0, 0));
while(!pq.isEmpty()) {
Node now = pq.poll();
int speed = now.cnt % 2;
if(wolfDistance[speed][now.v] < now.dis) continue;
if(speed == 0) {
// 늑대가 2배로 빠르게 갈 수 있을때
// now.cnt 가 0일 떄
for(Node next : graph[now.v]) {
if(wolfDistance[speed+1][next.v] > wolfDistance[speed][now.v] + next.dis/2) {
wolfDistance[speed+1][next.v] = wolfDistance[speed][now.v] + next.dis/2;
pq.add(new Node(next.v, wolfDistance[speed][now.v] + next.dis/2, speed+1));
}
}
} else {
// 늑대가 느리게 가야할 때
// speed 는 1인 상태
for(Node next : graph[now.v]) {
if(wolfDistance[speed-1][next.v] > wolfDistance[speed][now.v] + next.dis*2) {
wolfDistance[speed-1][next.v] = wolfDistance[speed][now.v] + next.dis*2;
pq.add(new Node(next.v, wolfDistance[speed][now.v] + next.dis*2, speed+1));
}
}
}
}
}
public static void dijkstra() {
PriorityQueue<Node> pq = new PriorityQueue<>((e1,e2)-> e1.dis - e2.dis);
foxDistance[1] = 0;
pq.add(new Node(1, 0, 0));
while(!pq.isEmpty()) {
Node now = pq.poll();
if(foxDistance[now.v] < now.dis) continue;
for(Node next : graph[now.v]) {
if(foxDistance[next.v] > foxDistance[now.v] + next.dis) {
foxDistance[next.v] = foxDistance[now.v] + next.dis;
pq.add(new Node(next.v, foxDistance[now.v] + next.dis, 0));
}
}
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
graph = new ArrayList[N+1];
foxDistance = new int[N+1];
wolfDistance = new int[2][N+1];
for(int i=0; i<=N; i++) {
graph[i] = new ArrayList<>();
foxDistance[i] = Integer.MAX_VALUE;
wolfDistance[0][i] = Integer.MAX_VALUE;
wolfDistance[1][i] = Integer.MAX_VALUE;
}
for(int i=0; i<M; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
graph[a].add(new Node(b, c*2, 0));
graph[b].add(new Node(a, c*2, 0));
}
dijkstra();
wolfDijkstra();
int answer = 0;
for(int i=2; i<=N; i++) {
if(foxDistance[i] < Math.min(wolfDistance[0][i], wolfDistance[1][i])) answer++;
}
System.out.println(answer);
}
}늑대, 여우 하나의 Priorirty Queue에서 구하는 방법
import java.io.*;
import java.util.*;
public class Main {
static int N, M;
static ArrayList<Node>[] graph;
static int[][] distance;
static class Node {
public int v, cnt;
public int dis;
public Node(int v, int dis, int cnt){
this.v = v;
this.dis = dis;
this.cnt = cnt;
}
}
public static void dijkstra(){
PriorityQueue<Node> pq = new PriorityQueue<>((e1,e2)-> e1.dis - e2.dis);
distance[0][1] = 0;
distance[2][1] = 0;
// 0은 빠른 늑대
// 1은 느린 늑대
// 2는 여우
pq.add(new Node(1, 0, 0));
pq.add(new Node(1, 0, 2));
while(!pq.isEmpty()) {
Node now = pq.poll();
int speed = now.cnt;
if(distance[speed][now.v] < now.dis) continue;
if(speed == 0) {
// 늑대가 2배로 빠르게 갈 수 있을때
// now.cnt 가 0일 떄
for(Node next : graph[now.v]) {
if(distance[speed+1][next.v] > distance[speed][now.v] + next.dis/2) {
distance[speed+1][next.v] = distance[speed][now.v] + next.dis/2;
pq.add(new Node(next.v, distance[speed][now.v] + next.dis/2, speed+1));
}
}
} else if(speed == 1) {
// 늑대가 느리게 가야할 때
// speed 는 1인 상태
for(Node next : graph[now.v]) {
if(distance[speed-1][next.v] > distance[speed][now.v] + next.dis*2) {
distance[speed-1][next.v] = distance[speed][now.v] + next.dis*2;
pq.add(new Node(next.v, distance[speed][now.v] + next.dis*2, speed-1));
}
}
} else {
// speed 가 2인경우 즉 여우인 상태
for(Node next : graph[now.v]) {
if(distance[speed][next.v] > distance[speed][now.v] + next.dis) {
distance[speed][next.v] = distance[speed][now.v] + next.dis;
pq.add(new Node(next.v, distance[speed][now.v] + next.dis, speed));
}
}
}
}
}
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
graph = new ArrayList[N+1];
distance = new int[3][N+1];
for(int i=0; i<=N; i++) {
graph[i] = new ArrayList<>();
distance[0][i] = Integer.MAX_VALUE;
distance[1][i] = Integer.MAX_VALUE;
distance[2][i] = Integer.MAX_VALUE;
}
for(int i=0; i<M; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
graph[a].add(new Node(b, c*2, 0));
graph[b].add(new Node(a, c*2, 0));
}
dijkstra();
int answer = 0;
for(int i=2; i<=N; i++) {
if(distance[2][i] < Math.min(distance[0][i], distance[1][i])) answer++;
}
System.out.println(answer);
}
}회고
- 문제에서 distance를 2D어레이로 만들어서 저장하는 아이디어가 중요한 아이디어이고 문제풀이는 재미있었다.
- 처음에 Long으로 풀어서 계속 시간초과가 나왔다… 타입을 항상 잘 확인해야한다.
