[JAVA] 백준 9205 맥주 마시면서 걸어가기

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

9205번: 맥주 마시면서 걸어가기

 

풀이

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

public class BOJ_9205_맥주마시면서걸어가기 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int t = Integer.parseInt(br.readLine());
		
		while(t-->0) {
			
			//입력
			int n = Integer.parseInt(br.readLine());
			int[][] info = new int[n+2][2];
			
			for(int i=0;i<n+2;i++) {
				String[] temp = br.readLine().split(" ");
				info[i] = new int[] {Integer.parseInt(temp[0]), Integer.parseInt(temp[1])};
			}
			
			//dist 배열 초기화
			int[][] dist = new int[n+2][n+2];
			for(int i=0;i<n+1; i++) {
				for(int j=i+1;j<n+2;j++) {
					dist[i][j] = dist[j][i] = Math.abs(info[i][0] - info[j][0]) + Math.abs(info[i][1] - info[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++) {
						dist[i][j] = Math.min(dist[i][j], dist[i][k]+dist[k][j]);
					}
				}
			}
			
			//이동하기
			String answer = "sad";

			Queue<Integer> q = new LinkedList<>();
			boolean[] visit = new boolean[n+2]; //방문여부
			q.add(0);
			
			while(!q.isEmpty()) {
				int cur = q.poll();
				
				if(cur == n+1) {
					answer = "happy";
					break;
				}
				
				for(int i=0;i<n+2;i++) {
					if(!visit[i] && 50*20>=dist[cur][i]){
						q.add(i);
						visit[i] = true;
					}
				}
			}
				
			System.out.println(answer);
		}

	}

}