[BOJ/JAVA] 백준 15686번 : 치킨 배달 (좀 더 공부해보자)

15686번: 치킨 배달

---

 

• 코드

실패 코드 : 시간 초과 백트래킹으로 치킨 집의 수가 M일 때까지 되돌려가면서 돌려줌. 치킨 집의 수가 M이 되었을 때 모든 치킨집과 집의 거리의 수를 더해준 값을 return 해준다. return 값 중 최소 값을 출력.

 

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

public class Main {
	static int[][] array;
	static boolean[][] check;
	static ArrayList<int[]> houses;
	static int N, M, 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.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		array = new int[N + 1][N + 1];
		houses = new ArrayList<>();

		int count = 0;
		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 1; j <= N; j++) {
				array[i][j] = Integer.parseInt(st.nextToken());
				if (array[i][j] == 2)
					count++;
				if (array[i][j] == 1)
					houses.add(new int[] { i, j });
			}
		}

		dfs(count);
		System.out.println(min);
	}

	// 치킨 집의 수가 M일 때까지 줄임
	// DFS 재귀 형식
	private static void dfs(int count) {
		// base case (치킨 집의 개수가 M이 되었을 때)
		if (count == M) {
			min = Math.min(min, bfs());
			return;
		}

		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				if (array[i][j] == 2) {
					array[i][j] = 0;
					dfs(count - 1);
					array[i][j] = 2;
				}
			}
		}
	}

	private static int bfs() {
		// 임시 배열 (기존 배열을 유지하기 위함)
		Queue<int[]> queue = new LinkedList<>();
		for (int i = 1; i <= N; i++)
			for (int j = 1; j <= N; j++)
				if (array[i][j] == 2)
					queue.add(new int[] { i, j });

		// 벽으로 보호되지 않은 곳은 virus를 퍼뜨림
		// BFS
		int sum = 0;
		while (!queue.isEmpty()) {
			int location[] = queue.poll();

			for (int[] house : houses)
				sum += ReturnAbsoluteValue(location[0], house[0]) + ReturnAbsoluteValue(location[1], house[1]);

		}
		return sum;
	}

	private static int ReturnAbsoluteValue(int a, int b) {
		if (a > b)
			return a - b;
		else
			return b - a;
	}
}

 

 

정답 코드 : stack에 치킨집을 하나씩 push, pop해주며 stack의 개수가 M개일 때, 최소 거리를 구해줌.

 

개선 사항

백트래킹으로 제거해주면서 돌리던 부분 => stack을 통해 해당 치킨집만 스택에 push, pop하며 push한 개수가 M개 일 때 체크한 뒤 마지막 push를 pop해줌 (위의 코드에서 bfs 첫번째 for문 O(n^2) 작업을 안해도됌)

 

 

import java.io.IOException;
import java.io.InputStream;
import java.util.ArrayList;
import java.util.InputMismatchException;
import java.util.Stack;

public class Main {
    static int N, M;
    static int[][] array;
    static ArrayList<int[]> chickens;
    static ArrayList<int[]> houses;
    static Stack<int[]> selectedChicken;
    static int min;
	
    public static void main(String[] args) throws Exception {
        SetData();
        SelectChicken(0, 0);
        System.out.println(min);
    }
    
