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

🔗 문제 링크

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

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

 

📝 풀이 과정

집에서 페스티벌까지 가는데 바로 페스티벌까지 갈 수도 있고, 1군데의 편의점을 들릴 수도 있지만 100군데의 편의점 모두를 들릴 수도 있기 때문에 모두 탐색을 해야한다고 생각했다.

 

n이 100이하이고, $n^3$을 해도 100만이기 때문에 플로이드 와샬 알고리즘을 통해 문제를 해결해보기로 했다.

 

for (int i = 0; i <= n + 1; i++){
  for (int j = 0; j <= n + 1; j++) {
    int[] p1 = point.get(i), p2 = point.get(j);
    dist[i][j] = Math.abs(p1[0] - p2[0]) + Math.abs(p1[1] - p2[1]);

    if (dist[i][j] <= 50 * 20)
    	d[i][j] = true;
    }
  }

먼저, List를 통해 각 정점의 좌표 값을 입력 받았다. 집의 위치를 0, 페스트벌의 위치를 n + 1로 두었고, 각 정점에서 다른 정점까지의 위치를 Math.abs()를 통해 계산하였다.

 

맥주를 한 번에 가질수 있는 최대 개수가 20개이고, 50m마다 1병의 맥주를 마시기 때문에, 거리가 50 * 20 이하라면 d[i][j] (i에서 j를 갈 수 있는지에 대한 여부)를 true로 설정하였다.

 

 

for (int k = 0; k <= n + 1; k++)
  for (int i = 0; i <= n + 1; i++)
    for (int j = 0; j <= n + 1; j++)
      if (d[i][k] & d[k][j])
      	d[i][j] = true;

다음으로 플로이드 와샬을 통해 만약 i -> k로 가는 것이 가능하고, k -> j로 가는 것이 가능하다면 i -> j로 가는것이 가능하기 때문에 d[i][j]를 true로 설정하였다.

 

따라서, d[0][n + 1]이 true라면 집에서 페스티발까지 맥주가 떨어지지 않고 도달할 수 있기 때문에 "happy"를 출력한다!

 

💻 코드

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

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();

        for (int tc = 1; tc <= T; tc++) {
            int n = sc.nextInt();
            int[][] dist = new int[n + 2][n + 2];
            boolean[][] d = new boolean[n + 2][n + 2];
            List<int[]> point = new ArrayList<>();
            for (int i = 0; i <= n + 1; i++)
                point.add(new int[]{sc.nextInt(), sc.nextInt()});

            for (int i = 0; i <= n + 1; i++)
                for (int j = 0; j <= n + 1; j++) {
                    int[] p1 = point.get(i), p2 = point.get(j);
                    dist[i][j] = Math.abs(p1[0] - p2[0]) + Math.abs(p1[1] - p2[1]);

                    if (dist[i][j] <= 50 * 20)
                        d[i][j] = true;
                }


            for (int k = 0; k <= n + 1; k++)
                for (int i = 0; i <= n + 1; i++)
                    for (int j = 0; j <= n + 1; j++)
                        if (d[i][k] & d[k][j])
                            d[i][j] = true;

            System.out.println(d[0][n + 1] ? "happy" : "sad");

        }
    }

}

 

 

📊 제출 결과