본문 바로가기
알고리즘/JAVA

DFS, BFS 활용

by vivi 2021. 9. 27. 
import java.util.*;

class Main {
	static int n, m, answer = Integer.MAX_VALUE;
	static int[] coin;

	public void DFS(int L, int sum) {
		if (L >= answer || sum > m)
			return;
		if (sum == m) {
			answer = Math.min(L, answer);
			return;
		} else {
			for (int i = 0; i < n; i++) {
				DFS(L + 1, sum + coin[i]);
			}
		}
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		n = kb.nextInt();
		coin = new int[n];
		for (int i = 0; i < n; i++)
			coin[n - 1 - i] = kb.nextInt();
		m = kb.nextInt();
		T.DFS(0, 0);
		System.out.print(answer);
	}
}

1. 합이 같은 부분집합

import java.util.*;

class Main {
	static int n, sum;
	static int[] arr, ch;
	static String answer = "NO";

	public void DFS(int L) {
		if (L == n + 1) {
			int tmp = 0;
			for (int i = 1; i < n + 1; i++) {
				if (ch[i] == 1)
					tmp += arr[i - 1];
			}
			if (sum - tmp == tmp)
				answer = "YES";
		} else {
			ch[L] = 1;
			DFS(L + 1);
			ch[L] = 0;
			DFS(L + 1);
		}
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		n = kb.nextInt();
		arr = new int[n];
		for (int i = 0; i < n; i++)
			arr[i] = kb.nextInt();
		sum = Arrays.stream(arr).sum();
		ch = new int[n + 1];
		T.DFS(1);
		System.out.print(answer);
	}
}

 

import java.util.*;

class Main {
	static String answer = "NO";
	static int n, total = 0;
	boolean flag = false;

	public void DFS(int L, int sum, int[] arr) {
		if (flag)
			return;
		if (sum > total / 2)
			return;
		if (L == n) {
			if ((total - sum) == sum) {
				answer = "YES";
				flag = true;
			}
		} else {
			DFS(L + 1, sum + arr[L], arr);
			DFS(L + 1, sum, arr);
		}
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		n = kb.nextInt();
		int[] arr = new int[n];
		for (int i = 0; i < n; i++)
			arr[i] = kb.nextInt();
		total = Arrays.stream(arr).sum();
		T.DFS(0, 0, arr);
		System.out.print(answer);
	}
}

 

2. 바둑이 승차(DFS)

import java.util.*;

class Main {
	static int answer = Integer.MIN_VALUE;
	static int c, n = 0;

	public void DFS(int L, int sum, int[] arr) {
		if (sum > c)
			return;
		if (L == n) {
			answer = Math.max(answer, sum);
			return;
		} else {
			DFS(L + 1, sum + arr[L], arr);
			DFS(L + 1, sum, arr);
		}
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		c = kb.nextInt();
		n = kb.nextInt();
		int[] arr = new int[n];
		for (int i = 0; i < n; i++)
			arr[i] = kb.nextInt();
		T.DFS(0, 0, arr);
		System.out.print(answer);
	}
}

 

3. 최대점수 구하기(DFS)

import java.util.*;

class Main {
	static int[] score, min;
	static int n, m, answer = Integer.MIN_VALUE;

	public void DFS(int L, int time, int sum) {

		if (time > m)
			return;
		if (L == n) {
			answer = Math.max(answer, sum);
		} else {
			DFS(L + 1, time + min[L], sum + score[L]);
			DFS(L + 1, time, sum);
		}
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		n = kb.nextInt();
		m = kb.nextInt();
		score = new int[n];
		min = new int[n];
		for (int i = 0; i < n; i++) {
			score[i] = kb.nextInt();
			min[i] = kb.nextInt();
		}
		T.DFS(0, 0, 0);
		System.out.print(answer);
	}
}

 

4. 중복순열

import java.util.*;

class Main {
	static int n, m;

