백준 7571 점 모으기 Java

정보올림피아드 easy 문제집에서 만난 점모으기 문제이다.

 

n * n의 배열에 점의 좌표가 주어지고

점이 상 하 좌 우로 움직일 수 있을 때

점들이 한곳에 모이는 가장 최단 거리를 출력하는 문제이다.

 

최단거리면 당연히 BFS라고 생각하고

BFS로 풀었다가

메모리 초과, 시간초과의 늪에 빠졌다.

 

다시 문제를 보니까

거리를 구할 때 굳이 BFS로 가지 않아도 점의 좌표값과 모일 곳의 좌표값을 뺀 후 절대값으로 만들면

거리를 구할 수 있는 것을 발견한 후

n*n의 배열의 모든 경우에 m만큼의 좌표만큼 거리를 더하고 최솟값을 출력했다.

결과는 시간초과였다.

 

어떻게보면 당연히 시간초과인데 이 방법말고는 생각이 나질 않았다.

 

그렇게 포기하고 답을 찾아봤는데 해결법은 중앙값을 구하는 것이였다.

좌표값이 주어질 때 x값 y값이 주어지는데.

x값들만 모은 배열을 만들고

y값들만 모은 배열을 만든다.

 

그 후에 

x배열, y배열을 정렬한 후 

x배열, y배열에서 그 중앙값을 찾으면

그 중앙값이 모든 점들이 모였을 때 최단 거리인 좌표 이다.

 

그 중앙값의  좌표와 점들의 좌표를 뺀 절대값을 더하면 정답인 것이다.

변명아닌 변명을 하자면 이 방법이 머리속을 스쳐가긴 했는데

그렇게 한다고 최단거리 좌표가 나올리가 있어~하고

모든 경우의 거리를 다 구했었다..

쨌든 코드는 간단하다.

public static void main(String[] args) throws IOException{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(reader.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int [] xArr = new int[m];
        int [] yArr = new int[m];
        
        
        for(int i=0; i<m; i++) {
            st = new StringTokenizer(reader.readLine());
            xArr[i] = Integer.parseInt(st.nextToken());
            yArr[i] = Integer.parseInt(st.nextToken());
        }
 
        Arrays.sort(xArr);
        Arrays.sort(yArr);
        
        int xMid = xArr[m/2];
        int yMid = yArr[m/2];
        
        int ans = 0;
        for(int i=0; i<m; i++) {
            ans += Math.abs(xMid - xArr[i]) + Math.abs(yMid - yArr[i]);
        }
        
        System.out.println(ans);
    }