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

📌 Problem

송도는 x와 y 좌표로 이루어진 곳이다. 한 지점에서 이동할 수 있는 다른 지점의 최대 거리는 1000이다. 그 이상의 거리에 있는 지점은 한 번에 갈 수 없다. 각 지점에 도착할 때마다 이동할 수 있는 거리는 초기화되어 다시 1000을 이동할 수 있다. 시작 지점, 도착 지점, 중간 지점들이 주어 졌을 때 시작 지점에서 도착 지점으로 갈 수 있는지를 판단하면 된다. 참고로 지점 사이의 거리는 x 좌표의 차이 + y 좌표의 차이이다.

📌 Solution

BFS으로 해결할 수 있다. 시작 지점에서 1000 이하에 있는 지점들이 다음으로 이동할 수 있는 지점들이다. 또한 한 번 방문한 지점은 이후에 다시 방문할 필요가 없다. 만약 다음으로 이동할 수 있는 지점이 도착 지점이라면 시작 지점에서 도착 지점으로 이동할 수 있는 것이다.

📌 Code

public void solve() throws IOException {
    StringTokenizer tokenizer;
    int T = Integer.parseInt(reader.readLine());
    while (T-- > 0) {
        Queue<Point> pointsArrived = new LinkedList<>();
        List<Point> pointsNotArrived = new LinkedList<>();

        int marketNum = Integer.parseInt(reader.readLine());
        tokenizer = new StringTokenizer(reader.readLine());
        Point start = new Point(Integer.parseInt(tokenizer.nextToken()), Integer.parseInt(tokenizer.nextToken()));
        pointsArrived.offer(start);

        while (marketNum-- > 0) {
            tokenizer = new StringTokenizer(reader.readLine());
            Point market = new Point(Integer.parseInt(tokenizer.nextToken()), Integer.parseInt(tokenizer.nextToken()));
            pointsNotArrived.add(market);
        }

        tokenizer = new StringTokenizer(reader.readLine());
        Point end = new Point(Integer.parseInt(tokenizer.nextToken()), Integer.parseInt(tokenizer.nextToken()), true);
        pointsNotArrived.add(end);

        result.append(canArriveFestival(pointsArrived, pointsNotArrived) ? "happy" : "sad").append('\n');
    }
}

private boolean canArriveFestival(Queue<Point> pointsArrived, List<Point> pointsNotArrived) {
    while (!pointsArrived.isEmpty()) {
        Point point = pointsArrived.poll();
        for (int p = 0; p < pointsNotArrived.size(); p++) {
            Point nextPoint = pointsNotArrived.get(p);
            if (point.distance(nextPoint) <= 1000)
                if (nextPoint.isFestival()) return true;
                else pointsArrived.add(pointsNotArrived.remove(p--));
        }
    }
    return false;
}

class Point {

    private final int x, y;
    private boolean festival;

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

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

    public int distance(Point point) {
        return Math.abs(x - point.x) + Math.abs(y - point.y);
    }

    public boolean isFestival() {
        return festival;
    }
}