[BOJ] 9205 맥주 마시면서 걸어가기 (Java)

https://www.acmicpc.net/problem/9205

알고리즘

플로이드 워셜

풀이

집, 편의점, 목적지 좌표를 입력받고, 모든 장소끼리의 거리를 구한다
거리가 50*20 이내인 경우를 제외하고 INF값으로 초기화한다.
플로이드 워셜 알고리즘을 적용해 각 장소끼리의 거리를 최소값으로 업데이트 한다.
만약 집에서 목적지까지의 길이가 0이상 INF값 미만이면 갈 수 있으므로 happy를 출력하고 그렇지 못하면 sad를 출력한다.

코드

import java.awt.Point;
import java.io.*;
import java.util.*;

public class Main {
	
	static int T, N;
	static Point[] points;
	static int[][] distance;
	static final int INF = 987654321;
	
	public static void main(String[] args) throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		T = Integer.parseInt(br.readLine());
		for(int tc=1; tc<=T; tc++) {
			N = Integer.parseInt(br.readLine());
			points = new Point[N+2];
			for(int i=0; i<N+2; i++) {
				st = new StringTokenizer(br.readLine());
				points[i] = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
			}
			
			distance = new int[N+2][N+2];
			for(int i=0; i<N+1; i++) {
				for(int j=i+1; j<N+2; j++) {
					distance[i][j] = distance[j][i] = INF;
					int dis = Math.abs(points[i].y - points[j].y) + Math.abs(points[i].x - points[j].x);
					if(dis <= 50*20) distance[i][j] = distance[j][i] = 1;							// i에서 j까지 안전하게 갈 수 있다면 1로 업데이트 
				}			
			}
			
			for(int k=0; k<N+2; k++) {
				for(int i=0; i<N+2; i++) {
					for(int j=0; j<N+2; j++) {
						distance[i][j] = Math.min(distance[i][j], distance[i][k]+distance[k][j]);	// i->j 까지 직항 경로와 k를 거치는 경유 경로의 길이를 비
					}
				}
			}
			
			if(distance[0][N+1]>0&&distance[0][N+1]<INF) System.out.println("happy");				// 만약 시작 위치에서 끝 지점까지 갈 수 있고, INF안에 갈 수 있다면 happy
			else System.out.println("sad");
		}		
		br.close();
	}

}