이번 장에서는 DFS 알고리즘을 사용하여 활용 문제를 해결해본다.
모든 코드는 깃허브 (링크)의 테스트 코드로 정리해두었다.
합이 같은 부분집합(아마존 기출)
N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나누었을 때 두 부분집합의 원소의 합이 서로 같은 경우가 존재하면 “YES"를 출력하고,
그렇지 않으면 ”NO"를 출력하는 프로그램을 작성하세요.
둘로 나뉘는 두 부분집합은 서로소 집합이며, 두 부분집합을 합하면 입력으로 주어진 원래의 집합이 되어야 합니다.
예를 들어 {1, 3, 5, 6, 7, 10}이 입력되면 {1, 3, 5, 7} = {6, 10} 으로 두 부분집합의 합이 16으로 같은 경우가 존재하는 것을 알 수 있다.
- 입력설명
첫 번째 줄에 자연수 N(1<=N<=10)이 주어집니다.
두 번째 줄에 집합의 원소 N개가 주어진다. 각 원소는 중복되지 않는다. - 출력설명
첫 번째 줄에 “YES" 또는 ”NO"를 출력한다. - 입력예제 1
6
1 3 5 6 7 10 - 출력예제 1
YES
public class SameSumSubset {
private static final int[] NUMBERS = {1, 3, 5, 6, 7, 10};
private static final int TOTAL_SUM = Arrays.stream(NUMBERS).sum();
private boolean isEnd = false;
private String answer = "NO";
public void solution1(int level, int sum) {
// 이미 조건에 부합하는 부분집합을 찾은 경우 더이상 로직을 타지않도록 return 처리한다.
if (isEnd == Boolean.TRUE) {
return;
}
// 최대합을 2로 나눈 경우가 sum보다 큰 경우는 끝까지 진행하더라도 문제에서 원하는 부분집합일 수 없으므로
// 더이상 로직을 타지 않도록 return 처리한다.
if (sum > TOTAL_SUM / 2) {
return;
}
if (level == NUMBERS.length) {
if (TOTAL_SUM / 2 == sum) {
answer = "YES";
isEnd = true;
}
} else {
// 포함되는 경우
solution1(level + 1, sum + NUMBERS[level]);
// 포함되지 않는 경우
solution1(level + 1, sum);
}
}
@Test
@DisplayName("합이 같은 부분집합(DFS)")
public void main() {
String expectedAnswer = "YES";
solution1(0, 0);
assertEquals(expectedAnswer, answer);
}
}바둑이 승차
철수는 그의 바둑이들을 데리고 시장에 가려고 한다. 그런데 그의 트럭은 C킬로그램 넘게 태울수가 없다.
철수는 C를 넘지 않으면서 그의 바둑이들을 가장 무겁게 태우고 싶다.
N마리의 바둑이와 각 바둑이의 무게 W가 주어지면, 철수가 트럭에 태울 수 있는 가장 무거운 무게를 구하는 프로그램을 작성하세요.
- 입력설명
첫 번째 줄에 자연수 C(1<=C<=100,000,000)와 N(1<=N<=30)이 주어집니다. 둘째 줄부터 N마리 바둑이의 무게가 주어진다. - 출력설명
첫 번째 줄에 가장 무거운 무게를 출력한다. - 입력예제 1
259 5
81
58
42
33
61 - 출력예제 1
242
public class RidingDog {
private static final int[] DOGS_WEIGHT = {81, 58, 42, 33, 61};
private static final int LIMIT_TOTAL_WEIGHT = 259;
private static int answer = Integer.MIN_VALUE;
public void solution1(int level, int sum) {
if (level == DOGS_WEIGHT.length) {
answer = LIMIT_TOTAL_WEIGHT >= sum ? Math.max(answer, sum) : answer;
} else {
// 해당 인덱스의 바둑이가 승차하는 경우
solution1(level + 1, sum + DOGS_WEIGHT[level]);
// 해당 인덱스의 바둑이가 승차하지 않는 경우
solution1(level + 1, sum);
}
}
@Test
@DisplayName("바둑이 승차(DFS)")
public void main() {
int expectedAnswer = 242;
solution1(0, 0);
Assertions.assertEquals(expectedAnswer, answer);
}
}최대점수 구하기
이번 정보올림피아드대회에서 좋은 성적을 내기 위하여 현수는 선생님이 주신 N개의 문제를 풀려고 합니다.
각 문제는 그것을 풀었을 때 얻는 점수와 푸는데 걸리는 시간이 주어지게 됩니다.
제한시간 M안에 N개의 문제 중 최대점수를 얻을 수 있도록 해야 합니다.
(해당문제는 해당시간이 걸리면 푸는 걸로 간주한다, 한 유형당 한개만 풀 수 있습니다.)
- 입력설명
첫 번째 줄에 문제의 개수N(1<=N<=20)과 제한 시간 M(10<=M<=300)이 주어집니다.
두 번째 줄부터 N줄에 걸쳐 문제를 풀었을 때의 점수와 푸는데 걸리는 시간이 주어집니다. - 출력설명
첫 번째 줄에 제한 시간안에 얻을 수 있는 최대 점수를 출력합니다. - 입력예제 1
5 20
10 5
25 12
15 8
6 3
7 4 - 출력예제 1
41
public class MaxScore {
private static final int PROBLEM_COUNT = 5;
private static final int LIMIT_SECOND = 20;
private static final int[][] PROBLEMS = {
{10, 5}, {25, 12}, {15, 8}, {6, 3}, {7, 4}
};
private int maxScore = Integer.MIN_VALUE;
public void solution1(int level, int score, int second) {
if (second > LIMIT_SECOND) {
return;
}
if (level == PROBLEM_COUNT) {
maxScore = Math.max(maxScore, score);
} else {
// 문제를 푸는 경우
solution1(level + 1,
score + PROBLEMS[level][0],
second + PROBLEMS[level][1]);
// 문제를 풀지 않는 경우
solution1(level + 1, score, second);
}
}
@Test
@DisplayName("최대점수 구하기(DFS")
public void main() {
int expectedAnswer = 41;
solution1(0, 0, 0);
assertEquals(expectedAnswer, maxScore);
}
}중복순열 구하기
1부터 N까지 번호가 적힌 구슬이 있습니다.
이 중 중복을 허락하여 M번을 뽑아 일렬로 나열하는 방법을 모두 출력합니다.
- 입력설명
첫 번째 줄에 자연수 N(3<=N<=10)과 M(2<=M<=N) 이 주어집니다. - 출력설명
첫 번째 줄에 결과를 출력합니다.
출력순서는 사전순으로 오름차순으로 출력합니다. - 입력예제 1
3 2 - 출력예제 1
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3
public class DuplicatedNumbers {
private static final int NUMBERS = 3;
private static final int COUNT = 2;
private static final Integer[][] EXPECTED_ANSWER = {
{1, 1}, {1, 2}, {1, 3},
{2, 1}, {2, 2}, {2, 3},
{3, 1}, {3, 2}, {3, 3}
};
private final List<Integer[]> numbersOfCases = new ArrayList<>();
public void solution1(int level, Integer[] tempNumbers) {
if (level == COUNT) {
numbersOfCases.add(tempNumbers.clone());
} else {
for (int i = 1; i <= NUMBERS; i++) {
if (Objects.isNull(tempNumbers)) {
tempNumbers = new Integer[COUNT];
}
tempNumbers[level] = i;
solution1(level + 1, tempNumbers);
}
}
}
@Test
@DisplayName("중복가능한 순열 구하기")
public void main() {
solution1(0, null);
for (int i = 0; i < NUMBERS * NUMBERS; i++) {
assertArrayEquals(EXPECTED_ANSWER[i], (Integer[]) numbersOfCases.toArray()[i]);
}
}
}동전교환
다음과 같이 여러 단위의 동전들이 주어져 있을 때 거스름 돈을 가장 적은 수의 동전으로 교환 해주려면 어떻게 주면 되는가?
각 단위의 동전은 무한정 쓸 수 있다.
- 입력설명
첫 번째 줄에는 동전의 종류개수 N(1<=N<=12)이 주어진다.
두 번째 줄에는 N개의 동전의 종 류가 주어지고, 그 다음줄에 거슬러 줄 금액 M(1<=M<=500)이 주어진다.
각 동전의 종류는 100원을 넘지 않는다. - 출력설명
첫 번째 줄에 거슬러 줄 동전의 최소개수를 출력한다. - 입력예제 1
3
1 2 5
15 - 출력예제 1
3
public class ExchangeCoin {
private static final int[] COINS = {1, 2, 5};
private static final int TARGET_COST = 15;
private static final int EXPECTED_ANSWER = 3;
private int minCoins = Integer.MAX_VALUE;
// DFS를 통한 풀이
public void solution1(int level, int sum) {
if (sum == TARGET_COST) {
minCoins = Math.min(minCoins, level);
} else if (sum < TARGET_COST && level < minCoins) {
for (int coin : COINS) {
if (sum + coin <= TARGET_COST) {
solution1(level + 1, sum + coin);
}
}
}
}
@Test
@DisplayName("동전교환")
public void main() {
solution1(0, 0);
assertEquals(EXPECTED_ANSWER, minCoins);
}
}순열 구하기
10이하의 N개의 자연수가 주어지면 이 중 M개를 뽑아 일렬로 나열하는 방법을 모두 출력합니다.
- 입력설명
첫 번째 줄에 자연수 N(3<=N<=10)과 M(2<=M<=N) 이 주어집니다. 두 번째 줄에 N개의 자연수가 오름차순으로 주어집니다. - 출력설명
첫 번째 줄에 결과를 출력합니다.
출력순서는 사전순으로 오름차순으로 출력합니다. - 입력예제 1
3 2
3 6 9 - 출력예제 1
3 6
3 9
6 3
6 9
9 3
9 6
public class Permutation {
private static final int[] NUMBERS = {3, 6, 9};
private static final int COUNT = 2;
private static final int[][] EXPECTED_ANSWER = {
{3, 6}, {3, 9},
{6, 3}, {6, 9},
{9, 3}, {9, 6}
};
private final List<int[]> answer = new ArrayList<>();
private final int[] checkArray = new int[NUMBERS.length];
public void solution1(int level, int[] tempNumbers) {
if (level == COUNT) {
answer.add(tempNumbers.clone());
} else {
for (int i = 0; i < NUMBERS.length; i++) {
if (Objects.isNull(tempNumbers)) {
tempNumbers = new int[2];
}
if (checkArray[i] == 0) {
checkArray[i] = 1;
tempNumbers[level] = NUMBERS[i];
solution1(level + 1, tempNumbers);
checkArray[i] = 0;
}
}
}
}
@Test
@DisplayName("순열 구하기")
public void main() {
solution1(0, null);
for (int i = 0; i < EXPECTED_ANSWER.length; i++) {
assertArrayEquals(EXPECTED_ANSWER[i], answer.get(i));
}
}
}조합의 경우의 수(메모이제이션)
다음 공식을 사용하여 재귀를 이용해 조합수를 구해주는 프로그램을 작성하세요.
nCr = n-1Cr-1 + n-1Cr
- 입력설명
첫째 줄에 자연수 n(3<=n<=33)과 r(0<=r<=n)이 입력됩니다. - 출력설명
첫째 줄에 조합수를 출력합니다. - 입력예제 1
5 3 - 출력예제 1
10 - 입력예제
2
33 19 - 출력예제 2
818809200
public class NumberOfCombinations {
// 자연수 n이 33까지 들어올 수 있으므로 최대 33개의 수가 저장될 수 있도록 한다.
private final int[][] memory = new int[34][34];
public int solution1(int n, int r) {
if (memory[n][r] > 0) {
return memory[n][r];
} else {
if (n == r || r == 0) {
return 1;
} else {
return memory[n][r] = solution1(n - 1, r - 1) + solution1(n - 1, r);
}
}
}
@Test
@DisplayName("조합의 경우의 수(메모이제이션")
public void main() {
int expectedAnswer1 = 10;
int answer1 = solution1(5, 3);
assertEquals(expectedAnswer1, answer1);
int expectedAnswer2 = 818809200;
int answer2 = solution1(33, 19);
assertEquals(expectedAnswer2, answer2);
}
}수열 추측하기
가장 윗줄에 1부터 N까지의 숫자가 한 개씩 적혀 있다.
그리고 둘째 줄부터 차례대로 파스칼 의 삼각형처럼 위의 두개를 더한 값이 저장되게 된다.
예를 들어 N이 4 이고 가장 윗 줄에 3 1 2 4 가 있다고 했을 때, 다음과 같은 삼각형이 그려진다.
3 1 2 4
4 3 6
7 9
16
N과 가장 밑에 있는 숫자가 주어져 있을 때 가장 윗줄에 있는 숫자를 구하는 프로그램을 작성하시오.
단, 답이 여러가지가 나오는 경우에는 사전순으로 가장 앞에 오는 것을 출력하여야 한다.
- 입력설명
첫째 줄에 두개의 정수 N(1≤N≤10)과 F가 주어진다.
N은 가장 윗줄에 있는 숫자의 개수를 의미하며 F는 가장 밑에 줄에 있는 수로 1,000,000 이하이다. - 출력설명
첫째 줄에 삼각형에서 가장 위에 들어갈 N개의 숫자를 빈 칸을 사이에 두고 출력한다.
답이 존재 하지않는 경우는 입력으로 주어지지 않는다. - 입력예제 1
4
16 - 출력예제 1
3 1 2 4 - 해설
n이 5인 경우 가장 위의 숫자는 아래와 같은 규칙을 따른다.
4C0 4C1 4C2 4C3 4C4
n이 10인 경우 가장 위의 숫자는 아래와 같은 규칙을 따른다.
9C0 9C1 9C2 9C3 9C4 9C5 9C6 9C7 9C8 9C9
HARD 다시 풀어볼 것!
public class GuessCombinations {
// 삼각형 최상단부의 숫자의 수
private static final int NUMBER_COUNT = 4;
// 삼각형의 최하단부의 숫자
private static final int FINAL_NUMBER = 16;
// NUMBER_COUNT = 4인 경우
// 3C0 3C1 3C2 3C3이 저장될 배열
private final int[] combinations = new int[NUMBER_COUNT];
private final int[] permutations = new int[NUMBER_COUNT];
private int[] answer = new int[NUMBER_COUNT];
// Index 기준으로 찾는 것이 아니라 1 ~ N까지이므로 N + 1의 크기를 할당한다.
// Index = 0 의 위치는 사용하지 않는다.
private final int[] checkArray = new int[NUMBER_COUNT + 1];
// 메모이제이션을 위한 배열
private final int[][] memory = new int[NUMBER_COUNT + 1][NUMBER_COUNT + 1];
private boolean isEnd = false;
// nCr
public int makeCombination(int n, int r) {
if (memory[n][r] > 0) {
return memory[n][r];
} else if (n == r || r == 0) {
return 1;
} else {
return memory[n][r] = makeCombination(n - 1, r - 1) + makeCombination(n - 1, r);
}
}
public void solution1(int level, int sum) {
if (isEnd) return;
if (level == NUMBER_COUNT) {
if (sum == FINAL_NUMBER) {
isEnd = true;
answer = permutations.clone();
}
} else {
for (int i = 1; i <= NUMBER_COUNT; i++) {
if (checkArray[i] == 0) {
checkArray[i] = 1;
permutations[level] = i;
solution1(level + 1, sum + (combinations[level] * permutations[level]));
checkArray[i] = 0;
}
}
}
}
@Test
@DisplayName("수열 추측하기")
public void main() {
for (int i = 0; i < NUMBER_COUNT; i++) {
combinations[i] = makeCombination(NUMBER_COUNT - 1, i);
}
int[] expectedAnswer = {3, 1, 2, 4};
solution1(0, 0);
assertArrayEquals(expectedAnswer, answer);
}
}조합 구하기
1부터 N까지 번호가 적힌 구슬이 있습니다.이중 M개를 뽑는 방법의 수를 출력하는 프로그램을 작성하세요.
- 입력설명
첫 번째 줄에 자연수 N(3<=N<=10)과 M(2<=M<=N) 이 주어집니다. - 출력설명
첫 번째 줄에 결과를 출력합니다.
출력순서는 사전순으로 오름차순으로 출력합니다. - 입력예제 1
4 2 - 출력예제 1
1 2
1 3
1 4
2 3
2 4
3 4
public class GetCombinations {
private static final int MAX_NUMBER = 4;
private static final int NUMBER_COUNT = 2;
private static final int[][] EXPECTED_ANSWER = {
{1, 2}, {1, 3}, {1, 4},
{2, 3}, {2, 4}, {3, 4}
};
List<int[]> answer = new ArrayList<>();
private final int[] tempCombination = new int[NUMBER_COUNT];
public void solution1(int level, int startNumber) {
if (level == NUMBER_COUNT) {
answer.add(tempCombination.clone());
} else {
for (int i = startNumber; i <= MAX_NUMBER; i++) {
tempCombination[level] = i;
solution1(level + 1, i + 1);
}
}
}
@Test
@DisplayName("조합 구하기")
public void main() {
solution1(0, 1);
assertArrayEquals(EXPECTED_ANSWER, answer.toArray());
}
}미로탐색
7*7 격자판 미로를 탈출하는 경로의 가지수를 출력하는 프로그램을 작성하세요.
출발점은 격 자의 (1, 1) 좌표이고, 탈출 도착점은 (7, 7)좌표이다.
격자판의 1은 벽이고, 0은 통로이다. 격 자판의 움직임은 상하좌우로만 움직인다. 미로가 다음과 같다면
S 0 0 0 0 0 0
0 1 1 1 1 1 0
0 0 0 1 0 0 0
1 1 0 1 0 1 1
1 1 0 0 0 0 1
1 1 0 1 1 0 0
1 0 0 0 0 0 E
위의 지도에서 출발점에서 도착점까지 갈 수 있는 방법의 수는 8가지이다.
- 입력설명
7*7 격자판의 정보가 주어집니다. - 출력설명
첫 번째 줄에 경로의 가지수를 출력한다. - 입력예제 1
0 0 0 0 0 0 0
0 1 1 1 1 1 0
0 0 0 1 0 0 0
1 1 0 1 0 1 1
1 1 0 0 0 0 1
1 1 0 1 1 0 0
1 0 0 0 0 0 0 - 출력예제 1
8
public class ExploringMaze {
private static final int[][] MAZE = {
{0, 0, 0, 0, 0, 0, 0},
{0, 1, 1, 1, 1, 1, 0},
{0, 0, 0, 1, 0, 0, 0},
{1, 1, 0, 1, 0, 1, 1},
{1, 1, 0, 0, 0, 0, 1},
{1, 1, 0, 1, 1, 0, 0},
{1, 0, 0, 0, 0, 0, 0}
};
// 이동할 수 있는 방향 상하좌우
private static final int[][] DIRECTIONS = {
// 좌 상 우 하
{-1, 0}, {0, 1}, {1, 0}, {0, -1}
};
private static final int EXPECTED_ANSWER = 8;
private int answer = 0;
private static final int[][] checkArray = new int[7][7];
public void solution1(int x, int y) {
if (x == 6 && y == 6) {
answer++;
} else {
for (int[] direction : DIRECTIONS) {
int nextX = x + direction[0];
int nextY = y + direction[1];
if (nextX >= 0 && nextX <= 6
&& nextY >= 0 && nextY <= 6
&& checkArray[nextX][nextY] == 0
&& MAZE[nextX][nextY] == 0) {
checkArray[nextX][nextY] = 1;
solution1(nextX, nextY);
checkArray[nextX][nextY] = 0;
}
}
}
}
@Test
@DisplayName("미로탐색(DFS)")
public void main() {
// 시작위치는 항상 탐색하므로 시작과 동시에 탐색완료 처리한다.
checkArray[0][0] = 1;
solution1(0, 0);
assertEquals(EXPECTED_ANSWER, answer);
}
}섬나라 아일랜드
N*N의 섬나라 아일랜드의 지도가 격자판의 정보로 주어집니다.
각 섬은 1로 표시되어 상하좌 우와 대각선으로 연결되어 있으며, 0은 바다입니다.
섬나라 아일랜드에 몇 개의 섬이 있는지 구하는 프로그램을 작성하세요.
1 1 0 0 0 1 0
0 1 1 0 1 1 0
0 1 0 0 0 0 0
0 0 0 1 0 1 1
1 1 0 1 1 0 0
1 0 0 0 1 0 0
1 0 1 0 1 0 0
만약 위와 같다면 섬의 개수는 5개입니다.
- 입력설명
첫 번째 줄에 자연수 N(3<=N<=20)이 주어집니다. 두 번째 줄부터 격자판 정보가 주어진다. - 출력설명
첫 번째 줄에 섬의 개수를 출력한다. - 입력예제 1
7
1 1 0 0 0 1 0
0 1 1 0 1 1 0
0 1 0 0 0 0 0
0 0 0 1 0 1 1
1 1 0 1 1 0 0
1 0 0 0 1 0 0
1 0 1 0 1 0 0 - 출력예제 1
5
public class IslandDFS {
private static final int SIZE = 7;
private static final int[][] MAPS = {
{1, 1, 0, 0, 0, 1, 0},
{0, 1, 1, 0, 1, 1, 0},
{0, 1, 0, 0, 0, 0, 0},
{0, 0, 0, 1, 0, 1, 1},
{1, 1, 0, 1, 1, 0, 0},
{1, 0, 0, 0, 1, 0, 0},
{1, 0, 1, 0, 1, 0, 0}
};
private static final int[][] DIRECTIONS = {
// 좌상 // 좌하 // 우상 // 우하
{-1, -1}, {-1, 1}, {1, -1}, {1, 1},
// 좌 우 상 하
{-1, 0}, {1, 0}, {0, -1}, {0, 1}
};
public void solution1(int x, int y) {
for (int[] direction : DIRECTIONS) {
int nextX = x + direction[0];
int nextY = y + direction[1];
if (nextX >= 0 && nextX < SIZE
&& nextY >= 0 && nextY < SIZE
&& MAPS[nextX][nextY] == 1) {
MAPS[nextX][nextY] = 0;
solution1(nextX, nextY);
}
}
}
@Test
@DisplayName("섬나라 아일랜드(DFS)")
public void main() {
int expectedAnswer = 5;
int answer = 0;
for (int i = 0; i < SIZE; i++) {
for (int j = 0; j < SIZE; j++) {
if (MAPS[i][j] == 1) {
answer++;
MAPS[i][j] = 0;
solution1(i, j);
}
}
}
assertEquals(expectedAnswer, answer);
}
}피자 배달 거리(삼성 기출)
N×N 크기의 도시지도가 있습니다. 도시지도는 1×1크기의 격자칸으로 이루어져 있습니다.
각 격자칸에는 0은 빈칸, 1은 집, 2는 피자집으로 표현됩니다. 각 격자칸은 좌표(행번호, 열 번호) 로 표현됩니다.
행번호는 1번부터 N번까지이고, 열 번호도 1부터 N까지입니다.
도시에는 각 집마다 “피자배달거리”가 았는데 각 집의 피자배달거리는 해당 집과 도시의 존재 하는 피자집들과의 거리 중 최소값을 해당 집의 “피자배달거리”라고 한다.
집과 피자집의 피자배달거리는 |x1-x2|+|y1-y2| 이다. 예를 들어, 도시의 지도가 아래와 같다면
0 1 0 0
0 0 2 1
0 0 1 0
1 2 0 2
(1, 2)에 있는 집과 (2, 3)에 있는 피자집과의 피자 배달 거리는 |1-2| + |2-3| = 2가 된다.
최근 도시가 불경기에 접어들어 우후죽순 생겼던 피자집들이 파산하고 있습니다.
도시 시장은 도시에 있는 피자집 중 M개만 살리고 나머지는 보조금을 주고 폐업시키려고 합니다.
시장은 살리고자 하는 피자집 M개를 선택하는 기준으로 도시의 피자배달거리가 최소가 되는 M개의 피자집을 선택하려고 합니다.
도시의 피자 배달 거리는 각 집들의 피자 배달 거리를 합한 것을 말합니다.
- 입력설명
첫째 줄에 N(2 ≤ N ≤ 50)과 M(1 ≤ M ≤ 12)이 주어진다. 둘째 줄부터 도시 정보가 입력된다. - 출력설명
첫째 줄에 M개의 피자집이 선택되었을 때 도시의 최소 피자배달거리를 출력한다. - 입력예제 1
4 4
0 1 2 0
1 0 2 1
0 2 1 2
2 0 1 2 - 출력예제 1
6
public class PizzaDeliveryDistance {
static class Point {
int x;
int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
public int getDistance(Point a) {
return Math.abs(this.x - a.x) + Math.abs(this.y - a.y);
}
}
private static final int SIZE = 4;
private static final int[][] MAPS = {
{0, 1, 2, 0},
{1, 0, 2, 1},
{0, 2, 1, 2},
{2, 0, 1, 2}
};
private final List<Point> houseList = new ArrayList<>();
private final List<Point> pizzaList = new ArrayList<>();
private final int[] pizzaCombination = new int[SIZE];
private int answer = Integer.MAX_VALUE;
public void solution(int level, int startIndex) {
if (level == SIZE) {
int sum = 0;
for (Point house : houseList) {
int minDistance = Integer.MAX_VALUE;
for (int i : pizzaCombination) {
minDistance = Math.min(minDistance, house.getDistance(pizzaList.get(i)));
}
sum += minDistance;
}
answer = Math.min(answer, sum);
} else {
for (int i = startIndex; i < pizzaList.size(); i++) {
pizzaCombination[level] = i;
solution(level + 1, startIndex + 1);
}
}
}
@Test
@DisplayName("피자 배달 거리(DFS)")
public void main() {
for (int i = 0; i < SIZE; i++) {
for (int j = 0; j < SIZE; j++) {
if (MAPS[i][j] == 1) {
houseList.add(new Point(i, j));
} else if (MAPS[i][j] == 2) {
pizzaList.add(new Point(i, j));
}
}
}
solution(0, 0);
Assertions.assertEquals(6, answer);
}
}'Algorithm' 카테고리의 다른 글
| [Algorithm] Dynamic Programming (0) | 2022.03.04 |
|---|---|
| [Algorithm] BFS 활용 (0) | 2022.03.01 |
| [Algorithm] Graph (0) | 2022.02.28 |
| [Algorithm] DFS 원리 (0) | 2022.02.28 |
| [Algorithm] DFS & BFS 기본문제 (0) | 2022.02.28 |
