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

📖 문제

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

 

 

 

💡  풀이 방식

• 플로이드 와샬

필요 자료구조
- 위치들 저장용 리스트
- 위치들 중 두 지점 간 방문 가능한지 표시하는 2차원형 boolean형 배열

 

1. 모든 위치들을 입력받아 리스트에 저장한다.

2. 모든 위치들 중 2개를 골라 두 위치 간의 맨해튼 거리를 계산한다. (맨해튼 거리가 1000 이하라면 해당 거리로 이동할 수 있다.)

3. 지점 A에서 B로 이동 가능하고, B에서 C로 이동 가능하다면 A에서 C로 이동 가능하므로 이동 가능하다는 표시를 한다. (플로이드-와샬)

 

 

💥 유의사항

플로이드-와샬은 시간 복잡도가 O(N^3)이므로 사용 시 주의가 필요하다.

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int T;
    static StringBuilder sb = new StringBuilder();
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        T = Integer.parseInt(br.readLine());
        while(T --> 0) {
            int N = Integer.parseInt(br.readLine());
            
            // 리스트에 위치들 저장
            List<int[]> list = new ArrayList<>();
            for(int i = 0 ; i < N+2 ; i++) {
                st = new StringTokenizer(br.readLine(), " ");
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                
                list.add(new int[]{x,y});
            }
            
            boolean[][] flag = new boolean[N+2][N+2];   // 도착 가능한지 나타내는 배열
            for(int i = 0 ; i < N+2 ; i++) {
                for(int j = 0 ; j < N+2 ; j++) {
                    int[] now = list.get(i);
                    int[] next = list.get(j);
                    
                    int dist = Math.abs(now[0] - next[0]) + Math.abs(now[1] - next[1]); // 맨해튼 거리 계산
                    if(dist <= 1000)
                        flag[i][j] = true;
                }
            }
            
            // [플로이드 와샬] A에서 B로 이동 가능하고, B에서 C로 이동 가능하면, A에서 C로 이동 가능
            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(flag[i][k] && flag[k][j])
                            flag[i][j] = true;
                    }
                }
            }
            
            sb.append(flag[0][N+1] ? "happy\n" : "sad\n");
        }
        
        System.out.println(sb.toString());
    }
}

 

 

 

➕ 다른 풀이 방식

- BFS를 활용한 풀이1

1. 편의점 위치들 N개를 리스트에 저장한다. (상근이네 집, 펜타포트 락 페스티벌 좌표는 따로 변수에 저장해둔다.)

2. 상근이네 집 위치부터 큐에 추가하며 BFS를 수행한다.

  ㄴ 현재 위치와 락페스티벌 위치 간 맨해튼 거리가 1000 미터 이하면 방문 가능하다.

  ㄴ 현재 위치부터 방문하지 않은 다른 편의점들 위치들을 돌면서 두 위치 간 맨해튼 거리가 1000 이하면, 해당 지점을 방문 처리하고 큐에 추가해 마저 탐색한다.

import java.util.*;
import java.io.*;
 
public class Main {
    static int T, N, sx, sy, dx, dy;
    static StringBuilder sb = new StringBuilder();
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        
        T = Integer.parseInt(br.readLine());
        while(T --> 0) {
            N = Integer.parseInt(br.readLine());
            
            List<int[]> list = new ArrayList<>();
            for(int i = 0 ; i < N+2 ; i++) {
                st = new StringTokenizer(br.readLine(), " ");
                int x = Integer.parseInt(st.nextToken());
                int y = Integer.parseInt(st.nextToken());
                
                if(i == 0) {
                    sx = x;
                    sy = y;
                }
                else if(i == N+1) {
                    dx = x;
                    dy = y;
                }
                else {
                    list.add(new int[]{x,y});
                }
            }
            
            sb.append(bfs(list) ? "happy\n" : "sad\n");
        }
        System.out.println(sb.toString());
    }
    
    private static boolean bfs(List<int[] > list) {
        boolean[] visited = new boolean[N];
        
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[] {sx, sy});
        
        while(!q.isEmpty()) {
            int[] now = q.poll();
            
            int px = now[0];
            int py = now[1];
            if(Math.abs(px-dx) + Math.abs(py-dy) <= 1000) {
                return true;
            }
            
            for(int i = 0 ; i < N ; i++) {
                if(!visited[i]) {
                    int nx = list.get(i)[0];
                    int ny = list.get(i)[1];
                    int dist = Math.abs(px-nx) + Math.abs(py-ny);
                    if(dist <= 1000) {
                        visited[i] = true;
                        q.add(new int[] {nx, ny});
                    }
                }
            }
        }
 
        return false;
    }
}

 

 

 

- BFS 풀이2인데 약간 다르다

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

 

---

💦 어려웠던 점

- 맥주 한 박스에 20개 있고, 50미터에 한 병씩 맥주를 마신다는 조건을 어떻게 내가 충족시켜주어야 하나라는 문제..

- 가장 가까운 위치부터 정렬해서 방문하면서 해야 하나? 라는 생각을 했었다..

 

 

🧐 새로 알게 된 내용

- A에서 B로 갈 수 있으면, B에서 C도 갈 수 있게 하는 BFS

- 맨해튼 거리가 1000m 이내여야 하는 이유 : 맥주 1병 50m * (시작 지점-편의점) or (편의점-편의점) or (편의점-도착지) 간 20병 = 1000m

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

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