글 읽기 - java 코드 질문입니다. (질문란의 반례들은 전부 만족)

eksrks0310 2년 전 0

안녕하세요

이번에 치킨 거리 문제에 대한 코드를 짜보았는데 어느 부분에서 문제가 생긴 건지 몰라서 질문드립니다.

질문란의 반례란 반례는 모두 넣어봤는데 코드 제출 후 1%도 가지 않고 틀렸습니다가 나와서 어떤 부분이 문제일지 상상도 가지 않습니다 ㅠㅠ

각 리스트 house, store에 집, 치킨 가게의 위치들을 저장한 후

각 치킨 가게에서 집까지의 거리에 대한 이차원배열이 담긴 map을 len이라 두었습니다.

재귀를 통해 전체 가게들 중 m개의 가게를 선택합니다(store에서 선택한 m개의 가게의 인덱스가 list에 저장됨)

선택된 m개의 가게에 대하여, 각 집에서 치킨 가게까지의 거리들 중 가장 작은 값을 각 집의 위치에 대입시킵니다. (Math.min으로 최소거리 탐색)

대입한 모든 값들을 합하여 전역변수로 저장된 min과 비교해 더 작은 값을 저장합니다.

위의 과정을 전체 가게 중 m개를 고르는 경우의 수만큼 반복한 후 min을 출력하였습니다.

귀한 시간을 들여 읽어주셔서 감사합니다

import java.util.*;
import java.io.*;

public class Main{
    static FastScanner fs = new FastScanner();
    static PrintWriter pw = new PrintWriter(System.out);
    static List<int[]> house, store;
    static Map<int[], int[][]> len = new HashMap<>();
    static int n, min = Integer.MAX_VALUE;
    
    static int[][] count;

    public static void main(String[] args){
    	n = fs.nextInt();
    	int m = fs.nextInt();
    	
    	house = new ArrayList<>();
    	store = new ArrayList<>();
    	count = new int[n][n];
    	
    	for (int i=0;i<n;i++) {
    		for (int j=0;j<n;j++) {
    			switch (fs.nextInt()) {
    				case 1:
	    				house.add(new int[] {i, j});
	    				break;
    				case 2:
	    				store.add(new int[] {i, j});
	    				break;
    			}
    		}
    	}
    	
    	fill();
    	for (int i=0;i<store.size();i++) {
    		List<Integer> list = new ArrayList<>();
    		list.add(i);
    		solve(m - 1, list);
    	}
    	
    	pw.println(min);
    	pw.close();
    }
    
    static void solve(int m, List<Integer> list) {
    	if (m > 0) {
    		for (int i=list.get(list.size() - 1) + 1;i<store.size();i++) {
    			list.add(i);
    			solve(m - 1, list);
    			list.remove(list.size() - 1);
    		}
    	}
    	else {
    		count = len.get(store.get(list.get(0)));
    		
    		for (int i=1;i<list.size();i++) {
    			int[] now = store.get(list.get(i));
    			
    			for (int row=0;row<n;row++) {
    				for (int col=0;col<n;col++) {
    					count[row][col] = Math.min(count[row][col], len.get(now)[row][col]);
    				}
    			}
    		}
    		
    		int res = 0;
    		for (int i=0;i<n;i++) {
    			for (int j=0;j<n;j++) {
    				res += count[i][j];
    			}
    		}
    		min = Math.min(min, res);
    	}
    }
    
    static void fill() {
    	for (int[] st : store) {
    		int[][] temp = new int[n][n];
    		
    		for (int[] hs : house) {
    			temp[hs[0]][hs[1]] = Math.abs(st[0] - hs[0]) + Math.abs(st[1] - hs[1]);
    		}
    		
    		len.put(st, temp);
    	}
    }


//    ----------input function----------

    static void sort(int[] a){
        ArrayList<Integer> L = new ArrayList<>();
        for (int i : a) L.add(i);
        Collections.sort(L);
        for (int i = 0; i < a.length; i++) a[i] = L.get(i);
    }

    static class FastScanner{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer("");
        String next(){
            while (!st.hasMoreTokens()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException e){
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt(){
            return Integer.parseInt(next());
        }

        int[] readArray(int n){
            int[] a = new int[n];
            for (int i = 0; i < n; i++) a[i] = nextInt();
            return a;
        }

        long nextLong(){
            return Long.parseLong(next());
        }
    }
}

eksrks0310 2년 전 0

결국 어디서 틀렸는지는 못찾았고

집, 가게를 각각 클래스 선언해 백트래킹하는 코드로 새로 짜서 통과했습니다.

ㅠㅠ

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