15686번: 치킨 배달
크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸
www.acmicpc.net
- 코드
실패 코드 : 시간 초과 백트래킹으로 치킨 집의 수가 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);
}
}'algorithm' 카테고리의 다른 글
| [BOJ/JAVA] 백준 14502번 : 연구소 (공부 더 해보기) (0) | 2021.01.24 |
|---|---|
| [BOJ/JAVA] 백준 7579번 : 앱 (0) | 2021.01.24 |
| [BOJ/JAVA] 백준 2573번 : 빙산 (0) | 2021.01.23 |
| [BOJ/JAVA] 백준 1781번 : 컵라면 (0) | 2021.01.22 |
| [BOJ/JAVA] 백준 11000번 : 강의실 배정 (0) | 2021.01.22 |
