[자바] 백준 30536 - 시루의 산책 (java)

목차

문제 : boj30536

 

 

필요 알고리즘

• 그래프 이론, bfs (너비 우선 탐색)
  
  • 문제에서 제시된 데이터를 그래프로 생각하고, 적절한 방식으로 탐색해서 풀 수 있는 문제이다.

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

 

 

풀이

  우선.. 내 경우 맞왜틀을 많이 외친 문제였다 ㅠ. 그 이유는 아래와 같다.

 

1. 난 각 기둥의 상태가 'A. 다른 강아지 마킹 있음', 'B. 마킹은 없으나 다른 강아지 냄새가 영향을 끼침', 'C. 마킹도 없고 다른 강아지 냄새가 영향을 안끼침' 이렇게 3가지로 생각했다. 그리고 'A'는 시루의 냄새로 덮이게 되더라도 마킹이 불가하다고 생각했다. 결론적으론 'A'도 시루의 냄새로 덮이게 되면 시루가 마킹 가능하다. 이건 개인적으론 문제에 명확히 제시되지 않아서 문제가 좀 아쉬웠다.

 

2. 이건 내 실수인데, Pi 는 겹칠 수 있다! 즉, 3번 기둥에 4마리의 다른 강아지가 마킹했을 수 있다. 이 때 유의미한건 이중 Ri가 가장 큰 마킹이므로 그 값만 알면 된다. 내 경우 이 부분을 늦게 깨달아서 맞왜틀 수가 더 늘어났다.

 

---

 

  풀이는 말로 설명하면 " 'C' 형태의 모든 기둥에 시루가 마킹을 하고, R0 이내에 존재하는 다른 기둥을 차례차례 마킹한다.' 이다. 즉, 'C' 형태의 모든 기둥에서 시작하며 R0 이내의 모든 기둥을 간선으로 이어주어 그래프 탐색을 하면 된다.

 

- 간선 만들기 : R0을 기준으로 모든 정점에서 모든 정점으로 간선을 이어주면 된다.

private List<Integer>[] findEdgesBaseOnR0(Pillar[] arr, int n, int r) {
    List<Integer>[] edges = new List[n+1];
    for (int i = 1; i <= n; i++) edges[i] = new ArrayList<>();

    for (int i = 1; i <= n; i++) {
        for (int j = i+1; j <= n; j++) {
            if (!reachable(arr[i], arr[j], r)) continue;

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

    return edges;
}

 

 

- 이 때 주의점은 두 기둥의 거리를 구하기 위해선 루트값을 알아야하는데, 그럼 double형으로 비교를 해야한다. double형 비교는 피할 수 있으면 최대한 피해야 한다 (오차로 인해). 이 문제의 경우 양변을 모두 제곱해주면 된다. 즉, 두 기둥의 거리의 제곱이면 루트를 안쓰고 정수로 계산 가능하다.

private boolean reachable(Pillar a, Pillar b, int r) {
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y) <= r*r;
}

 

 

- 아무 영향도 안받는 기둥 역시 모든 기둥의 쌍을 확인하면 구할 수 있다.

private List<Integer> findStartPoint(final Pillar[] arr, final int n) {
    boolean[] chk = new boolean[n+1];
    for (int i = 1; i <= n; i++) {
        if (arr[i].r == -1) continue;
        chk[i] = true;

        for (int j = 1; j <= n; j++) {
            if (i == j) continue;

            if (reachable(arr[i], arr[j], Math.max(arr[i].r, arr[j].r)))
                chk[j] = true;
        }
    }

    List<Integer> ans = new ArrayList<>();
    for (int i = 1; i <= n; i++) {
        if (!chk[i])
            ans.add(i);
    }

    return ans;
}

 

 

- 이후 위에서 구한 아무 영향도 안받는 기둥에서부터 시작해 무지성 그래프 탐색을 해주면서 개수를 세주면 된다.

Queue<Integer> q = new ArrayDeque<>(startPoint);

while (!q.isEmpty()) {
    int cur = q.poll();

    for (int next : edges[cur]) {
        if (v[next]) continue;
        v[next] = true;

        answer++;
        q.add(next);
    }
}

 

 

 

코드 : github

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1<<16);

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    public void solution() throws Exception {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        Pillar[] arr = new Pillar[n+1];
        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            arr[i] = new Pillar(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }

        st = new StringTokenizer(br.readLine());
        StringTokenizer pst = new StringTokenizer(br.readLine());
        int r = Integer.parseInt(pst.nextToken());
        while (m-->0) arr[Integer.parseInt(st.nextToken())].marking(Integer.parseInt(pst.nextToken()));

        List<Integer>[] edges = findEdgesBaseOnR0(arr, n, r);
        List<Integer> startPoint = findStartPoint(arr, n);

        int answer = startPoint.size();
        boolean[] v = new boolean[n+1];
        for (int cur : startPoint) v[cur] = true;
        Queue<Integer> q = new ArrayDeque<>(startPoint);

        while (!q.isEmpty()) {
            int cur = q.poll();

            for (int next : edges[cur]) {
                if (v[next]) continue;
                v[next] = true;

                answer++;
                q.add(next);
            }
        }

        System.out.println(answer);
    }

    private List<Integer> findStartPoint(final Pillar[] arr, final int n) {
        boolean[] chk = new boolean[n+1];
        for (int i = 1; i <= n; i++) {
            if (arr[i].r == -1) continue;
            chk[i] = true;

            for (int j = 1; j <= n; j++) {
                if (i == j) continue;

                if (reachable(arr[i], arr[j], Math.max(arr[i].r, arr[j].r)))
                    chk[j] = true;
            }
        }

        List<Integer> ans = new ArrayList<>();
        for (int i = 1; i <= n; i++) {
            if (!chk[i])
                ans.add(i);
        }

        return ans;
    }

    private List<Integer>[] findEdgesBaseOnR0(Pillar[] arr, int n, int r) {
        List<Integer>[] edges = new List[n+1];
        for (int i = 1; i <= n; i++) edges[i] = new ArrayList<>();

        for (int i = 1; i <= n; i++) {
            for (int j = i+1; j <= n; j++) {
                if (!reachable(arr[i], arr[j], r)) continue;

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

        return edges;
    }

    private boolean reachable(Pillar a, Pillar b, int r) {
        return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y) <= r*r;
    }
}

class Pillar {
    int x, y, r = -1;

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

    public void marking(int dist) {
        this.r = Math.max(this.r, dist);
    }
}