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

문제

송도에 사는 상근이와 친구들은 송도에서 열리는 펜타포트 락 페스티벌에 가려고 한다. 올해는 맥주를 마시면서 걸어가기로 했다. 출발은 상근이네 집에서 하고, 맥주 한 박스를 들고 출발한다. 맥주 한 박스에는 맥주가 20개 들어있다. 목이 마르면 안되기 때문에 50미터에 한 병씩 마시려고 한다.

 

상근이의 집에서 페스티벌이 열리는 곳은 매우 먼 거리이다. 따라서, 맥주를 더 구매해야 할 수도 있다. 미리 인터넷으로 조사를 해보니 다행히도 맥주를 파는 편의점이 있다. 편의점에 들렸을 때, 빈 병은 버리고 새 맥주 병을 살 수 있다. 하지만, 박스에 들어있는 맥주는 20병을 넘을 수 없다.

 

편의점, 상근이네 집, 펜타포트 락 페스티벌의 좌표가 주어진다. 상근이와 친구들이 행복하게 페스티벌에 도착할 수 있는지 구하는 프로그램을 작성하시오.

 

 

입력

첫째 줄에 테스트 케이스의 개수 t가 주어진다. (t ≤ 50)

 

각 테스트 케이스의 첫째 줄에는 맥주를 파는 편의점의 개수 n이 주어진다. (0 ≤ n ≤ 100).

 

다음 n+2개 줄에는 상근이네 집, 편의점, 펜타포트 락 페스티벌 좌표가 주어진다. 각 좌표는 두 정수 x와 y로 이루어져 있다. (두 값 모두 미터, -32768 ≤ x, y ≤ 32767)

 

송도는 직사각형 모양으로 생긴 도시이다. 두 좌표 사이의 거리는 x 좌표의 차이 + y 좌표의 차이 이다. (맨해튼 거리)

 

 

출력

각 테스트 케이스에 대해서 상근이와 친구들이 행복하게 페스티벌에 갈 수 있으면 "happy", 중간에 맥주가 바닥나면 "sad"를 출력한다.

 

 

풀이

이 문제는 2가지 풀이법이 있습니다. 전자는 BFS이고, 후자는 플로이드 와샬 알고리즘입니다.

 

BFS든 플로이드 와샬 알고리즘이든, 탐색을 하기 전에 먼저 해야하는 가장 중요한 과정이 있었습니다.

바로, 맨헤튼 거리 1000m 안에 갈 수 있는 정점을 서로 이어주는 것이죠.

(맥주 1병 당 50m 갈 수 있다고 했으므로, 50 * 20 = 1000m 입니다.)

 

따라서 집, 편의점, 페스티벌에 대한 좌표들을 저장하는 리스트를 정의하고, 그 리스트 중 임의의 두 인덱스를 선택해서 맨해튼 거리 1000m를 만족하는 정점 2개를 양방향 그래프로 이어주면 됩니다.  (BFS 방식)

 

또는, boolean[][] 타입의 배열을 정의하여 위에서 정의한 리스트 중 임의의 두 인덱스를 선택해서 맨해튼 거리 1000m를 만족하는 정점 2개에 대하여 true로 처리하면 됩니다.  (플로이드-와샬 알고리즘 방식)

 

여기까지 초기 과정이 완료되었습니다. 이제 탐색만 하면 됩니다.

 

 

BFS를 활용한 풀이

위에서 정의한 양방향 그래프에 대하여 BFS 탐색을 하면 됩니다.

전형적인 BFS 탐색을 사용하되, 끝점에 도달할 수 있으면 true를 반환하고 도달할 수 없으면 false를 반환하면 됩니다.

 

그리고 BFS가 true일 경우 "happy", false일 경우 "sad"를 출력하면 끝입니다.

 

 

BFS를 활용한 소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
class Point {
    int x;
    int y;
 
    Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}
 
public class Main {
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
 
        int T = Integer.parseInt(br.readLine());
 
        ArrayList<Point> a; // 집, 편의점, 페스티벌에 위치를 저장하는 배열
        ArrayList<ArrayList<Integer>> graph;
        
        StringBuilder sb = new StringBuilder();
        while (T-- > 0) {
            int N = Integer.parseInt(br.readLine());
 
            a = 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());
 
