글 읽기 - (Java) 시간 초과를 어떻게 해결할 수 있을까요...

an286 2년 전 0

M개의 치킨집을 선택하여 집별로 가까운 치킨집까지의 거리를 구하는 방식으로 구현하였습니다.

이전에 거리를 BFS로 구하여 시간초과가 발생하나해서 바꿨는데도 똑같이 시간초과가 발생하네요

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.PriorityQueue;

// 치킨 배달

public class Main {
    static int size, closeMax, shopSize, minDistance;

    static LinkedList<Position> shopList, selectList;
    static ArrayList<Position> houseList;
    static boolean[] used;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] sizeStr = br.readLine().trim().split(" ");

        size = Integer.parseInt(sizeStr[0]);
        closeMax = Integer.parseInt(sizeStr[1]);

        shopList = new LinkedList<>();
        houseList = new ArrayList<>();

        for (int i = 0; i < size; i++) {
            String[] input = br.readLine().trim().split(" ");
            for (int j = 0; j < size; j++) {
                int now = Integer.parseInt(input[j]);

                if(now == 2){
                    shopList.add(new Position(i, j));
                }else if(now == 1){
                    houseList.add(new Position(i, j));
                }
            }
        }
        shopSize = shopList.size();
        used = new boolean[shopSize];
        selectList = new LinkedList<>();
        minDistance = Integer.MAX_VALUE;

        selectShop(0, 0);
        System.out.println(minDistance);
    }

    static void selectShop(int count, int start){
        if(count == closeMax){
            calculateDistance();
            return;
        }

        for (int i = start; i < shopSize; i++) {
            if(!used[i]){
                selectList.add(shopList.get(i));
                used[i] = true;
                selectShop(count + 1, start + 1);
                used[i] = false;
                selectList.removeLast();
            }
        }
    }

    static void calculateDistance(){
        int distanceSum = 0;
        for (Position house : houseList) {
            int min = Integer.MAX_VALUE;

            for (Position shop : selectList) {
                int nowDistance = Math.abs(house.i - shop.i) + Math.abs(house.j - shop.j);
                min = Math.min(min, nowDistance);
            }
            distanceSum += min;
            if(distanceSum >= minDistance){
                return;
            }
        }
        minDistance = Math.min(minDistance, distanceSum);
    }

    static class Position{
        int i, j;

        Position(int i, int j){
            this.i = i;
            this.j = j;
        }
    }
}

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

(Java) 시간 초과를 어떻게 해결할 수 있을까요...

an286 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말