[백준BOJ] 9205번 맥주 마시면서 걸어가기.java

 

백준 저지에서 맥주 마시면서 걸어가기를 자바를 통해 풀어 보았다. 

 

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

GitHub - tomy9729/Algorithm: 🐗 내가 직접 작성한 내 코드 🐗

 

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

문제

송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. 맥주 한 박스에는 맥주가 20개 들어있다. 목이 마르면 안되기 때문에 50미터에 한 병씩 마시려고 한다. 즉, 50미터를 가려면 그 직전에 맥주 한 병을 마셔야 한다.
상근이의 집에서 페스티벌이 열리는 곳은 매우 먼 거리이다. 따라서, 맥주를 더 구매해야 할 수도 있다. 미리 인터넷으로 조사를 해보니 다행히도 맥주를 파는 편의점이 있다. 편의점에 들렸을 때, 빈 병은 버리고 새 맥주 병을 살 수 있다. 하지만, 박스에 들어있는 맥주는 20병을 넘을 수 없다. 편의점을 나선 직후에도 50미터를 가기 전에 맥주 한 병을 마셔야 한다.
편의점, 상근이네 집, 펜타포트 락 페스티벌의 좌표가 주어진다. 상근이와 친구들이 행복하게 페스티벌에 도착할 수 있는지 구하는 프로그램을 작성하시오.

설명

이 문제를 풀기 위해서는 플로이드-워셜 알고리즘을 알고 있어야 한다. 플로이드-워셜 알고리즘이란 그래프가 존재할 때 모든 정점에서 다른 정점으로의 최단 거리를 구하는 알고리즘이다. 시간복잡도는 O(n^3)이며 브루트포스보다 훨씬 빠르고, 각 정점에 대해서 다익스트라를 쓰는 것보다 훨씬 간단하기 때문에 자주 사용되는 알고리즘이다.

 

맥주는 최대 20병까지 들고 다닐 수 있고 한 병당 50m를 움직일 수 있으므로 최대 1000m까지 움직일 수 있다. 즉 다음 편의점 또는 페스티벌까지 거리가 1000m 이하여야 이동 가능하다. 집, 편의점, 락페스티벌의 위치를 한 배열에 저장했으며 첫 번째 인덱스에는 집, 마지막 인덱스에는 페스티벌을 저장했다.

 

이 문제를 두 가지 방법으로 풀었다.

하나는 모든 간선을 연결한 후 플로이드-워셜 알고리즘을 통해 각 정점과 정점마다 최단 거리를 구한 후 dfs를 통해 1000m 이하인 경로를 찾아가는 것이다. 다른 하나는 정점과 정점 사이 거리가 1000m 이하인 간선만 연결한 후 플로이드-워셜 알고리즘을 통해 집에서 페스티벌까지 가는 최단 경로가 존재하는지 확인하는 것이다. 신기했던 것은 큰 차이는 안 나지만 플로이드-워셜에 dfs까지 사용한 전자의 속도가 더 빨랐다.

 

아래 코드에서 주석으로 표시한 부분이 플로이드-워셜 + dfs로 푼 방법이다.

 

코드

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

public class 맥주_마시면서_걸어가기_9205 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static StringBuilder sb = new StringBuilder();
	
	static boolean check;
	public static void main(String[] args) throws NumberFormatException, IOException {
		int T = Integer.parseInt(br.readLine());
		for(int t=1;t<=T;t++) {
			//맥주를 파는 편의점의 개수
			int n = Integer.parseInt(br.readLine());
			point[] points = new point[n+3];
			int[][] d = new int[n+3][n+3];
			for(int i=1;i<n+3;i++) {
				st = new StringTokenizer(br.readLine()," ");
				int x = Integer.parseInt(st.nextToken());
				int y = Integer.parseInt(st.nextToken());
				points[i] = new point(x,y);
			}
			for(int i=1;i<n+3;i++) {
				for(int j=1;j<n+3;j++) {
					if(i==j)continue;
					d[i][j] = Math.abs(points[i].x-points[j].x) + Math.abs(points[i].y-points[j].y);
					if(d[i][j]>1000)d[i][j] = 9999999;
				}
			}
			
			for(int k=1;k<n+3;k++) {//경유
				for(int i=1;i<n+3;i++) {//출발
					for(int j=1;j<n+3;j++) {//도착
						d[i][j] = Math.min(d[i][k]+d[k][j], d[i][j]);
					}
				}
			}
						
//			boolean[] visit = new boolean[n+3];
//			visit[1]=true;
//			check = false;
//			dfs(1,d,visit);
//			if(check)sb.append("happy\n");
//			else sb.append("sad\n");
			
			if(d[1][n+2]!=9999999)sb.append("happy\n");
			else sb.append("sad\n");
			
			
		}
		System.out.println(sb.toString());
	}
	public static void dfs(int now, int[][] d, boolean[] visit) {
		if(check)return;
		if(now == d.length-1) {
			check = true;
			return;
		}
		
		for(int i=1;i<d.length;i++) {
			if(!visit[i]) {
				if(d[now][i]<=1000) {
					visit[i]=true;
					dfs(i,d,visit);
				}
			}
		}
	}
	static class point{
		int x;
		int y;
		point(int x, int y){
			this.x=x;
			this.y=y;
		}
	}
}