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

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

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

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

 

해결 방법

1트

문제를 읽고 DFS를 이용하여 해결하려고 했습니다.
하지만, 구현해 보니 페스티벌에 갈수 있는지 없는지 판별하기가 어려웠습니다.
경로 하나만 맥주를 다 못마시면 sad를 출력했기 때문입니다. ㅠㅠ

 

2트

BFS를 사용해보았습니다.
그런데 x, y 좌표가 음수의 값을 갖을 수도 있습니다..
그래서 문제를 해결하지 못했습니다.

 

3트

결국 다른 사람의 풀이를 보고 해결했습니다.

맥주는 20개 까지 갖고 다닐 수 있기 때문에 최대 1000m를 움직일 수 있습니다.
그리고 입력값으로 경로를 줄때 반드시 순차적으로 주지 않을 수도 있습니다.

중간에 1번 sad가 나왔다고 해서 락페스티벌에 참가를 못하는 것이 아닙니다.
따라서 시작점을 기준으로 모든 경로를 탐색해야 합니다.

 

처음에 주어진 좌표를 이용하여 맨하튼 거리를 계산하고
이를 이용하여 거리 1000m 이하인 것은 노드로 저장하지 않습니다.

 

이게 무슨 말이냐면

1. 인접 리스트에 주어진  x, y 좌표를 저장한다.
2. 이를 이용해서 맨하튼 거리를 계산합니다.
3. 거리가 1000m이하인 것만 1차원 노드로 변환하여 인접 리스트에 저장합니다.

 

코드로 표현하면 다음과 같습니다.

// 집, 편의점, 도착지 좌표 저장
path = new ArrayList<>();
for(int i = 0; i < n+2; i++) {
    StringTokenizer st = new StringTokenizer(br.readLine());
    int x = Integer.parseInt(st.nextToken());
    int y = Integer.parseInt(st.nextToken());

    path.add(new Node(x, y));
}

// 인접 리스트 초기화
graph = new ArrayList<>();
for(int i = 0; i < n + 2; i++) {
    graph.add(new ArrayList<>());
}

// 맥주마시면서 갈수 있는 좌표만 인접 리스트에 저장
for(int i = 0; i < n + 2; i++) {
    for(int j = i + 1; j < n + 2; j++) {
        Node node1 = path.get(i);
        Node node2 = path.get(j);

        // 맥주 마시면서 갈수 있는 최대거리는 1000미터
        if(getManhattanDistance(node1.getX(), node1.getY(), node2.getX(), node2.getY()) <= 1000) {
              // 양방향
            graph.get(i).add(j);
            graph.get(j).add(i);
        }
    }
}

 

이렇게 하면 출발점에서 시작해서 인접한 모든 노드의 경로를 탐색할 수 있습니다.
마지막 도착점에 도달하지 못하면 sad, 도착하면 happy를 출력하면 됩니다.^^

풀이

public class Quiz9205 {
    static int n;
    static boolean[] visited;
    static List<Integer>[] newMap;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int t = Integer.parseInt(br.readLine());

        for(int tc = 0; tc < t; tc++) {
            n = Integer.parseInt(br.readLine());

            // x,y를 저장하는 리스트 생성
            List<Node> path = new ArrayList<>();

            // 시작점, 편의점, 도착점 저장
            for(int i = 0; i < n + 2; i++) {
                StringTokenizer st = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());

                path.add(new Node(x, y));
            }

            // 인접 리스트 생성
            newMap = new ArrayList[n+2];
            for(int i = 0; i < n + 2; i++) {
                newMap[i] = new ArrayList<>();
            }

            for(int i = 0; i < n + 2; i++) {
                for(int j = i + 1; j < n + 2; j++) {
                    Node node1 = path.get(i);
                    Node node2 = path.get(j);

                    // 거리가 1000m 이하이면
                    if(getManhattanDistance(node1.getX(), node1.getY(), node2.getX(), node2.getY()) <= 1000) {
                        // i, j를 노드라고 생각하고 경로 생성
                        // 양방향
                        newMap[i].add(j);
                        newMap[j].add(i);
                    }
                }
            }

            // newMap에는 인접한 거리가 1000m이하인 경로들로 이루어져 있다.
            // 1000m이하이니까 무조건 happy 아닌가? 라고 생각할 수 있는데
            // 1000m이하로 이루어져 있더라도, 도착점에 가지 못하면 sad입니다.
            visited = new boolean[n+2];
            String bfs = bfs(0);

            sb.append(bfs).append("\n");
        }

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

    private static String bfs(int start) {
        Queue<Integer> queue = new ArrayDeque<>();
        // 시작점 삽입
        queue.add(start);
        visited[start] = true;

        while (!queue.isEmpty()) {
            // 노드를 꺼낸다.
            Integer poll = queue.poll();

            // 도착점에 도착하면
            if(poll == n + 1) {
                return "happy";
            }

            // 인접 노드를 탐색
            for(Integer node : newMap[poll]) {
                // 인접 노드에 방문 이력이 없으면
                if(!visited[node]) {
                    visited[node] = true;
                    queue.add(node);
                }
            }
        }

        return "sad";
    }

    // 맨하튼 거리 계산
    private static int getManhattanDistance(int startX, int startY, int endX, int endY) {
        return Math.abs(startX - endX) + Math.abs(startY - endY);
    }

    static class Node {
        private int x;
        private int y;

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

        public int getX() {
            return x;
        }

        public int getY() {
            return y;
        }
    }
}