	public void DFS(int L, String str) {
		if (L > m + 1)
			return;
		if (L == m + 1) {
			System.out.println(str);
			return;
		} else {
			for (int i = 1; i < n + 1; i++) {
				DFS(L + 1, str + i + " ");
			}
		}
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		n = kb.nextInt();
		m = kb.nextInt();
		T.DFS(1, "");
	}
}

 

import java.util.*;

class Main {
	static int[] pm;
	static int n, m;

	public 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);
			}
		}
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		n = kb.nextInt();
		m = kb.nextInt();
		pm = new int[m];
		T.DFS(0);
	}
}

 

5. 동전교환

import java.util.*;

class Main {
	static int n, m, answer = Integer.MAX_VALUE;
	static int[] coin;

	public void DFS(int L, int sum) {
		if (L >= answer || sum > m)
			return;
		if (sum == m) {
			answer = Math.min(L, answer);
			return;
		} else {
			for (int i = 0; i < n; i++) {
				DFS(L + 1, sum + coin[i]);
			}
		}
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		n = kb.nextInt();
		coin = new int[n];
		for (int i = 0; i < n; i++)
			coin[n - 1 - i] = kb.nextInt();
		m = kb.nextInt();
		T.DFS(0, 0);
		System.out.print(answer);
	}
}

 

import java.util.*;

class Main {
	static int n, m, answer = Integer.MAX_VALUE;
	static Integer[] coin;

	public void DFS(int L, int sum) {
		if (L >= answer || sum > m)
			return;
		if (sum == m) {
			answer = Math.min(L, answer);
			return;
		} else {
			for (int i = 0; i < n; i++) {
				DFS(L + 1, sum + coin[i]);
			}
		}
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		n = kb.nextInt();
		coin = new Integer[n];
		for (int i = 0; i < n; i++)
			coin[i] = kb.nextInt();
		Arrays.sort(coin, Collections.reverseOrder());
		m = kb.nextInt();
		T.DFS(0, 0);
		System.out.print(answer);
	}
}

 

6. 순열 구하기

import java.util.*;

class Main {
	static int n, m;
	static int[] arr, ch;

	public void DFS(int L, int[] pm) {
		if (L == m) {
			for (int x : pm)
				System.out.print(x + " ");
			System.out.println();
			return;
		} else {
			for (int i = 0; i < n; i++) {
				if (ch[i] != 1) {
					ch[i] = 1;
					pm[L] = arr[i];
					DFS(L + 1, pm);
					ch[i] = 0;
				}
			}
		}
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		n = kb.nextInt();
		m = kb.nextInt();
		arr = new int[n];
		int[] pm = new int[m];
		ch = new int[n];
		for (int i = 0; i < n; i++)
			arr[i] = kb.nextInt();
		T.DFS(0, pm);
	}
}

 

7. 조합의 경우수(메모이제이션)

import java.util.*;

class Main {
	static int answer = 0;
	static int[][] memo;

	public int solution(int n, int r) {
		if (memo[n][r] > 0)
			return memo[n][r];
		if (n == r || r == 0)
			return memo[n][r] = 1;
		else {
			return memo[n][r] = solution(n - 1, r - 1) + solution(n - 1, r);
		}
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		int r = kb.nextInt();
		memo = new int[n + 1][r + 1];
		System.out.print(T.solution(n, r));
	}
}

 

8. 수열 추측하기

import java.util.*;

class Main {
	static int answer, n, f = 0;
	static int[][] memo;
	static int[] p, b, ch;
	boolean flag = false;

	public void DFS(int L) {
		if (!flag) {
			if (L == n) {
				int sum = 0;
				for (int i = 0; i < n; i++) {
					sum += b[i] * p[i];
				}
				if (sum == f) {
					for (int x : p)
						System.out.print(x + " ");
					flag = true;
					return;
				}
			} else if (L > n)
				return;
			else {
				for (int i = 0; i < n; i++) {
					if (ch[i] == 0) {
						ch[i] = 1;
						p[L] = i + 1;
						DFS(L + 1);
						ch[i] = 0;
					}

				}
			}
		} else
			return;
	}

