CH08 DFS, BFS 활용
package dfsbfs_new.main1;
import java.util.Scanner;
public class Main {
static int[] numbers;
static int total = 0;
static boolean stopNow = false;
static String answer = "NO";
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int count = scanner.nextInt();
numbers = new int[count];
for (int i = 0; i < count; i++) {
int value = scanner.nextInt();
numbers[i] = value;
total += value;
}
Main main = new Main();
main.DFS(0, 0);
System.out.println(answer);
}
private void DFS(int L, int sum) {
if (sum > total - sum || stopNow) return;
if (L == numbers.length - 1) {
if (total - sum == sum) {
answer = "YES";
stopNow = true;
return;
}
} else {
DFS(L + 1, sum + numbers[L]);
DFS(L + 1, sum);
}
}
}
package dfsbfs_new.main2;
import java.util.Scanner;
public class Main {
static int limit;
static int[] dogs;
static int max = Integer.MIN_VALUE;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
limit = scanner.nextInt();
dogs = new int[scanner.nextInt()];
for (int w = 0; w < dogs.length; w++) {
dogs[w] = scanner.nextInt();
}
Main main = new Main();
main.DFS(0, 0);
System.out.println(max);
}
private void DFS(int L, int sum) {
if (sum > limit) return;
if (L == dogs.length) {
max = Math.max(max, sum);
return;
} else {
DFS(L + 1, sum + dogs[L]);
DFS(L + 1, sum);
}
}
}
package dfsbfs.main3;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
class Problem {
int point;
int time;
public Problem(int point, int time) {
this.point = point;
this.time = time;
}
}
public class Main {
static int count;
static int limit;
static int pointMax = 0;
static List<Problem> problems = new ArrayList<>();
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
count = scanner.nextInt();
limit = scanner.nextInt();
for (int i = 0; i < count; i++) {
problems.add(new Problem(scanner.nextInt(), scanner.nextInt()));
}
Main main = new Main();
main.DFS(0, 0, 0);
System.out.println(pointMax);
}
private void DFS(int index, int pointSum, int timeSum) {
if (timeSum > limit) return;
if (index == count) {
pointMax = Math.max(pointSum, pointMax);
} else {
DFS(index + 1, pointSum + problems.get(index).point, timeSum + problems.get(index).time);
DFS(index + 1, pointSum, timeSum);
}
}
}
package dfsbfs.main4;
import java.util.Scanner;
public class Main {
static int[] pm;
static int n, m;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
m = scanner.nextInt();
pm = new int[m];
Main main = new Main();
main.DFS(0);
}
private void DFS(int L) {
if (L == m) {
for (int x : pm) System.out.print(x + " ");
System.out.println();
} else {
for (int i = 1; i <= n; i++) {
pm[L] = i;
DFS(L + 1);
}
}
}
}
package dfsbfs.main5;
import java.util.Scanner;
public class Main {
static int count;
static int[] coins;
static int target;
static int min = Integer.MAX_VALUE;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
count = scanner.nextInt();
coins = new int[count];
for (int i = count - 1; i >= 0; i--) {
coins[i] = scanner.nextInt();
}
target = scanner.nextInt();
Main main = new Main();
main.DFS(0, 0);
System.out.println(min);
}
private void DFS(int L, int sum) {
if (sum > target || L > min) {
return;
}
if (sum == target) {
min = Math.min(min, L);
return;
} else {
for (int i = 0; i < count; i++) {
DFS(L + 1, sum + coins[i]);
}
}
}
}
package dfsbfs.main6;
import java.util.Scanner;
public class Main {
static int totalCount;
static int selectCount;
static int[] numbers;
static int[] pm;
static int[] check;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
totalCount = scanner.nextInt();
selectCount = scanner.nextInt();
numbers = new int[totalCount];
for (int i = 0; i < totalCount; i++) {
numbers[i] = scanner.nextInt();
}
pm = new int[selectCount];
check = new int[totalCount];
Main main = new Main();
main.DFS(0);
}
private void DFS(int L) {
if (L > selectCount) return;
if (L == selectCount) {
for (int number : pm) System.out.print(number + " ");
System.out.println();
} else {
for (int i = 0; i < totalCount; i++) {
if (check[i] == 0) {
check[i] = 1;
pm[L] = numbers[i];
DFS(L + 1);
check[i] = 0;
}
}
}
}
}
package dfsbfs.main7;
import java.util.Scanner;
public class Main {
int[][] dy = new int[35][35];
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int r = scanner.nextInt();
Main main = new Main();
System.out.println(main.DFS(n, r));
}
private int DFS(int n, int r) {
if (dy[n][r] != 0) return dy[n][r];
if (n == r || r == 0) {
return 1;
} else {
dy[n][r] = DFS(n - 1, r - 1) + DFS(n - 1, r);
return dy[n][r];
}
}
}
package dfsbfs.main10;
import java.util.Scanner;
public class Main {
static int[] dx = {-1, 0, 1, 0};
static int[] dy = {0, 1, 0, -1};
static int[][] board;
static int answer = 0;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
board = new int[8][8];
for (int i = 1; i <= 7; i++) {
for (int j = 1; j <= 7; j++) {
board[i][j] = scanner.nextInt();
}
}
board[1][1] = 1;
Main main = new Main();
main.DFS(1, 1);
System.out.println(answer);
}
private void DFS(int x, int y) {
if (x == 7 && y == 7) {
answer++;
} else {
for (int i = 0; i < 4; i++) {
int nextX = x + dx[i];
int nextY = y + dy[i];
if (nextX >= 1 && nextX <= 7 && nextY >= 1 && nextY <= 7 && board[nextX][nextY] == 0) {
board[nextX][nextY] = 1;
DFS(nextX, nextY);
board[nextX][nextY] = 0;
}
}
}
}
}
package dfsbfs.main11;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
class Point {
int x;
int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
public class Main {
static int[] dx = {-1, 0, 1, 0};
static int[] dy = {0, 1, 0, -1};
static int[][] board;
static int[][] dis;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
board = new int[8][8];
dis = new int[8][8];
for (int i = 1; i <= 7; i++) {
for (int j = 1; j <= 7; j++) {
board[i][j] = scanner.nextInt();
}
}
Main main = new Main();
main.BFS(1, 1);
if (dis[7][7] == 0) {
System.out.println(-1);
} else {
System.out.println(dis[7][7]);
}
}
private void BFS(int x, int y) {
Queue<Point> Q = new LinkedList<>();
Q.offer(new Point(x, y));
board[x][y] = 1;
while (!Q.isEmpty()) {
Point temp = Q.poll();
for (int i = 0; i < 4; i++) {
int nextX = temp.x + dx[i];
int nextY = temp.y + dy[i];
if (nextX >= 1 && nextX <= 7 && nextY >= 1 && nextY <= 7 && board[nextX][nextY] == 0) {
board[nextX][nextY] = 1;
Q.offer(new Point(nextX, nextY));
dis[nextX][nextY] = dis[temp.x][temp.y] + 1;
}
}
}
}
}
package dfsbfs.main12;
import java.util.Scanner;
public class Main {
static int answer = 0;
static int n;
static int[] dx = {-1, -1, 0, 1, 1, 1, 0, -1};
static int[] dy = {0, 1, 1, 1, 0, -1, -1, -1};
static int[][] board;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
board = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
board[i][j] = scanner.nextInt();
}
}
Main main = new Main();
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (board[i][j] == 1) {
answer++;
board[i][j] = 0;
main.DFS(i, j);
}
}
}
System.out.println(answer);
}
private void DFS(int x, int y) {
for (int i = 0; i < 8; i++) {
int nextX = x + dx[i];
int nextY = y + dy[i];
if (nextX >= 0 && nextX < n && nextY >= 0 && nextY < n && board[nextX][nextY] == 1) {
board[nextX][nextY] = 0;
DFS(nextX, nextY);
}
}
}
}Last updated