[BJ] 9205 : 맥주 마시면서 걸어가기

       문제 요약        

- 문제

 

- 입출력

         아이디어        

- 상근이네 집, 편의점, 펜타포트 락 페스티벌 좌표 i행 j열 는 거리를 계산하기 위해서 필요할 뿐, 좌표 자체 의미는 없다.

x,y값의 범위를 보면, 그러지 말라는 것을 예측할 수 있다.

 

- 0번 노드: 상근이네집, 1번 노드: 편의점(1), 2번 노드: 편의점(2) ...., N+2번 노드: 펜타포트 락 페스티벌 좌표 의 의미로 이해하고 코드를 작성하면 된다. 

 

BFS 풀이

-  A와 B 지점 사이의 거리가 1000m(50m * 20개)이내 라면, A <=> B 는 이동할 수 있는 간선이므로, 이를 간선리스트에 저장한다. 그리고 출발지로부터 도착지까지 갈 수 있는지 bfs를 활용하여 확인하면 된다.

 

         소스코드        

BFS 소스코드

package _week05._0310;

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

public class B9205 {
    static int T;
    static int N;
    /**
     * 출발(상근이네 집) ~ 맥주 한 박스(맥주 20개) ~ 1병/50m
     */
    static List<Point> points; // 좌표
    static List<Integer>[] adjList;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        T = Integer.parseInt(br.readLine());
        for (int t = 1; t <= T; t++) { // 테스트 케이스의 개수 T
            N = Integer.parseInt(br.readLine()); // 맥주를 파는 편의점의 개수 N

            points = new ArrayList<>(); // [좌표] 상근이네, 편의점, 펜타포트 락 페스티벌
            for (int n = 0; n < N + 2; n++) {
                st = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                points.add(new Point(x, y));
            }

            adjList = new ArrayList[N + 2];
            for (int i = 0; i < N + 2; i++) {
                adjList[i] = new ArrayList<>();
            }
            // 두 좌표 사이의 거리: x좌표의 차이 + y좌표의 차이
            for (int i = 0; i < N + 2; i++) {
                for (int j = i + 1; j < N + 2; j++) {
                    if (Point.distance(points.get(i), points.get(j)) <= 1000) { // 1000m
                        adjList[i].add(j);
                        adjList[j].add(i);
                    }
                }
            }

            if (bfs()) {
                System.out.println("happy");
            } else {
                System.out.println("sad");
            }
        }
    }

    private static boolean bfs() {
        boolean[] visited = new boolean[N + 2]; // 0 ~ N+1
        Queue<Integer> queue = new ArrayDeque<>();
        queue.add(0);
        visited[0] = true;
        while (!queue.isEmpty()) {
            int now = queue.poll();
            if (now == N + 1) {
                return true;
            }
            for (int next : adjList[now]) {
                if (visited[next]) continue;
                visited[next] = true;
                queue.add(next);
            }
        }
        return false;
    }

    static class Point {
        int x, y;

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

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

 

Floyd 소스코드

package _week05._0310;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class B9205_Floyd {
    static int T;
    static int N;
    /**
     * 출발(상근이네 집) ~ 맥주 한 박스(맥주 20개) ~ 1병/50m
     */
    static List<Point> points; // 좌표
    static boolean[][] isSearch;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        T = Integer.parseInt(br.readLine());
        for (int t = 1; t <= T; t++) { // 테스트 케이스의 개수 T
            N = Integer.parseInt(br.readLine()); // 맥주를 파는 편의점의 개수 N

            points = new ArrayList<>(); // [좌표] 상근이네, 편의점, 펜타포트 락 페스티벌
            for (int n = 0; n < N + 2; n++) {
                st = new StringTokenizer(br.readLine());
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                points.add(new Point(x, y));
            }

            isSearch = new boolean[N + 2][N + 2];
            // 두 좌표 사이의 거리: x좌표의 차이 + y좌표의 차이
            for (int i = 0; i < N + 2; i++) {
                for (int j = i + 1; j < N + 2; j++) {
                    if (Point.distance(points.get(i), points.get(j)) <= 1000) { // 1000m
                        isSearch[i][j] = isSearch[j][i] = true;
                    }
                }
            }

            floyd();
            if (isSearch[0][N + 1]) {
                System.out.println("happy");
            } else {
                System.out.println("sad");
            }
        }
    }

    private static void floyd() { // 플로이드 와샬 알고리즘 O(N*3) -> 잘 안씀
        for (int k = 0; k < N + 2; k++) {
            for (int i = 0; i < N + 2; i++) {
                for (int j = 0; j < N + 2; j++) {
                    if (isSearch[i][k] && isSearch[k][j]) {//i -> k경유지 -> j
                        isSearch[i][j] = true;
                        // dist(i,j) > dist(i,k) + dist(k,j) :경유
                    }
                }
            }
        }
    }

    static class Point {
        int x, y;

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

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

}

 

 

 

---

https://steady-coding.tistory.com/97

[BOJ] 백준 9205번 : 맥주 마시면서 걸어가기 (JAVA)