	public int combi(int n, int r) {
		if (memo[n][r] > 0)
			return memo[n][r];
		if (n == r || r == 0)
			return memo[n][r] = 1;
		else {
			return memo[n][r] = combi(n - 1, r - 1) + combi(n - 1, r);
		}
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		n = kb.nextInt();
		f = kb.nextInt();
		memo = new int[n + 1][n + 1];
		b = new int[n];
		p = new int[n];
		ch = new int[n];
		for (int i = 0; i < n; i++) {
			b[i] = T.combi(n - 1, i);
		}
		T.DFS(0);
	}
}

 

9. 조합 구하기

import java.util.*;

class Main {
	static int n, m;
	static int[] arr;

	public void DFS(int L, int[] pm, int s) {
		if (L == m) {
			for (int x : pm)
				System.out.print(x + " ");
			System.out.println();
			return;
		} else {
			for (int i = s; i < n; i++) {
				pm[L] = arr[i];
				DFS(L + 1, pm, pm[L]);
			}
		}
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		n = kb.nextInt();
		m = kb.nextInt();
		arr = new int[n + 1];
		int[] pm = new int[m];
		for (int i = 0; i < n; i++)
			arr[i] = i + 1;
		T.DFS(0, pm, 0);
	}
}

 

import java.util.*;

class Main {
	static int[] combi;
	static int n, m;

	public void DFS(int L, int s) {
		if (L == m) {
			for (int x : combi)
				System.out.print(x + " ");
			System.out.println();
		} else {
			for (int i = s; i <= n; i++) {
				combi[L] = i;
				DFS(L + 1, i + 1);
			}
		}
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		n = kb.nextInt();
		m = kb.nextInt();
		combi = new int[m];
		T.DFS(0, 1);
	}
}

 

10. 미로탐색(DFS)

import java.util.*;

class Main {
	static int[][] miro;
	static int answer = 0;
	static int[] dx = { 0, 0, -1, 1 }, dy = { 1, -1, 0, 0 };

	public void DFS(int x, int y) {
		if (x == 6 && y == 6) {
			answer++;
			return;
		} else {
			for (int i = 0; i < 4; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				if (nx >= 0 && nx < 7 && ny >= 0 && ny < 7 && miro[nx][ny] == 0) {
					miro[x][y] = 1;
					DFS(nx, ny);
					miro[x][y] = 0;
				}
			}
		}
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		miro = new int[7][7];
		for (int i = 0; i < 7; i++)
			for (int j = 0; j < 7; j++)
				miro[i][j] = kb.nextInt();
		T.DFS(0, 0);
		System.out.print(answer);
	}
}

 

11. 미로의 최단거리 통로(BFS)

import java.util.*;

class Pos {
	int bx, by, cx, cy, dis;

	public Pos(int bx, int by, int cx, int cy, int dis) {
		this.bx = bx;
		this.by = by;
		this.cx = cx;
		this.cy = cy;
		this.dis = dis;
	}

	public void setBPos(int bx, int by) {
		this.bx = bx;
		this.by = by;
	}

	public void setCPos(int cx, int cy) {
		this.cx = cx;
		this.cy = cy;
	}

	public int getCx() {
		return cx;
	}

	public int getCy() {
		return cy;
	}

	public int getBx() {
		return bx;
	}

	public int getBy() {
		return by;
	}

	public int getDis() {
		return dis;
	}

}

class Main {
	static int[][] miro;
	static int answer = Integer.MAX_VALUE;
	static int[] dx = { 0, 0, -1, 1 }, dy = { 1, -1, 0, 0 };
	Queue<Pos> q = new LinkedList<>();

