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

문제

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

리뷰

문제 조건만 잘 이해하면 전형적으로 BFS를 통해 풀이할 수 있는 문제였다.

이동할 수 있는 위치 각각을 정점으로 보면, 박스에 한 번에 담을 수 있는
맥주 20병*50 미터=1000미터가 한 번에 이동할 수 있는 위치이다.

이를 바탕으로 Location 이라는 x,y 좌표를 필드로 가지는 클래스를
통해 출발 정점, 편의점 정점, 도착 정점 정보를 저장하고 bfs를 통해
이동 가능한(현재 탐색 중인 정점에서 1000미터 이내의 정점) 정점으로의
탐색을 통하여 도착 정점에 도달할 수 있는 경우 happy 를 불가능할 경우
sad 를 출력하도록 로직을 구성하였다.

BFS의 시간복잡도를 $O(N^2)$으로 가정하였을때 전체 로직의 시간복잡도는
$O(TN^2)$으로 수렴하고, 이는 최악의 경우 $50 \times 102^2$ 번의 연산을
수행한다. 따라서 주어진 시간 제한 조건인 1초를 무난히 통과한다.

코드

import org.w3c.dom.Node;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

import static java.lang.Integer.parseInt;


public class Main {
    static List<Location> locations = new ArrayList<>();
    static boolean[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = parseInt(br.readLine());
        StringTokenizer st;
        Location start, end;
        int x, y;
        StringBuilder sb = new StringBuilder();

        while (T-- > 0) {
            int n = parseInt(br.readLine());
            visited = new boolean[n + 2];

            st = new StringTokenizer(br.readLine());
            x = parseInt(st.nextToken());
            y = parseInt(st.nextToken());
            start = new Location(x, y);
            locations.add(start);

            for (int i = 0; i < n; i++) {
                st = new StringTokenizer(br.readLine());
                x = parseInt(st.nextToken());
                y = parseInt(st.nextToken());

                locations.add(new Location(x, y));
            }

            st = new StringTokenizer(br.readLine());
            x = parseInt(st.nextToken());
            y = parseInt(st.nextToken());
            end = new Location(x, y);
            locations.add(end);

            sb.append(bfs(start, end) ? "happy\n" : "sad\n");

            locations.clear();
        }

        System.out.print(sb);
        br.close();
    }

    static boolean bfs(Location start, Location end) {
        visited[0] = true;
        Queue<Location> queue = new ArrayDeque<>();
        queue.offer(start);

        while (!queue.isEmpty()) {
            Location current = queue.poll();
            if (current.x == end.x && current.y == end.y)
                return true;

            for (int i = 0; i < locations.size(); i++) {
                Location next = locations.get(i);

                if (!visited[i] && getDistance(current.x, current.y, next.x, next.y) <= 1000) {
                    visited[i] = true;
                    queue.offer(new Location(next.x, next.y));
                }
            }
        }

        return false;
    }

    static int getDistance(int x, int y, int nx, int ny) {
        return Math.abs(x - nx) + Math.abs(y - ny);
    }

    static class Location {
        int x, y;

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

결과