[알고리즘] 백준 > #9205. 맥주 마시면서 걸어가기

문제링크

백준 #9205. 맥주 마시면서 걸어가기

풀이방법

결국 패스하긴 했지만 그 전에 잘못된 방법을 시도했었다. 그 잘못된 풀이부터 쭉- 남기고자 한다.

일단, 이동할 수 있는 조건은 두 위치 사이의 거리가 1000이하인 경우이다.

첫번째 시도한 방법은 Greedy 스러운 방법이었다. 이동 시 해당 위치에서 가장 가깝고 다녀오지 않은 곳으로 이동하는 방식이다. 계속 위 조건을 만족하는 가장 가깝고 다녀오지 않은 곳으로 이동해 페스티벌 위치에 도달하면 happy, 그렇지 않으면 sad라는 결과를 냈다. 하지만 (0, 0), (2, 1), (500, 500), (1002, 1)과 같은 반례가 존재한다. (2, 1)에서 모든 조건을 만족하는 (500, 500)으로 이동하고 (500, 500)에서 모든 조건을 만족하는 곳을 탐색한다. (1002, 1)까지의 거리가 1000을 초과해 도달하지 못하게 되어 sad 결과를 갖게된다. 이 문제를 해결하기 위해 "가장 가까운 곳을로"라는 조건을 없앴다. n 값의 범위를 보았을 때, 현재 위치에서 갈 수 있는 곳들을 모두 큐에 넣었다. 이렇게 하면 위와 같은 반례또한 해결 가능했다. 이를 구현할 때는 다익스트라 알고리즘을 참고했다(다익스트라 알고리즘은 모두 연결되어 있을 때 최단 거리를 구하는 알고리즘으로, 해당 문제에서는 거리가 1000을 초과하면 연결 될 수 없다는 부분이 달랐다). 모든 지점의 dist 값을 MAX_DIST로 설정하고 0번째 지점부터 시작해 도달가능한 곳들을 큐에 넣고, dist 값을 갱신했다. 이 과정을 마치고 페스티벌 지점의 dist 값이 MAX_DIST라면 sad를, 그렇지 않다면 happy를 결과 값에 넣었다.

코드

import java.util.*;

public class BOJ9205 {

    static final int MAX_DIST = 200000;

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

        int t = sc.nextInt();
        boolean[] results = new boolean[t];

        for (int time = 0; time < t; time++) {
            int n = sc.nextInt();
            Location[] locations = new Location[n + 2];
            for (int i = 0; i < n + 2; i++) {
                int x = sc.nextInt();
                int y = sc.nextInt();
                locations[i] = new Location(x, y);
            }

            int[] dist = new int[n + 2];
            for (int i = 0; i < n + 2; i++) dist[i] = MAX_DIST;
            boolean[] visited = new boolean[n + 2];
            Queue<Integer> q = new LinkedList<>();
            q.offer(0);
            dist[0] = 0;

            while (!q.isEmpty()) {
                int head = q.poll();

                if (!visited[head]) {
                    visited[head] = true;

                    for (int i = 0; i < n + 2; i++) {
                        if (!visited[i] && isReachable(locations[head].x, locations[head].y, locations[i].x, locations[i].y)) {
                            q.offer(i);
                            dist[i] = dist[head] + 1;
                        }
                    }
                }
            }

           results[time] = (dist[n + 1] != MAX_DIST) ? true : false;
        }

        StringBuilder output = new StringBuilder();
        for (int i = 0; i < t; i++) {
            output.append(results[i] ? "happy" : "sad");
            output.append("\n");
        }

        System.out.print(output.toString());
    }

    public static boolean isReachable(int x1, int y1, int x2, int y2) {
        return (Math.abs(x1 - x2) + Math.abs(y1 - y2) <= 1000);
    }
}

class Location {
    public int x;
    public int y;

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