	public void BFS() {
		Pos p = new Pos(0, 0, 0, 0, 0);
		q.offer(p);
		while (!q.isEmpty()) {

			for (int i = 0; i < q.size(); i++) {
				p = q.poll();
				for (int j = 0; j < 4; j++) {
					int nx = p.getCx() + dx[j];
					int ny = p.getCy() + dy[j];
					if (nx == 6 && ny == 6) {
						answer = Math.min(answer, p.getDis() + 1);
					}
					if (nx >= 0 && nx < 7 && ny >= 0 && ny < 7 && miro[nx][ny] == 0
							&& !(p.getBx() == nx && p.getBy() == ny) && p.getDis() < answer && p.getDis() < 30) {
						q.offer(new Pos(p.getCx(), p.getCy(), nx, ny, p.getDis() + 1));
					}
				}
			}
		}
		if (answer == Integer.MAX_VALUE)
			answer = -1;
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		miro = new int[7][7];
		for (int i = 0; i < 7; i++)
			for (int j = 0; j < 7; j++)
				miro[i][j] = kb.nextInt();
		T.BFS();
		System.out.print(answer);
	}
}

 

import java.util.*;

class Pos {
	int x, y;

	public Pos(int x, int y) {
		super();
		this.x = x;
		this.y = y;
	}

	public int getX() {
		return x;
	}

	public void setX(int x) {
		this.x = x;
	}

	public int getY() {
		return y;
	}

	public void setY(int y) {
		this.y = y;
	}

}

class Main {
	static int[][] miro, board;
	static int answer = Integer.MAX_VALUE;
	static int[] dx = { 0, 0, -1, 1 }, dy = { 1, -1, 0, 0 };
	Queue<Pos> q = new LinkedList<>();

	public void BFS() {
		q.offer(new Pos(0, 0));
		while (!q.isEmpty()) {
			int len = q.size();
			for (int i = 0; i < len; i++) {
				Pos p = q.poll();
				for (int j = 0; j < 4; j++) {
					int nx = p.getX() + dx[j];
					int ny = p.getY() + dy[j];
					if (nx >= 0 && nx < 7 && ny >= 0 && ny < 7 && miro[nx][ny] == 0 && board[nx][ny] == 0) {
						miro[nx][ny] = 1;
						board[nx][ny] = board[p.getX()][p.getY()] + 1;
						q.offer(new Pos(nx, ny));
					}
				}
			}
		}
		if (board[6][6] != 0)
			answer = board[6][6];
		else
			answer = -1;
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		miro = new int[7][7];
		board = new int[7][7];
		for (int i = 0; i < 7; i++)
			for (int j = 0; j < 7; j++)
				miro[i][j] = kb.nextInt();
		T.BFS();
		System.out.print(answer);
	}
}

 

12. 토마토(BFS 활용)

import java.util.*;

class Pos {
	int x, y;

	public int getX() {
		return x;
	}

	public void setX(int x) {
		this.x = x;
	}

	public int getY() {
		return y;
	}

	public void setY(int y) {
		this.y = y;
	}

	public Pos(int x, int y) {
		this.x = x;
		this.y = y;
	}
}

public class Main {
	static int m, n, answer = 0;
	static int[][] tomato;
	Queue<Pos> Q = new LinkedList<>();
	int[] dx = { 0, 0, -1, 1 }, dy = { 1, -1, 0, 0 };

	boolean flag = true;

	public void BFS() {
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (tomato[i][j] == 1)
					Q.offer(new Pos(j, i));
			}
		}

		while (!Q.isEmpty()) {
			int len = Q.size();
			for (int i = 0; i < len; i++) {
				Pos p = Q.poll();
				for (int j = 0; j < 4; j++) {
					int nx = p.getX() + dx[j];
					int ny = p.getY() + dy[j];
					if (nx >= 0 && nx < m && ny >= 0 && ny < n && tomato[ny][nx] == 0) {
						tomato[ny][nx] = 1;
						Q.offer(new Pos(nx, ny));
					}
				}
			}
			answer++;
			flag = true;
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					if (tomato[i][j] == 0)
						flag = false;
				}
			}
			if (flag)
				return;
		}
		if (!flag)
			answer = -1;
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		m = kb.nextInt();
		n = kb.nextInt();
		tomato = new int[n][m];
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				tomato[i][j] = kb.nextInt();
		T.BFS();
		System.out.print(answer);
		return;
	}
}

 

