[백준 JAVA] 15686번: 치킨 배달

https://www.acmicpc.net/problem/15686

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {

	public static int[][] a, home_map, chik_map;
	public static int[] arr, what;
	public static int n, m, home = 0, chik = 0, ans, min = 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.valueOf(st.nextToken());
		m = Integer.valueOf(st.nextToken());
		a = new int[n][n];
		
		chik_map = new int[2][13];
		home_map = new int[2][2 * n];
		what = new int[m];
		for (int i = 0; i < n; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 0; j < n; j++) {
				a[i][j] = Integer.valueOf(st.nextToken());
				if (a[i][j] == 2) {
					chik_map[0][chik] = i;
					chik_map[1][chik] = j;
					chik++;
				} else if (a[i][j] == 1) {
					home_map[0][home] = i;
					home_map[1][home] = j;
					home++;
				}
			}
		}
		
		arr = new int[home];
		
		Arrays.fill(arr, Integer.MAX_VALUE);
		
		dfs(0,0);
		
		System.out.println(min);
		
	}
	
	public static void dfs(int at, int depth){
		
		if(depth == m) {
			Arrays.fill(arr, Integer.MAX_VALUE);
			for(int d : what) {
				distance(d);
			}
			int sum = 0;
			for(int d : arr) {
				sum += d;
			}
			if(min > sum)
				min = sum;
			return;
		}
		for(int i = at;i<chik;i++) {
			what[depth] = i;
			dfs(i + 1, depth+1);
		}
	}
	
	public static void distance(int chik) {
		for(int i = 0 ;i < home; i++) {
			int r = Math.abs(home_map[0][i] - chik_map[0][chik]);
			int c = Math.abs(home_map[1][i] - chik_map[1][chik]);
			if(arr[i] > r+c) {
				arr[i] = r+c;
			}
		}
	}
}

 

public static int[][] a;
public static int[][] b;
public static int n, m, k, ans, min = MAX_INT;

n, m 입력

지도 입력
치킨집 갯수 저장

치킨집은 배열에 저장 갯수 중 m개 골라서 나머지는 탐색하지 않고 dfs 조합

거리 구하기

각 거리의 최솟값 구하고

거리합 중 최소값 구하기

가장 가까운 치킨 집과의 거리를 어떻게 구하지?

1. 치킨집을 다 넣고 최소값을 구한다. 100 * 13

 

스승님의 일침!

 

1. 좀 더 구체화해서 동작 과정을 적었으면 좋겠다. 

  예를들면 단순히 거리구하기가 아니라 뭐 길이를 뺀 절대값을 더해서 이런과정 문제를 정리하는 곳이라 생각해도 될꺼같다.

또한 이 문제를 챗지피티한테 이런식으로 풀어라 라고 물어본다면 -> 좀더 컴퓨터가 알아듣기 좋게끔 바꿔야한다.

컴퓨터가 알아듣기 좋은 언어로 바꾸는 과정 필요

 

2. 나의 피드백 대충 이런식으로 해서 짜자 보다는 정확하게 어떤식으로 동작할지 예상하고 코드를 짜보자.

특히 재귀함수를 작성할때 어떤기능이 어디에 들어가야할지 생각하고 코드를 짜보자.