[백준/JAVA] 28215번: 대피소

📖 문제

28215번: 대피소

 

 

 

💡  풀이 방식

#브루트포스 #시뮬레이션

N의 최대 크기가 50이어서 O(N^4)해도 괜찮으므로 브루트포스 가능.

 

대피소 갯수를 3개로 정하고 코드를 짜는 것이 핵심!

대피소가 1개인 경우는 3개 위치를 모두 동일하게 하고,

2개인 경우는 2개 위치 idx만 동일하게 하면 된다.

 

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, K;
    static int[][] arr;
    static int answer = Integer.MAX_VALUE;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        
        arr = new int[N][2];
        for(int i = 0 ; i < N ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
        }
        
        if(K == 1) { // 대피소가 1개인 경우
            for(int i = 0 ; i < N ; i++)
                answer = Math.min(answer, calc(i, i, i));
        }
        else if(K == 2) { // 대피소가 2개인 경우
            for(int i = 0 ; i < N - 1 ; i++) {
                for(int j = i + 1 ; j < N ; j++)
                    answer = Math.min(answer, calc(i, j, j)); // 대피소 2개 위치만 동일하게
            }
        }
        
        else if(K == 3) { // 대피소가 3개인 경우
            for(int i = 0 ; i < N - 2 ; i++) {
                for(int j = i + 1 ; j < N - 1 ; j++) {
                    for(int k = j + 1 ; k < N ; k++)
                        answer = Math.min(answer, calc(i, j, k));
                }
            }     
        }
            
        System.out.println(answer);
    }
    
    // 가장 최단 거리로 i번째 위치의 거리를 반환하고, 그 값의 max를 리턴하는 메서드
    private static int calc(int a, int b, int c) {
        int ans = 0;
        
        for(int i = 0 ; i < N ; i++) {
            int tmp1 = Math.abs(arr[i][0] - arr[a][0]) + Math.abs(arr[i][1] - arr[a][1]);
            int tmp2 = Math.abs(arr[i][0] - arr[b][0]) + Math.abs(arr[i][1] - arr[b][1]);
            int tmp3 = Math.abs(arr[i][0] - arr[c][0]) + Math.abs(arr[i][1] - arr[c][1]);
            
            ans = Math.max(ans, Math.min(Math.min(tmp1, tmp2), tmp3));
        }
        
        return ans;
    }
}
 

 

 

 

➕ 다른 풀이 방식

- 대피소의 1-3개 위치를 백트래킹으로 잡고 진행하신 풀이

https://www.acmicpc.net/source/71571706

https://www.acmicpc.net/source/70120356

 

- 4중 for문... 메소드 통일 안 하고 매번 다르게 계산한 풀이,, (좀 더 느리다)

코드 확인하기

import java.util.*;
import java.io.*;
 
public class Main {
    static int N, K;
    static int[][] arr;
    static int answer = Integer.MAX_VALUE;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        
        arr = new int[N][2];
        for(int i = 0 ; i < N ; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            arr[i][0] = Integer.parseInt(st.nextToken());
            arr[i][1] = Integer.parseInt(st.nextToken());
        }
        
        if(K == 1) {
            for(int i = 0 ; i < N ; i++) {
                int dist = 0;
                
                for(int j = 0 ; j < N ; j++) {
                    int tmp = Math.abs(arr[i][0] - arr[j][0]) + Math.abs(arr[i][1] - arr[j][1]);
                    dist = Math.max(dist, tmp);
                }
                
                answer = Math.min(answer, dist);
            }
        }
        else if(K == 2) {
            for(int i = 0 ; i < N - 1 ; i++) {
                for(int j = i + 1 ; j < N ; j++) {
                    int dist = 0;
                    
                    for(int k = 0 ; k < N ; k++) {
                        int tmp1 = Math.abs(arr[i][0] - arr[k][0]) + Math.abs(arr[i][1] - arr[k][1]);
                        int tmp2 = Math.abs(arr[j][0] - arr[k][0]) + Math.abs(arr[j][1] - arr[k][1]);
                        dist = Math.max(dist, Math.min(tmp1, tmp2));
                    }
                    
                    answer = Math.min(answer, dist);
                }
            }
        }
        else if(K == 3) {
            for(int i = 0 ; i < N - 2 ; i++) {
                for(int j = i + 1 ; j < N - 1 ; j++) {
                    for(int k = j + 1 ; k < N ; k++) {
                        int dist = 0;
                        
                        for(int a = 0 ; a < N ; a++) {
                            int tmp1 = Math.abs(arr[i][0] - arr[a][0]) + Math.abs(arr[i][1] - arr[a][1]);
                            int tmp2 = Math.abs(arr[j][0] - arr[a][0]) + Math.abs(arr[j][1] - arr[a][1]);
                            int tmp3 = Math.abs(arr[k][0] - arr[a][0]) + Math.abs(arr[k][1] - arr[a][1]);
                            dist = Math.max(dist, Math.min(Math.min(tmp1, tmp2), tmp3));
                        }
                        
                        answer = Math.min(answer, dist);
                    }
                }
            }        
        }
        
        System.out.println(answer);
    }
}
 

---

💦 어려웠던 점

- 처음에는 대피소가 1개일 때, 2개일 때, 3개일 때 모두 각각 반복문 안에서 가장 짧은 거리를 매번 계산하도록 했었고,, Math.min이랑 max 제대로 안 적어서 틀렸었다,, (문제를 제대로 읽자!)

 

- 푸는 건 다 푸는데 얼마나 빠르게 푸느냐가 관건일 듯,,,

 

 

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

---

(참고)

[BruteForce] 백준 28215, 대피소