	private static void SetData() throws Exception {
		InputReader in = new InputReader(System.in);

        N = in.readInt();
        M = in.readInt();

        array = new int[N + 1][N + 1];
        min = Integer.MAX_VALUE;
        chickens = new ArrayList<>();
        houses = new ArrayList<>();
        selectedChicken = new Stack<>();

        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                array[i][j] = in.readInt();

                if (array[i][j] == 1) {
                	// 집
                    houses.add(new int[] {i, j});
                } else if (array[i][j] == 2) {
                    // 치킨집
                    chickens.add(new int[] {i, j});
                }
            }
        }
	}
	
    static void SelectChicken(int start, int count) {
    	// Basecase
        if (count == M) {
            bfs();
            return;
        }

        // 선택된 치킨집 3개를 구하기 위함.
        for (int i = start; i < chickens.size(); i++) {
        	selectedChicken.push(chickens.get(i));
            SelectChicken(i + 1, count + 1);
            selectedChicken.pop();
        }
    }

    static void bfs() {
        int sum = 0;
        for (int[] house : houses) {
            int tempMin = Integer.MAX_VALUE;
            
            // 해당 치킨집에서의 최소 배달 지역 집을 선택
            for (int[] chicken : selectedChicken) {
                int tempValue = Math.abs(house[0] - chicken[0]) + Math.abs(house[1] - chicken[1]);
                tempMin = Math.min(tempMin, tempValue);
            }
            sum += tempMin;

            // 현재까지의 값이 구하려는 최소값보다 크면 작업을 더 안해도 됨 => return
            if (sum > min) {
                return;
            }
        }
        min = Math.min(sum, min);
    }
	
	private static class InputReader {
		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;
		private SpaceCharFilter filter;

		public InputReader(InputStream stream) {
			this.stream = stream;
		}

		public int read() {
			if (numChars == -1) {
				throw new InputMismatchException();
			}
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = stream.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (numChars <= 0) {
					return -1;
				}
			}
			return buf[curChar++];
		}

		public int readInt() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			int res = 0;
			do {
				if (c < '0' || c > '9') {
					throw new InputMismatchException();
				}
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}

		public boolean isSpaceChar(int c) {
			if (filter != null) {
				return filter.isSpaceChar(c);
			}
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		public interface SpaceCharFilter {
			public boolean isSpaceChar(int ch);
		}
	}
}

 

 

공부해볼 코드

 

/**
 * 출처 : https://www.acmicpc.net/source/16451230
 */

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

public class Main {

    private static final int HOUSE = 1;
    private static final int CHICKEN = 2;

    private static int n;
    private static int m;

    private static Point[] house;
    private static Point[] chick = new Point[13];
    private static Dist[][] distMap;

    private static int numHouse = 0;
    private static int numChicken = 0;

    private static int min = Integer.MAX_VALUE;

    public static void main(String[] args) throws Exception {
        inputData();
        solve();
    }

    private static void inputData() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = s2i(st.nextToken());
        m = s2i(st.nextToken());

        house = new Point[2*n];

        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                int tmp = s2i(st.nextToken());

                if (tmp == HOUSE) {
                    house[numHouse++] = new Point(i, j);
                } else if (tmp == CHICKEN) {
                    chick[numChicken++] = new Point(i, j);
                }
            }
        }


    }

    private static void solve() {
        recordDistHouseFromChicken();
        dfs(distMap, 0, 0, new boolean[numChicken]);
        System.out.println(min);
    }

    private static void recordDistHouseFromChicken() {
        distMap = new Dist[numHouse][numChicken];

        for (int i = 0; i < numHouse; i++) {
            for (int j = 0; j < numChicken; j++) {
                distMap[i][j] = new Dist(j, calculateChickDist(i, j));
            }

            Arrays.parallelSort(distMap[i]);
        }
    }

    private static void dfs(Dist[][] distMap, int cnt, int idx, boolean[] checkChick) {
        if (cnt == m) {
            int sum = 0;
            for (Dist[] dists : distMap) {
                for (Dist dist : dists) {
                    if (checkChick[dist.idxChick]) {
                        sum += dist.dist;
                        break;
                    }
                }
            }

            if (sum < min) {
                min = sum;
            }
            return;
        }

        if (idx == numChicken) {
            return;
        }

        checkChick[idx] = true;
        dfs(distMap, cnt + 1, idx + 1, checkChick);
        checkChick[idx] = false;
        dfs(distMap, cnt, idx + 1, checkChick);
    }


    private static int calculateChickDist(int idxHouse, int idxChick) {
        return Math.abs(house[idxHouse].r - chick[idxChick].r) + Math.abs(house[idxHouse].c - chick[idxChick].c);
    }

    private static int s2i(String s) {
        return Integer.parseInt(s);
    }
}

class Point {
    int r, c;

    Point(int r, int c) {
        this.r = r;
        this.c = c;
    }
}

class Dist implements Comparable<Dist> {
    int idxChick, dist;

    Dist(int idxChick, int dist) {
        this.idxChick = idxChick;
        this.dist = dist;
    }

    @Override
    public int compareTo(Dist d) {
        if (this.dist == d.dist) {
            return Integer.compare(this.idxChick, d.idxChick);
        }
        return Integer.compare(this.dist, d.dist);
    }
}