import java.util.*;

class Point {
	public int x, y;

	Point(int x, int y) {
		this.x = x;
		this.y = y;
	}
}

public class Main {
	static int m, n;
	static int[][] board, dis;
	static int[] dx = { -1, 0, 1, 0 }, dy = { 0, 1, 0, -1 };
	static Queue<Point> Q = new LinkedList<>();

	public void BFS() {
		while (!Q.isEmpty()) {
			Point tmp = Q.poll();
			for (int i = 0; i < 4; i++) {
				int nx = tmp.x + dx[i];
				int ny = tmp.y + dy[i];
				if (nx >= 0 && nx < n && ny >= 0 && ny < m && board[nx][ny] == 0) {
					board[nx][ny] = 1;
					Q.offer(new Point(nx, ny));
					dis[nx][ny] = dis[tmp.x][tmp.y] + 1;
				}
			}
		}
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		m = kb.nextInt();
		n = kb.nextInt();
		board = new int[n][m];
		dis = new int[n][m];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				board[i][j] = kb.nextInt();
				if (board[i][j] == 1)
					Q.offer(new Point(i, j));
			}
		}
		T.BFS();
		boolean flag = true;
		int answer = Integer.MIN_VALUE;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (board[i][j] == 0)
					flag = false;
			}
		}
		if (flag) {
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < m; j++) {
					answer = Math.max(answer, dis[i][j]);
				}
			}
			System.out.print(answer);
		} else
			System.out.println(-1);
	}
}

 

13. 섬나라 아일랜드(DFS)

import java.util.*;

class Point {
	public int x, y;

	Point(int x, int y) {
		this.x = x;
		this.y = y;
	}
}

public class Main {
	static int n, answer = 0;
	static int[] dx = { -1, -1, 0, 1, 1, 1, 0, -1 }, dy = { 0, 1, 1, 1, 0, -1, -1, -1 };
	static int[][] board;
	static boolean cnt = false;

	public void DFS(int x, int y) {
		boolean flag = true;

		board[x][y] = 0;
		for (int i = 0; i < 8; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx >= 0 && nx < n && ny >= 0 && ny < n && board[nx][ny] == 1) {
				DFS(nx, ny);
				flag = false;
			}
		}
		if (flag) {
			if (!cnt)
				answer++;
			cnt = true;
			return;
		}
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		n = kb.nextInt();
		board = new int[n][n];
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				board[i][j] = kb.nextInt();

		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++) {
				if (board[i][j] == 1) {
					cnt = false;
					T.DFS(i, j);
				}
			}
		System.out.print(answer);
	}
}

 

import java.util.*;

class Point {
	public int x, y;

	Point(int x, int y) {
		this.x = x;
		this.y = y;
	}
}

public class Main {
	static int n, answer = 0;
	static int[] dx = { -1, -1, 0, 1, 1, 1, 0, -1 }, dy = { 0, 1, 1, 1, 0, -1, -1, -1 };
	static int[][] board;
	Queue<Point> q = new LinkedList<>();

	public void DFS(int x, int y) {
		board[x][y] = 0;
		for (int i = 0; i < 8; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if (nx >= 0 && nx < n && ny >= 0 && ny < n && board[nx][ny] == 1) {
				DFS(nx, ny);
			}
		}
	}

