8-2. 바둑이 승차(DFS)
문제
이진트리
탐색 순서
sum(81) = sum[0] + array[0] = 0 + 81
sum(139) = sum[81] + array[1] = 81 + 58
sum(181) = sum[139] + array[2] = 139 + 42
sum(214) = sum[181] + array[3] = 181 + 33
sum(275) = sum[214] + array[4] = 214 + 61
sum(275) = sum[275] + array[5] = 275 + 0
sum(214) = sum[214] + array[5] = 214 + 0
sum(242) = sum[181] + array[4] = 181 + 61
sum(242) = sum[242] + array[5] = 242 + 0
sum(181) = sum[181] + array[5] = 181 + 0
sum(172) = sum[139] + array[3] = 139 + 33
sum(233) = sum[172] + array[4] = 172 + 61
sum(233) = sum[233] + array[5] = 233 + 0
sum(172) = sum[172] + array[5] = 172 + 0
sum(200) = sum[139] + array[4] = 139 + 61
sum(200) = sum[200] + array[5] = 200 + 0
sum(139) = sum[139] + array[5] = 139 + 0
sum(123) = sum[81] + array[2] = 81 + 42
sum(156) = sum[123] + array[3] = 123 + 33
sum(217) = sum[156] + array[4] = 156 + 61
sum(217) = sum[217] + array[5] = 217 + 0
sum(156) = sum[156] + array[5] = 156 + 0
sum(184) = sum[123] + array[4] = 123 + 61
sum(184) = sum[184] + array[5] = 184 + 0
sum(123) = sum[123] + array[5] = 123 + 0
sum(114) = sum[81] + array[3] = 81 + 33
sum(175) = sum[114] + array[4] = 114 + 61
sum(175) = sum[175] + array[5] = 175 + 0
sum(114) = sum[114] + array[5] = 114 + 0
sum(142) = sum[81] + array[4] = 81 + 61
sum(142) = sum[142] + array[5] = 142 + 0
sum(81) = sum[81] + array[5] = 81 + 0
sum(58) = sum[0] + array[1] = 0 + 58
sum(100) = sum[58] + array[2] = 58 + 42
sum(133) = sum[100] + array[3] = 100 + 33
sum(194) = sum[133] + array[4] = 133 + 61
sum(194) = sum[194] + array[5] = 194 + 0
sum(133) = sum[133] + array[5] = 133 + 0
sum(161) = sum[100] + array[4] = 100 + 61
sum(161) = sum[161] + array[5] = 161 + 0
sum(100) = sum[100] + array[5] = 100 + 0
sum(91) = sum[58] + array[3] = 58 + 33
sum(152) = sum[91] + array[4] = 91 + 61
sum(152) = sum[152] + array[5] = 152 + 0
sum(91) = sum[91] + array[5] = 91 + 0
sum(119) = sum[58] + array[4] = 58 + 61
sum(119) = sum[119] + array[5] = 119 + 0
sum(58) = sum[58] + array[5] = 58 + 0
sum(42) = sum[0] + array[2] = 0 + 42
sum(75) = sum[42] + array[3] = 42 + 33
sum(136) = sum[75] + array[4] = 75 + 61
sum(136) = sum[136] + array[5] = 136 + 0
sum(75) = sum[75] + array[5] = 75 + 0
sum(103) = sum[42] + array[4] = 42 + 61
sum(103) = sum[103] + array[5] = 103 + 0
sum(42) = sum[42] + array[5] = 42 + 0
sum(33) = sum[0] + array[3] = 0 + 33
sum(94) = sum[33] + array[4] = 33 + 61
sum(94) = sum[94] + array[5] = 94 + 0
sum(33) = sum[33] + array[5] = 33 + 0
sum(61) = sum[0] + array[4] = 0 + 61
sum(61) = sum[61] + array[5] = 61 + 0
sum(0) = sum[0] + array[5] = 0 + 0
package test;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
//백준
public class Main {
static int[] array;
static int[] visited;
static int size;
static int total;
static int re = Integer.MIN_VALUE;
static boolean visit= false;
public static void dfs(int point, int sum) {
int ch = sum;
if(visit) return;
if (sum == total) {
visit=true;
re=sum;
}
if(sum<total&&sum>re) re=sum;
if(sum<total&&point<size) {
System.out.println("sum("+(sum + array[point] )+") = sum["+sum+"] + array["+point+"] = "+ch+" + "+array[point]);
dfs(point+1, sum + array[point]);
dfs(point+1, sum );
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// Queue<Integer> q = new LinkedList<>();
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
total = Integer.parseInt(st.nextToken());
size = Integer.parseInt(st.nextToken());
array = new int[size];
// visited = new int[size];
for (int i = 0; i < size; i++) {
array[i] = Integer.parseInt(br.readLine());
}
dfs(0, 0);
System.out.println(re);
}
}
소스는 문제풀이게 맞게 조건이 들어가 있어서 탐색순서를 건너뛰게끔 되어있다.
더하거나 그렇지 않거나, 2가지 조건에 대해서 복습할 수 있었다.