Baekjoon 16958 텔레포트 JAVA

16958번: 텔레포트

문제

2차원 평면 위에 N개의 도시가 있다. 일부 도시는 특별한 도시이다. (r1, c1)에 있는 도시에서 (r2, c2)에 있는 도시로 가는 이동 시간은 |r1 - r2| + |c1 - c2|와 같다. 만약, 두 도시가 특별한 도시라면, 텔레포트를 이용해서 이동할 수도 있다. 텔레포트에 걸리는 시간은 T이다.

두 도시의 쌍 M개가 주어졌을 때, 최소 이동 시간을 구해보자.

조건

[입력]

첫째 줄에 도시의 수 N, 텔레포트하는 데 걸리는 시간 T가 주어진다.

둘째 줄부터 N개의 줄에 도시의 정보를 의미하는 세 정수 s, x, y가 1번 도시부터 N번 도시까지 순서대로 주어진다. s가 1인 경우에는 특별한 도시라는 의미이고, 0인 경우는 특별한 도시가 아니라는 의미이다. (x, y)는 도시의 좌표이다.

다음 줄에는 M이 주어지고, 다음 M개의 줄에는 두 도시 A와 B가 주어진다. 

 

[출력]

총 M개의 줄에 걸쳐서 A에서 B에 가는 최소 이동 시간을 출력한다.

 

• 2 ≤ N ≤ 1,000
• 1 ≤ T ≤ 2,000
• 1 ≤ M ≤ 1,000
• 0 ≤ x, y ≤ 1,000
• A ≠ B
• 두 도시의 좌표가 같은 경우는 없다.

풀이

해당 문제는 도시별로 최소 이동 시간을 구하는 문제다. 플로이드 와샬 알고리즘을 이용해 해결할 수 있었고, 처음에 도시에 정보를 list로 관리했더니 시간 초과가 발생했고 배열로 관리해서 문제를 해결할 수 있었다.

로직은 아래와 같은 방식으로 구현하였다.

1. 배열에 도시 정보를 저장한다.

2. 저장된 도시 정보를 통해 도시별 이동 거리를 갱신한다

    2-1. 두 도시가 특별한 도시고 이동 거리가 T보다 크면 T로 갱신한다.

3. 플로이드 와샬 적용

4. 출력

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int T = Integer.parseInt(st.nextToken());
		
		int city[][] = new int[N+1][3];
		for (int i = 1; i <=N; i++) { // 배열에 도시 정보를 저장
			st = new StringTokenizer(br.readLine());
			city[i][0] = Integer.parseInt(st.nextToken());
			city[i][1] = Integer.parseInt(st.nextToken());
			city[i][2] = Integer.parseInt(st.nextToken());
		}
		
		int map[][] = new int[N+1][N+1];
		
		for (int i = 0; i < N; i++) { // 플로이드를 돌리기위해 도시별 이동 정보를 갱신
			for (int j = 0; j < N; j++) {
				if(i == j)
					continue;
				// 먼저 두 도시에대해서 거리를 저장함
				map[i+1][j+1] = map[j+1][i+1] = Math.abs(city[i+1][1] - city[j+1][1]) + Math.abs(city[i+1][2] - city[j+1][2]);
				if(city[i+1][0] + city[j+1][0] == 2 && map[i+1][j+1] > T) // 두도시가 특별한 도시고 거리가 T보다 멀면 T로 갱신
					map[i+1][j+1] = map[j+1][i+1] = T;
			}
		}
		
		for (int k = 1; k <=N; k++) { // 플로이드 와샬 적용
			for (int i = 1; i <=N; i++) {
				if(k == i)
					continue;
				for (int j = 1; j <=N; j++) {
					if(k == j || i == j)
						continue;
					map[i][j] = Math.min(map[i][j], map[i][k] + map[k][j]);
				}
			}
		}
		
		int M = Integer.parseInt(br.readLine()); // 출력
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			System.out.println(map[a][b]);
		}
	}
}

 

GitHub - JUNGSOONIL/Algorithm-JAVA: 알고리즘 문제 해결 자바 소스 코드