import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/*
BAEKJOON 15686 치킨 배달
https://www.acmicpc.net/problem/15686
*/
public class Main {
static final int EMPTY = 0;
static final int HOUSE = 1;
static final int CHICKEN = 2;
static int[][] map;
static int n;
static int m;
static int result = Integer.MAX_VALUE;
static List<Position> chickenPos = new ArrayList<>();
static List<Position> housePos = new ArrayList<>();
static class Position {
public int x;
public int y;
public Position(int x, int y) {
this.x = x;
this.y = y;
}
}
static void calculateChickenDistance(List<Position> selectedChickens) {
int cityChickenSum = 0;
for (Position house : housePos) {
int houseChickenMin = Integer.MAX_VALUE;
for (Position chicken : selectedChickens) {
houseChickenMin = Math.min(houseChickenMin, Math.abs(house.x - chicken.x) + Math.abs(house.y - chicken.y));
}
cityChickenSum += houseChickenMin;
}
result = Math.min(result, cityChickenSum);
}
static void generateCombinations(int start, List<Position> selectedChickens) {
if (selectedChickens.size() == m) {
calculateChickenDistance(selectedChickens);
return;
}
for (int i = start; i < chickenPos.size(); i++) {
selectedChickens.add(chickenPos.get(i));
generateCombinations(i + 1, selectedChickens);
selectedChickens.remove(selectedChickens.size() - 1);
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] NM = br.readLine().split(" ");
n = Integer.parseInt(NM[0]);
m = Integer.parseInt(NM[1]);
map = new int[n][n];
for (int i = 0; i < n; i++) {
int[] line = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
for (int k = 0; k < line.length; k++) {
map[i][k] = line[k];
if (line[k] == CHICKEN) {
chickenPos.add(new Position(k, i));
} else if (line[k] == HOUSE) {
housePos.add(new Position(k, i));
}
}
}
generateCombinations(0, new ArrayList<>());
System.out.println(result);
}
}
import java.io.ByteArrayInputStream;
import java.io.ByteArrayOutputStream;
import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.PrintStream;
import java.lang.reflect.Field;
import java.lang.reflect.Modifier;
import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.TimeoutException;
/**
* 이 테스트 코드는 <a href="https://github.com/PENEKhun/Baekjoon-java-starter">Baekjoon-java-starter</a>를 사용하여
* 생성되었습니다.
*
* @author PENEKhun
*/
public class TestHelper {
private static final Map<Field, byte[]> initialStates = new HashMap<>();
private static final int timeLimit = 2;
public static void main(String[] args) {
captureInitialState();
TestCase[] testCases = new TestCase[] {
new TestCase(
// input
"""
5 3
0 0 1 0 0
0 0 2 0 1
0 1 2 0 0
0 0 1 0 0
0 0 0 0 2
""",
// output
"""
5
"""),
new TestCase(
// input
"""
5 2
0 2 0 1 0
1 0 1 0 0
0 0 0 0 0
2 0 0 1 1
2 2 0 1 2
""",
// output
"""
10
"""),
new TestCase(
// input
"""
5 1
1 2 0 0 0
1 2 0 0 0
1 2 0 0 0
1 2 0 0 0
1 2 0 0 0
""",
// output
"""
11
"""),
new TestCase(
// input
"""
5 1
1 2 0 2 1
1 2 0 2 1
1 2 0 2 1
1 2 0 2 1
1 2 0 2 1
""",
// output
"""
32
"""),
};
int passedCases = runTestCases(testCases);
printSummary(passedCases, testCases.length);
}
private static int runTestCases(TestCase[] testCases) {
int passedCases = 0;
for (int i = 0; i < testCases.length; i++) {
resetToInitialState();
if (runSingleTestCase(testCases[i], i + 1)) {
passedCases++;
}
}
return passedCases;
}
private static boolean runSingleTestCase(TestCase testCase, int caseNumber) {
ByteArrayOutputStream outputStream = new ByteArrayOutputStream();
PrintStream originalOut = System.out;
setupStreams(testCase.input, outputStream);
ExecutorService executor = Executors.newSingleThreadExecutor();
Future<?> future = submitTask(executor);
boolean testCaseException = false;
try {
future.get(timeLimit, TimeUnit.SECONDS);
} catch (TimeoutException e) {
handleException(originalOut, caseNumber, testCase, "시간 초과 발생", e);
testCaseException = true;
} catch (InterruptedException | ExecutionException e) {
handleException(originalOut, caseNumber, testCase, "Main() Exception 발생", e);
testCaseException = true;
} finally {
executor.shutdown();
}
if (!testCaseException) {
return compareOutput(testCase, caseNumber, outputStream.toString(), originalOut);
}
return false;
}
private static Future<?> submitTask(ExecutorService executor) {
return executor.submit(() -> {
try {
Main.main(new String[0]);
} catch (Exception e) {
throw new RuntimeException(e);
}
});
}
private static void setupStreams(String input, ByteArrayOutputStream outputStream) {
System.setOut(new PrintStream(outputStream));
System.setIn(new ByteArrayInputStream(input.getBytes()));
}
private static boolean compareOutput(TestCase testCase, int caseNumber, String output, PrintStream originalOut) {
System.setOut(originalOut);
String actualOutput = removeTrailingSpaces(output);
String expectedOutput = testCase.expectedOutput.stripTrailing();
if (actualOutput.equals(expectedOutput)) {
return true;
} else {
printFail(caseNumber, testCase, red("[실제 값]\n%s\n\n출력 값이 기대한 값과 다릅니다.").formatted(actualOutput));
return false;
}
}
private static String removeTrailingSpaces(String input) {
String[] lines = input.split("\n");
StringBuilder result = new StringBuilder();
for (String line : lines) {
result.append(line.stripTrailing()).append("\n");
}
if (!result.isEmpty()) {
result.setLength(result.length() - 1);
}
return result.toString();
}
private static void handleException(PrintStream originalOut, int caseNumber, TestCase testCase, String message, Exception e) {
System.setOut(originalOut);
printFail(caseNumber, testCase, message);
e.printStackTrace(originalOut);
}
private static void captureInitialState() {
try {
Field[] fields = Main.class.getDeclaredFields();
for (Field field : fields) {
if (Modifier.isStatic(field.getModifiers())) {
field.setAccessible(true);
Object fieldValue = field.get(null);
byte[] serializedField = SerializationUtils.serialize(fieldValue);
initialStates.put(field, serializedField);
}
}
} catch (Exception e) {
System.out.println(red("Main 클래스에 접근할 수 없습니다."));
}
}
private static void resetToInitialState() {
try {
for (Map.Entry<Field, byte[]> entry : initialStates.entrySet()) {
Field field = entry.getKey();
Object originalState = SerializationUtils.deserialize(entry.getValue());
field.setAccessible(true);
field.set(null, originalState);
}
} catch (Exception e) {
System.out.println(red("Main 클래스에 접근할 수 없습니다."));
}
}
private static void printFail(int caseNumber, TestCase testCase, String message) {
System.out.printf("""
====== %s ======
[입력 값]
%s
[기대 값]
%s
""", red(caseNumber + " 번째 케이스 실패"), testCase.input, testCase.expectedOutput);
System.out.println(green(message));
}
private static void printSummary(int passedCases, int totalCases) {
System.out.println("===============");
System.out.println("테스트 완료 (" + passedCases + " / " + totalCases + ")");
if (passedCases == totalCases) {
System.out.println("주어진 케이스에 대해 잘 동작하고 있습니다.");
}
}
private static String red(String message) {
return String.format("\u001B[31m%s\u001B[0m", message);
}
private static String green(String message) {
return String.format("\u001B[32m%s\u001B[0m", message);
}
private static class TestCase {
public final String input;
public final String expectedOutput;
public TestCase(String input, String expectedOutput) {
this.input = input;
this.expectedOutput = expectedOutput;
}
}
public static class SerializationUtils {
public static byte[] serialize(Object obj) throws IOException {
try (ByteArrayOutputStream bos = new ByteArrayOutputStream();
ObjectOutputStream oos = new ObjectOutputStream(bos)) {
oos.writeObject(obj);
return bos.toByteArray();
}
}
public static Object deserialize(byte[] bytes) throws IOException, ClassNotFoundException {
try (ByteArrayInputStream bis = new ByteArrayInputStream(bytes);
ObjectInputStream ois = new ObjectInputStream(bis)) {
return ois.readObject();
}
}
}
}/Users/penekhun/Library/Java/JavaVirtualMachines/openjdk-21.0.1/Contents/Home/bin/java -javaagent:/Applications/IntelliJ IDEA.app/Contents/lib/idea_rt.jar=51631:/Applications/IntelliJ IDEA.app/Contents/bin -Dfile.encoding=UTF-8 -Dsun.stdout.encoding=UTF-8 -Dsun.stderr.encoding=UTF-8 -classpath /Volumes/BackupDrive/JavaAlgorithm/BOJ/p15686/out/production/p15686 TestHelper
Main 클래스에 접근할 수 없습니다.
Main 클래스에 접근할 수 없습니다.
====== 2 번째 케이스 실패 ======
[입력 값]
5 2
0 2 0 1 0
1 0 1 0 0
0 0 0 0 0
2 0 0 1 1
2 2 0 1 2
[기대 값]
10
[실제 값]
5
출력 값이 기대한 값과 다릅니다.
Main 클래스에 접근할 수 없습니다.
====== 3 번째 케이스 실패 ======
[입력 값]
5 1
1 2 0 0 0
1 2 0 0 0
1 2 0 0 0
1 2 0 0 0
1 2 0 0 0
[기대 값]
11
[실제 값]
5
출력 값이 기대한 값과 다릅니다.
Main 클래스에 접근할 수 없습니다.
====== 4 번째 케이스 실패 ======
[입력 값]
5 1
1 2 0 2 1
1 2 0 2 1
1 2 0 2 1
1 2 0 2 1
1 2 0 2 1
[기대 값]
32
[실제 값]
5
출력 값이 기대한 값과 다릅니다.
===============
테스트 완료 (1 / 4)
종료 코드 0(으)로 완료된 프로세스
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent