[BOJ 16958] 텔레포트 (Java)

BOJ 16958 텔레포트

문제풀이

완전 간단한 문제가 아닌가 하고 단순하게 문제에서 요구하는대로 두 도시 사이의 이동 시간을 출력했다. 하지만 바로 틀렸는데... 입력과 출력을 대조해서 보니 다른 도시를 거쳐서 가는 것이 더 빠르면 거쳐도 되는 것이였다. 문제에 거쳐서 가도 된다는 언급이 없어서 생각안했건만...

첫 번째 시도는 다익스트라 알고리즘을 사용해봤다. 다익스트라가 하나의 정점에서 다른 모든 정점으로의 최단거리를 구하는 것이니까 각 정점마다 한 번씩 다익스트라를 실행하면 된다고 생각했다. 모든 정점이 연결되어있는 그래프를 생각하고 시도했는데 시간초과가 났다. 우선순위큐를 이용한 다익스트라 알고리즘의 시간복잡도는 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);
	}
}