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

문제링크

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

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

 

 

 

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

public class Main {

	static int map[][];
	static ArrayList<Node> list;
	static final int INF = 99999999;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int T = Integer.parseInt(br.readLine());

		for (int t = 0; t < T; t++) {
			int N = Integer.parseInt(br.readLine()); // 편의점의 개수
			map = new int[N + 2][N + 2];
			list = new ArrayList<>();

			for (int i = 0; i < N + 2; i++) {
				for (int j = 0; j < N + 2; j++)
					map[i][j] = INF;
			}

			for (int i = 0; i < N + 2; i++) {
				st = new StringTokenizer(br.readLine());
				list.add(new Node(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
			}

			for (int i = 0; i < N + 2; i++) {
				for (int j = 0; j < N + 2; j++) {
					if (i == j)
						continue;

					Node current = list.get(i);
					Node next = list.get(j);

					int distance = Math.abs(current.x - next.x) + Math.abs(current.y - next.y);
					if (distance <= 1000)
						map[i][j] = 1;
				}
			} // 두 지점 사이의 거리가 1000보다 작거나 같으면 이동할 수 있는 거리임으로 map 배열 바꿔주기

			for (int k = 0; k < N + 2; k++) {// 경유지
				for (int i = 0; i < N + 2; i++) {// 출발지
					for (int j = 0; j < N + 2; j++) {// 도착지
						if (i == j || k == j)
							continue;
						if (map[i][j] > map[i][k] + map[k][j])
							map[i][j] = map[i][k] + map[k][j];
					}
				}
			}

			if (map[0][N + 1] > 0 && map[0][N + 1] < INF)
				System.out.println("happy");
			else
				System.out.println("sad");

		}
	}

	static class Node {
		int x;
		int y;

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

 

floyd사용해서 해결하였다.

처음에 접근을 어떻게 해야할지 몰라서 애를 먹었다.

50m씩 이동하면서 맥주를 하나씩 빼야하나 생각을 했지만 그렇게 생각하지 말고

두 지점사이의 거리가 1000m이하면 무조건 이동이 가능하다. (50m * 맥주 20병)

따라서 두 지점 사이의 거리가 1000m이하인 곳은 이동가능하다고 표시를 한다.

 

그 후 floyd를 사용해서 경유지->출발지->도착지 순으로 순회하면서 갈 수 있는지 없는지를 check해준다.

출발지 0 에서 도착지 N+2까지의 가는 길이 있으면 happy 아니면 sad로 출력하면 된다.