                a.add(new Point(x, y));
            }
 
            graph = new ArrayList<>();
            for (int i = 0; i < N + 2; i++) {
                graph.add(new ArrayList<>());
            }
            
            // 맨해튼 거리 1000m 이하를 만족하는 두 정점을 찾음.
            // 그리고 양방향 그래프로 서로 이어 줌.
            for (int i = 0; i < N + 2; i++) {
                for (int j = i + 1; j < N + 2; j++) {
                    if (Manhattan(a.get(i), a.get(j)) <= 1000) {
                        graph.get(i).add(j);
                        graph.get(j).add(i);
                    }
                }
            }
            
            // BFS를 이용하여 집에서 페스티벌까지 갈 수 있는지 탐색.
            sb.append((BFS(graph, N) ? "happy" : "sad") + '\n');
        }
        
        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }
    
    // 맨해튼 거리
    public static int Manhattan(Point p1, Point p2) {
        return Math.abs(p1.x - p2.x) + Math.abs(p1.y - p2.y);
    }
    
    // 전형적인 BFS 코드
    public static boolean BFS(ArrayList<ArrayList<Integer>> graph, int N) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(0);
 
        boolean[] visited = new boolean[N + 2];
        visited[0] = true;
 
        while (!q.isEmpty()) {
            int now = q.poll();
 
            if (now == N + 1) {
                return true;
            }
 
            for (int next : graph.get(now)) {
                if (!visited[next]) {
                    visited[next] = true;
                    q.offer(next);
                }
            }
        }
 
        return false;
    }
 
}

 

 

플로이드 와샬 알고리즘을 활용한 풀이

위에 과정에서 boolean[][] 타입의 배열을 이용합니다. 여기서 특정 인덱스의 값이 true일 경우, i에서 j로 이동할 수 있다는 의미이고, false일 경우, i에서 j로 이동할 수 없다는 의미입니다.

 

이것은 11403번 경로 찾기 문제와 상당히 유사합니다. 이 문제가 궁금하신 분은 아래 포스팅을 참조하시길 바랍니다.

 

 

[BOJ] 백준 11403번 : 경로 찾기 (JAVA)

 

 

우리가 할 일은 간단합니다. 주어진 boolean[][] 타입 배열을 플로이드 와샬 알고리즘을 활용하여 i에서 k로 이동하고, k에서 j로 이동할 수 있는 경로가 있는지 체크하여 추가로 true 처리를 하면 됩니다.

 

플로이드 와샬 알고리즘이 끝난 후, boolean[][] 타입 배열의 시작점과 끝점이 서로 연결되어있는지 확인하여, 적절히 "happy"와 "sad"를 출력하면 끝입니다.

 

 

플로이드 와샬 알고리즘을 활용한 소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.StringTokenizer;
 
class Point {
    int x;
    int y;
 
    Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}
 
public class Main {
 
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;
 
        int T = Integer.parseInt(br.readLine());
 
        ArrayList<Point> a; // 집, 편의점, 페스티벌에 위치를 저장하는 배열
        boolean[][] isSearch;
        
        StringBuilder sb = new StringBuilder();
        while (T-- > 0) {
            int N = Integer.parseInt(br.readLine());
 
            a = 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());
 
                a.add(new Point(x, y));
            }
            
            isSearch = new boolean[N + 2][N + 2];
            
            // 맨해튼 거리 1000m 이하를 만족하는 두 정점을 찾음.
            // 그 두 거리는 서로 연결되어있다고 판단하고,
            // 경로 배열에 true 처리를 함.
            for (int i = 0; i < N + 2; i++) {
                for (int j = i + 1; j < N + 2; j++) {
                    if (Manhattan(a.get(i), a.get(j)) <= 1000) {
                        isSearch[i][j] = isSearch[j][i] = true;
                    }
                }
            }
            
            fload(isSearch, N);
            
            sb.append((isSearch[0][N + 1] ? "happy" : "sad") + '\n');
        }
        
        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }
    
    // 맨해튼 거리
    public static int Manhattan(Point p1, Point p2) {
        return Math.abs(p1.x - p2.x) + Math.abs(p1.y - p2.y);
    }
    
    // 플로이드 와샬 알고리즘
    public static void fload(boolean[][] isSearch, int N) {
        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]) {
                        isSearch[i][j] = true;
                    }
                }
            }
        }
    }
 
}

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.