[Java] 9205. 맥주 마시면서 걸어가기

www.acmicpc.net/problem/9205

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

문제

송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. 맥주 한 박스에는 맥주가 20개 들어있다. 목이 마르면 안되기 때문에 50미터에 한 병씩 마시려고 한다.

상근이의 집에서 페스티벌이 열리는 곳은 매우 먼 거리이다. 따라서, 맥주를 더 구매해야 할 수도 있다. 미리 인터넷으로 조사를 해보니 다행히도 맥주를 파는 편의점이 있다. 편의점에 들렸을 때, 빈 병은 버리고 새 맥주 병을 살 수 있다. 하지만, 박스에 들어있는 맥주는 20병을 넘을 수 없다.

편의점, 상근이네 집, 펜타포트 락 페스티벌의 좌표가 주어진다. 상근이와 친구들이 행복하게 페스티벌에 도착할 수 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 t가 주어진다. (t ≤ 50)

각 테스트 케이스의 첫째 줄에는 맥주를 파는 편의점의 개수 n이 주어진다. (0 ≤ n ≤ 100).

다음 n+2개 줄에는 상근이네 집, 편의점, 펜타포트 락 페스티벌 좌표가 주어진다. 각 좌표는 두 정수 x와 y로 이루어져 있다. (두 값 모두 미터, -32768 ≤ x, y ≤ 32767)

송도는 직사각형 모양으로 생긴 도시이다. 두 좌표 사이의 거리는 x 좌표의 차이 + y 좌표의 차이 이다. (맨해튼 거리)

출력

각 테스트 케이스에 대해서 상근이와 친구들이 행복하게 페스티벌에 갈 수 있으면 "happy", 중간에 맥주가 바닥나면 "sad"를 출력한다. 

---

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

public class BOJ_9205 {
	static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;

	static class Point {
		int x, y;

		public Point(int x, int y) {
			this.x = x;
			this.y = y;
		}

		@Override
		public String toString() {
			return "Point [x=" + x + ", y=" + y + "]";
		}

	}

	static ArrayList<Point> list;
	static Point home, festival;
	static int map[][], from[], to[], n;
	static boolean avail[][];
	static final int INF = 9999;

	public static void main(String[] args) throws Exception {
		int T = Integer.parseInt(in.readLine());
		for (int tc = 0; tc < T; tc++) {
			n = Integer.parseInt(in.readLine());
			map = new int[n + 2][n + 2];
			avail = new boolean[n + 2][n + 2];
			list = new ArrayList<>();

			for (int i = 0; i < map.length; i++) {
				st = new StringTokenizer(in.readLine(), " ");
				list.add(new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
			}

			for (int i = 0; i < map.length; i++) {
				for (int j = 0; j < map[i].length; j++) {
					int tmp = getDist(list.get(i), list.get(j));
					map[i][j] = tmp > 1000 ? INF : tmp;

					if (map[i][j] <= 1000) {
						avail[i][j] = true;
					}
				}
			}
			floyd();
			if (avail[0][n + 1]) {
				System.out.println("happy");
			} else {
				System.out.println("sad");
			}

		}
	}
	static void print() {
		System.out.println();
		for (int i = 0; i < avail.length; i++) {
			System.out.println(Arrays.toString(avail[i]));
		}
	}
	private static void floyd() {
		for (int via = 0; via < n+2; via++) {
			for (int from = 0; from < n+2; from++) {
				if (via == from)
					continue;
				for (int to = 0; to < n+2; to++) {
					if (from == to || via == to)
						continue;
					if (avail[from][via] && avail[via][to]) {
						avail[from][to] = true;
					}
				}
			}
		}
	}

	private static int getDist(Point a, Point b) {
		return Math.abs(a.x - b.x) + Math.abs(a.y - b.y);
	}
}

풀이

먼저 좌표를 사용하기 위해 static class를 먼저 선언했다. 그 후 모든 좌표를 ArrayList를 이용하여 입력받았다.

후에 map과 avail이라는 배열을 선언하였는데, 여기서 map은 각 좌표간 거리, avail은 출발지에서 도착지로 갈 수 있는지에 대한 Boolean Type의 배열이다.

 

그리고  50미터당 한 병의 맥주를 소모하기 때문에 맥주 20병으로 갈 수 있는 최대의 거리는 1000m이다. 따라서 애초에  map 배열에 거리를 저장할 때, 1000을 넘게되면 9999를 저장하게 하였다. ( Integer.MAX_VALUE 를 이용하면 Floyd 알고리즘에서 음의 무한대가 나오는 경우가 발생해서 적절한 값으로 조절해줬다.)

 

다음 floyd()를 수행하여 갈 수 있는지 여부를 모두 표시하게 해 주었다. floyd 알고리즘은 모든 노드로의 최단 경로를 구하는 알고리즘이라고 학습했는데, boolean으로 갈 수 있는지 여부를 구하는 알고리즘으로 활용이 가능하다는 것을 알게 되었다.

(처음에는 최단경로로 모든 경로를 구하고, 집에서 가까운 편의점까지 거리, 그리고 편의점에서 페스티벌 장소까지의 거리만을 이용하고자 했는데, 이렇게 되면 굳이 floyd 알고리즘을 사용할 필요가 없었다.)

 

그리고 마지막에 avail[0][n+1] 혹은 avail[n+1][0]의 참거짓을 확인하고 true이면 갈 수 있다는 것이므로 Happy를 아니면 Sad를 출력하면 된다.

 

실버 1이지만 처음 쓰는 알고리즘이라 그런지 생각의 전환이 필요했다