[백준] 9205번 맥주 마시면서 걸어가기 (java, 플로이드 와샬)

www.acmicpc.net/problem/9205

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

 

걱정했는데 swexpert의 플로이드 와샬보다 알고보니 쉬운 문제였다.

 

거리를 초기화해줄 때 1000(맥주를 마실 수 있는 최대 거리) 보다 크면 -1로 양방향(여기 양방향 처리 안했다 틀렸다)으로 넣어준다.

양방향으로 넣어주는 이유는 시작점과 끝점 둘 중 하나라도 연결이 안되면(중간점과의 간선길이가 1000보다 큰 경우)

시작점 - 중간점 - 끝점 을 연결할 수가 없기 때문이다.

 

만약 시작점과 끝점 둘다 -1이 아니라면 연결할 수가 있다. 이때 -1이 아닌 수로 아무거나 넣어줬다. 

연결이 되었다는 표시만 해주면 된다.

 

 

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

class Edge{
	int y;
	int x;
	public Edge(int y, int x) {
		super();
		this.y = y;
		this.x = x;
	}
	
}

public class B_9205_Main {
	static int t,n;
	static List<Edge> list;
	static int[][] dist;
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		t=sc.nextInt();
		for (int tc = 0; tc < t; tc++) {
			n=sc.nextInt();
			list=new ArrayList<>();
			dist=new int[n+2][n+2];
			for (int i = 0; i < n+2; i++) {
				int y=sc.nextInt();
				int x=sc.nextInt();
				list.add(new Edge(y,x));
			}
			
			for (int i = 0; i < n+2; i++) {
				for (int j = i+1; j < n+2; j++) {
					dist[i][j]=Math.abs(list.get(i).x-list.get(j).x)+Math.abs(list.get(i).y-list.get(j).y);
					if(dist[i][j]>1000) { //1000보다 크면 맥주 보충 불가능 
						dist[i][j]=-1;
						dist[j][i]=-1;
					}
				}
			}
			
			
			floyd();
			
			
			if(dist[0][n+1]==-1) {
				System.out.println("sad");
			}else {
				System.out.println("happy");
			}
		}
		

	}
	private static void floyd() {
		for (int k = 0; k < n+2; k++) {
			for (int i = 0; i <n+2; i++) {
				if(k==i)continue;
				for (int j = 0; j < n+2; j++) {
					if(i==j || j==k)continue;
					if(dist[i][k]==-1 || dist[k][j]==-1)continue;//연결 못하는 곳 이미 길이 1000보다 큰 곳은 걸러짐 
						dist[i][j]=1;// 둘 다 1000이하면 무조건 연결됨 

				}
			}
		}
		
	}
}