	public void BFS() {
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++) {
				if (board[i][j] == 1) {
					board[i][j] = 0;
					answer++;
					q.offer(new Point(i, j));
					while (!q.isEmpty()) {
						int len = q.size();
						for (int k = 0; k < len; k++) {
							Point p = q.poll();
							for (int s = 0; s < 8; s++) {
								int nx = p.x + dx[s];
								int ny = p.y + dy[s];
								if (nx >= 0 && nx < n && ny >= 0 && ny < n && board[nx][ny] == 1) {
									board[nx][ny] = 0;
									q.offer(new Point(nx, ny));
								}
							}
						}
					}
				}
			}

	}

	public void solution() {
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++) {
				if (board[i][j] == 1) {
					answer++;
					DFS(i, j);
				}
			}
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		n = kb.nextInt();
		board = new int[n][n];
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				board[i][j] = kb.nextInt();
//		T.solution();
		T.BFS();
		System.out.print(answer);
	}
}

for의 향연..

 

14. 피자 배달 거리(삼성 SW역량평가 기출문제 : DFS활용)

import java.util.*;

class Point {
	public int x, y;

	Point(int x, int y) {
		this.x = x;
		this.y = y;
	}
}

public class Main {
	static int n, m, answer = Integer.MAX_VALUE;
	static ArrayList<Point> pizza, house;
	static ArrayList<Point> s;

	public int dis() {
		// 피자 배달 거리 계산.
		int M = 0;
		for (Point h : house) {
			int min = Integer.MAX_VALUE;
			for (Point p : s) {
				min = Math.min(min, Math.abs(h.x - p.x) + Math.abs(h.y - p.y));
			}
			M += min;
		}
		return M;
	}

	public void DFS(int L, int n, int dis) {

		if (L >= pizza.size() || n > m)
			return;
		if (n == m && dis < answer) {
			answer = dis;
			return;
		} else {
			Point tmp = pizza.get(L);
			s.add(tmp);
			int M = dis();
			DFS(L + 1, n + 1, M);
			s.remove(tmp);
			DFS(L + 1, n, dis);
		}
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		n = kb.nextInt();
		m = kb.nextInt();
		pizza = new ArrayList<Point>();
		house = new ArrayList<Point>();
		s = new ArrayList<Point>();
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++) {
				int n = kb.nextInt();
				if (n == 1)
					house.add(new Point(i, j));
				else if (n == 2)
					pizza.add(new Point(i, j));
			}
		T.DFS(0, 0, 0);
		System.out.print(answer);
	}
}

 

import java.util.*;

class Point {
	public int x, y;

	Point(int x, int y) {
		this.x = x;
		this.y = y;
	}
}

public class Main {
	static int n, m, answer = Integer.MAX_VALUE, len;
	static ArrayList<Point> pizza, house;
	static int[] combi;

	public void DFS(int L, int s) {
		if (L == m) {
			int M = 0;
			for (Point h : house) {
				int min = Integer.MAX_VALUE;
				for (int i = 0; i < m; i++) {
					Point p = pizza.get(combi[i]);
					min = Math.min(min, Math.abs(h.x - p.x) + Math.abs(h.y - p.y));
				}
				M += min;
			}
			answer = Math.min(answer, M);
		} else {
			for (int i = s; i < len; i++) {
				combi[L] = i;
				DFS(L + 1, i + 1);
			}
		}
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		n = kb.nextInt();
		m = kb.nextInt();
		pizza = new ArrayList<Point>();
		house = new ArrayList<Point>();
		combi = new int[m];
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++) {
				int n = kb.nextInt();
				if (n == 1)
					house.add(new Point(i, j));
				else if (n == 2)
					pizza.add(new Point(i, j));
			}
		len = pizza.size();
		T.DFS(0, 0);
		System.out.print(answer);
	}
}

조합구하는 방식 외워두기

'알고리즘 > JAVA' 카테고리의 다른 글

dynamic programming(동적계획법)  (0) 2021.10.06
Greedy Algorithm  (0) 2021.10.04
Recursive, Tree, Graph(DFS, BFS 기초)  (0) 2021.09.26
10. 마구간 정하기(결정알고리즘)  (0) 2021.09.25
9. 뮤직비디오(결정알고리즘)  (0) 2021.09.25

관련글

댓글

티스토리툴바