백준 9205번 맥주 마시면서 걸어가기 :: 마이구미

이번 글은 백준 알고리즘 문제 9205번 "맥주 마시면서 걸어가기" 를 다뤄본다.

문제 풀이는 플로이드 와샬 알고리즘으로 해결했다.

플로이드 와샬 알고리즘은 다음 링크를 참고하면 되겠다. (플로이드 와샬 알고리즘)

* BFS를 통한 방법은 14431번 소수마을 풀이 참고

Github 알고리즘 문제 - https://github.com/hotehrud/acmicpc

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

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

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

이 문제의 입력 부분은 유독 길게 설명되어 있는 모습을 볼 수 있다.

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

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

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

단순히 2차원 배열을 통해 문제를 접근하려고 했다면, 이미 메모리 초과를 경험할 것이다.

이 부분에서 살짝 멘붕이 올 수 있다.

일단 가장 기본적인 것은 "우리는 락 페스티벌에 가는 모든 경로 중 단 하나라도 맥주가 안 떨어지면 "happy"를 출력하면 된다."

이러한 성질로 인해 DFS보다 BFS가 생각난다면, 좋은 생각이다.

BFS 풀이 방식은 비슷한 문제인 14431번 "소수마을" 문제 풀이를 보자.

하지만 이번 글은 플로이드 와샬을 통해 풀이하겠다.

정점의 기준을 어떻게 정하는 지가 중요하다.

상근이네 집, 편의점, 펜타포트 락 페스티벌을 정점으로 둔다.

이 말은 정점 0은 상근이네 집, 1~n은 페스티벌, n+1은 락으로 두는 것이다.

그리고 플로이드 와샬 알고리즘을 그대로 구현하면 된다.

각 정점에 대한 비용을 가지는 배열을 만드는 것이 첫번째이다.

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        if (i == j) {
            continue;
        }
        Point v = pos.get(i);
        Point next = pos.get(j);

        int distance = Math.abs(v.x - next.x) + Math.abs(v.y - next.y);

        if (distance <= 1000) {
            d[i][j] = 1;
        }
    }
}

문제에서 명시된 맨해튼 거리를 통해 50m에 한 병이기 때문에 20병이 떨어질 거리는 1000m가 된다.

두 정점간의 거리가 1000m가 안되면 연결되어 있다고 표시한다.

그리고 완성된 비용 배열을 통해 플로이드 와샬 알고리즘을 돌린다.

그렇다면, 0 정점에서 n + 1 정점까지 연결 여부를 확인하면 된다.

private void solve() {
    int t = sc.nextInt();
 
    while (t-- > 0) {
        int n = sc.nextInt() + 2;
        int max = 102;
        int[][] d = new int[max][max];
        ArrayList<Point> pos = new ArrayList<>();
 
        for (int i = 0; i < n; i++) {
            pos.add(new Point(sc.nextInt(), sc.nextInt()));
        }
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i != j)
                    d[i][j] = max;
            }
        }
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) {
                    continue;
                }
                Point v = pos.get(i);
                Point next = pos.get(j);
 
                int distance = Math.abs(v.x - next.x) + Math.abs(v.y - next.y);
 
                if (distance <= 1000) {
                    d[i][j] = 1;
                }
            }
        }
 
        floyd(d, n);
 
        n -= 2;
        if (0 < d[0][n + 1] && d[0][n + 1] < max) {
            System.out.println("happy");
        } else {
            System.out.println("sad");
        }
    }
}
 
public static void floyd(int[][] d, int n) {
    for (int k = 0; k < n; ++k) {
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (d[i][j] > d[i][k] + d[k][j]) {
                    d[i][j] = d[i][k] + d[k][j];
                }
            }
        }
    }
}
 
public static class Point {
    int x;
    int y;
 
    Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}