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가지 조건에 대해서 복습할 수 있었다.