문제풀이
완전 간단한 문제가 아닌가 하고 단순하게 문제에서 요구하는대로 두 도시 사이의 이동 시간을 출력했다. 하지만 바로 틀렸는데... 입력과 출력을 대조해서 보니 다른 도시를 거쳐서 가는 것이 더 빠르면 거쳐도 되는 것이였다. 문제에 거쳐서 가도 된다는 언급이 없어서 생각안했건만...
첫 번째 시도는 다익스트라 알고리즘을 사용해봤다. 다익스트라가 하나의 정점에서 다른 모든 정점으로의 최단거리를 구하는 것이니까 각 정점마다 한 번씩 다익스트라를 실행하면 된다고 생각했다. 모든 정점이 연결되어있는 그래프를 생각하고 시도했는데 시간초과가 났다. 우선순위큐를 이용한 다익스트라 알고리즘의 시간복잡도는 O(ElogV)이니까 m번 수행으로 O(mElogV)다. 최악의 경우 m = 1000, E(간선) = 1000^2, V(정점) = 1000으로 대략 30억 번 수행된다.
두 번째 시도는 플로이드 와샬 알고리즘을 사용했다. 모든 정점에서 모든 정점으로의 최단거리를 구하는 알고리즘으로 다익스트라 알고리즘이 가장 적은 가중치를 선택해 진행한다면 플로이드 와샬은 거쳐가는 정점을 기준으로 진행한다. 플로이드 와샬 알고리즘의 시간복잡도가 O(V^3)이고 이 문제에서 최악의 경우에 V(정점) = 1000 이니까 1000^3으로 10억...? 왜 통과되지..? 엣지케이스가 제대로 안들어있는 것 같다.
세 번째 시도는 시뮬레이션이라고 해야하나? 다른 사람들의 풀이를 살펴보다 보니 위의 방법들 처럼 어렵게 풀 문제가 아니였다. 우선 두 도시가 좌표계 위에 있기 때문에 두 점 사이의 최단거리는 무조건 직선이다. 다만 텔레포트가 있기 때문에 텔레포트를 한 번 이용할 경우에만 더 짧은 거리가 나올 수 있다. 따라서 다음과 같이 경우를 나눌 수 있다.
- 출발점과 도착점이 텔레포트가 가능한 경우
- 출발점과 도착점의 직선 거리 소요 시간과 텔레포트 소요 시간을 비교한다.
- 출발점만 텔레포트 가능 도시일 경우
- 도착점과 가장 가까운 텔레포트 가능 도시를 찾는다. 그러면 텔레포트 시간 + 가장 가까운 도시에서 도착점까지의 직선 거리 소요 시간과 출발점과 도착점의 직선 거리 소요 시간을 비교한다.
- 도착점만 텔레포트 가능 도시일 경우
- 출발점과 가장 가까운 텔레포트 가능 도시를 찾는다. 그러면 텔레포트 시간 + 가장 가까운 도시에서 출발점까지의 직선 거리 소요 시간과 출발점과 도착점의 직선 거리 소요 시간을 비교한다.
- 출발점과 도착점이 둘다 텔레포트가 불가한 경우
- 출발점, 도착점과 가장 가까운 텔레포트 가능 도시를 각각 찾는다. 텔레포트 시간 + 각 지점과 찾은 도시 사이의 직선 거리 소요 시간과 출발점과 도착점의 직선 거리 소요 시간을 비교한다.
총 네가지의 경우를 바탕으로 최단거리를 출력한다.
이런 문제가 나올 경우 처음 접근할 때 제대로 검증하지 않으면 굉장히 오랜시간을 들여서 돌아가게 된다. 마지막 풀이는 사실 굉장히 간단한데 말이다...
구현코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int N, M, T;
static int[][] city;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = stoi(st.nextToken());
T = stoi(st.nextToken());
city = new int[N + 1][3];
for(int i = 1 ; i <= N ; ++i) {
st = new StringTokenizer(br.readLine());
city[i][0] = stoi(st.nextToken());
city[i][1] = stoi(st.nextToken());
city[i][2] = stoi(st.nextToken());
}
M = stoi(br.readLine());
for(int i = 0 ; i < M ; ++i) {
st = new StringTokenizer(br.readLine());
int a = stoi(st.nextToken());
int b = stoi(st.nextToken());
int distance = 0;
if(city[a][0] == 1 && city[b][0] == 1) {
distance = getDistance(a, b);
} else if(city[a][0] == 1) {
int bToTelpo = getNearestTelpo(b);
distance = Math.min(bToTelpo + T, getDistance(a, b));
} else if(city[b][0] == 1) {
int aToTelpo = getNearestTelpo(a);
distance = Math.min(aToTelpo + T, getDistance(a, b));
} else {
int bToTelpo = getNearestTelpo(b);
int aToTelpo = getNearestTelpo(a);
distance = Math.min(bToTelpo + aToTelpo + T, getDistance(a, b));
}
System.out.println(distance);
}
}
private static int getNearestTelpo(int point) {
int min = Integer.MAX_VALUE;
for(int i = 1 ; i <= N ; ++i) {
if(city[i][0] == 0) continue;
int dist = getDistance(point, i);
min = min > dist ? dist : min;
}
return min;
}
private static int getDistance(int a, int b) {
int dist = Math.abs(city[a][1] - city[b][1]) + Math.abs(city[a][2] - city[b][2]);
if(city[a][0] == 1 && city[b][0] == 1) dist = dist > T ? T : dist;
return dist;
}
private static int stoi(String s) {
return Integer.parseInt(s);
}
}
// 플로이드 와샬 알고리즘을 이용한 풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int N, M, T;
static int[][] city;
static int[][] distance;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = stoi(st.nextToken());
T = stoi(st.nextToken());
city = new int[N + 1][3];
distance = new int[N + 1][N + 1];
for(int i = 1 ; i <= N ; ++i) {
st = new StringTokenizer(br.readLine());
city[i][0] = stoi(st.nextToken());
city[i][1] = stoi(st.nextToken());
city[i][2] = stoi(st.nextToken());
}
for(int i = 1 ; i <= N ; ++i) {
for(int j = 1 ; j <= N ; ++j) {
if(i == j) continue;
int dist = getDistance(i, j);
if(city[i][0] == 1 && city[j][0] == 1) {
dist = dist > T ? T : dist;
}
distance[i][j] = dist;
distance[j][i] = dist;
}
}
for(int mid = 1 ; mid <= N ; ++mid) {
for(int from = 1 ; from <= N ; ++from) {
for(int to = 1 ; to <= N ; ++to) {
if(from == to) continue;
if(distance[from][to] > distance[from][mid] + distance[mid][to]) {
distance[from][to] = distance[from][mid] + distance[mid][to];
}
}
}
}
M = stoi(br.readLine());
for(int i = 0 ; i < M ; ++i) {
st = new StringTokenizer(br.readLine());
int from = stoi(st.nextToken());
int to = stoi(st.nextToken());
System.out.println(distance[from][to]);
}
}
private static int getDistance(int a, int b) {
return Math.abs(city[a][1] - city[b][1]) + Math.abs(city[a][2] - city[b][2]);
}
private static int stoi(String s) {
return Integer.parseInt(s);
}
}
그냥 개발자