[자바] 백준 9205 - 맥주 마시면서 걸어가기 (java)

 문제 : boj9205

---

 

필요 알고리즘 개념

• 너비 우선 탐색 (bfs), 깊이 우선 탐색(dfs), 분리 집합(disjoint set) 중 하나
  
  • 데이터를 원하는 형태로 바꾸는 사전작업이 좀 필요하다. 그것만 하면 그냥 가중치가 동일한 정점과 간선이 주어질 때 특정 지점부터 특정 지점까지 도달 가능하는지만 판단하면 되므로, bfs나 dfs나 분리집합이나 아무거나 써서 찾아주면 된다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  BFS를 모른다면 'BFS 알고리즘 (너비 우선 탐색) - 배열 BFS, 그래프 BFS' 글을 참고해보자. 저 글에서 '사실 배열 BFS도 그래프 BFS와 동일하다.' 부분에 나온 방식처럼 배열 데이터를 그래프 형태로 가공해서 풀 수 있는 문제이다.

 

  '50미터를 가려면 그 직전에 맥주 한 병을 마셔야 한다.'와 '편의점을 나선 직후에도 50미터를 가기 전에 맥주 한 병을 마셔야 한다.' 라는 부분이 있다. 어차피 항상 출발 전에 먹어야 하고, 어차피 맥주를 몇 병 사거나 몇 병 먹느냐는 이 문제에서 중요한게 아니므로, 항상 편의점 도착시에는 20병까지 전부 리필해버리면 된다.

 

  그렇다면 맥주 한병에 50미터이므로, 시작지점에서 편의점 혹은 편의점과 편의점 혹은 편의점과 도착점 사이에서 아무튼 50x20 = 1000미터 이내라면 어떻게든 갈 수 있다는걸 알 수 있다. 그렇다면 주어진 데이터의 출발점, 편의점들, 도착점들을 정점이라 생각했을 때, 도착 가능한(맨해튼 거리가 1000미터 이하인 곳) 정점끼리 간선으로 이어볼 수 있다. 예를들어 다음의 경우를 보자.

1
3
0 0
1000 0
0 1000
1000 1000
2000 1000

 

  위의 경우에 대해 얘기한대로 간선을 연결해보면 다음과 같다.

 

  그럼 이제 이 문제는 거리정보는 아예 의미가 없고, 그냥 정점들과 가중치가 동일한 간선들이 존재할 때 출발점에서 출발해 도착점으로 갈 수 있냐는 문제가 된다. 그럼 bfs를 써도 되고, dfs를 써도 되고, 분리 집합을 써도 되고 아무거나 써서 구해주면 된다.

 

...

for (int i = 0; i < list.size(); i++) {
    for (int j = i+1; j < list.size(); j++) {
        Pos a = list.get(i);
        Pos b = list.get(j);
        if (Math.abs(a.x-b.x)+Math.abs(a.y-b.y) > DISTANCE_LIMIT) continue;
        
        // 맨허튼 거리 기준으로 1000 이하라면 간선 연결
        edges[i].add(j);
        edges[j].add(i);
    }
}

// 이후 그냥 일반적인 bfs다.
Queue<Integer> q = new ArrayDeque<>();
boolean[] v = new boolean[list.size()];
q.add(0);
v[0] = true;
while (!q.isEmpty()) {
    int cur = q.poll();
    if (cur == list.size()-1) {	// 도착점을 찾을 시
        return true;
    }
    for (int next : edges[cur]) {
        if (v[next]) continue;
        v[next] = true;
        q.add(next);
    }
}
return false;	// 도착점을 못찾고 이 라인까지 왔다면 출발점에서 도달 못한거다.

---

 

코드 : github

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

public class Main {
    class Pos {
        int x, y;
        public Pos(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    private static final int DISTANCE_LIMIT = 1000;
    private static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws Exception {
        Main main = new Main();
        int t = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();
        while (t-->0) {
            boolean result = main.solution();
            sb.append(result ? "happy" : "sad");
            sb.append('\n');
        }
        System.out.print(sb);
    }

    public boolean solution() throws Exception {
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        Pos start = new Pos(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        List<Pos> list = new ArrayList<>();
        list.add(start);
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            list.add(new Pos(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
        }
        st = new StringTokenizer(br.readLine());
        Pos end = new Pos(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        list.add(end);

        List<Integer>[] edges = new ArrayList[list.size()];
        for (int i = 0; i < list.size(); i++) {
            edges[i] = new ArrayList<>();
        }

        for (int i = 0; i < list.size(); i++) {
            for (int j = i+1; j < list.size(); j++) {
                Pos a = list.get(i);
                Pos b = list.get(j);
                if (Math.abs(a.x-b.x)+Math.abs(a.y-b.y) > DISTANCE_LIMIT) continue;

                edges[i].add(j);
                edges[j].add(i);
            }
        }

        Queue<Integer> q = new ArrayDeque<>();
        boolean[] v = new boolean[list.size()];
        q.add(0);
        v[0] = true;
        while (!q.isEmpty()) {
            int cur = q.poll();
            if (cur == list.size()-1) {
                return true;
            }
            for (int next : edges[cur]) {
                if (v[next]) continue;
                v[next] = true;
                q.add(next);
            }
        }
        return false;
    }
}