DFS/BFS
유형
1.합이 같은 부분집합(DFS : 아마존 면접)
//문제
N개의 원소로 구성된 자연수 집합이 주어지면, 이 집합을 두 개의 부분집합으로 나누었을 때
두 부분집합의 원소의 합이 서로 같은 경우가 존재하면 YES를 출력하고, 그렇지 않으면
NO를 출력하는 프로그램을 작성하세요.
//입력
6
1 3 5 6 7 10
//출력
YESpublic class ex1 {
static int n, total=0;
static String answer="NO";
public static void DFS(int L,int sum,int[] arr){
if(sum>total/2) return;
if(L==n){
if((total-sum)==sum){
answer="YES";
}
}
else{
DFS(L+1,sum+arr[L],arr);
DFS(L+1,sum,arr);
}
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
int[] arr= new int[n];
for(int i=0; i<n; i++){
arr[i] = sc.nextInt();
total+=arr[i];
}
DFS(0,0,arr);
System.out.println(answer);
}
}
풀이
1.부분집합을 2개로 나눴을 때 두 부분집합들의 합이 같아야한다 --> 절반이 총합이랑 같아야한다.
2.그것을 기준으로 DFS시작
2.바둑2 승차(DFS)
//문제
N마리의 바둑2과 바둑2의 각 무게 W가 주어지면, 철수가 트럭에 태울 수 있는 가장 무거운 무게를 구하는 프로그램을 작성
//입력
259 5
81
58
42
33
61
//출력
242public class ex2 {
static int n,c;
static int answer =0;
public static void DFS(int L,int sum,int[] arr){
if(sum>c) return;
if(L==n) {
answer=Math.max(answer,sum);
}
else{
DFS(L+1,sum+arr[L],arr);
DFS(L+1,sum,arr);
}
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
c = sc.nextInt();
n = sc.nextInt();
int[] arr= new int[n];
for(int i=0; i<n; i++){
arr[i] = sc.nextInt();
}
DFS(0,0,arr);
System.out.println(answer);
}
}풀이
1. 첫 줄에 입력되는 무게를 넘지않게 최대한 큰 수를 구해야한다.
2. 위 문제와 비슷하다.
3.최대 점수 구하기(DFS)
//문제
첫 번째 줄에 문제의 개수N , 제한 시간 M이 주어진다. 두 번째 줄 부터 점수와 시간이 주어진다.
M을 넘지 않으면서 풀 수있는 최고 점수를 구해라.
//입력
5 20
10 5
25 12
15 8
6 3
7 4
//출력
41
public class ex3 {
static int n,m;
static int answer =0;
static int sum2=0;
public static void DFS(int L,int sum,int time,int[] a,int[] b){
if(time>m) return;
if(L==n) {
answer=Math.max(answer,sum);
}
else{
DFS(L + 1, sum + a[L],time+b[L],a,b);
DFS(L + 1, sum,time,a,b);
}
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
int[] a= new int[n];
int[] b= new int[n];
for(int i=0; i<n; i++){
a[i] = sc.nextInt();
b[i] = sc.nextInt();
}
DFS(0,0,0,a,b);
System.out.println(answer);
}
}
풀이
1.종착점의 경우 : 시간초과 , 해당 문제 개수만큼 풀었을 경우
2.재귀 : sum에 점수인a[L]를 더한다. time에 시간 b[L]을 더한다.
4.중복 순열 구하기
//문제
1부터N까지 중복을 허락하여 M번을 뽑아 순열을 구하여라.
//입력
3 2
//출력
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3public class ex4 {
static int n,m;
static int[] answer;
public static void DFS(int L){
if(L==m) {
for(int x : answer) System.out.print(x + " ");
}
else{
for(int i=1; i<=n; i++){
answer[L]=i;
DFS(L+1);
}
}
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
answer = new int[m];
DFS(0);
}
}
풀이
1.1부터 N까지의 숫자이기 때문에 for문으로 answer에 i값을 그냥 바로 더하고 다음 재귀 호출.
2.종착점 : L==m 인 경우.
5.동전 교환
//문제
여러 단위의 동전이 주어졌을때 거스름돈을 가장 적은 수의 동전으로 교환 해주려면 어떻게 줘야 하는 가?
//입력
3
1 2 5
15
//출력
3public class ex5 {
static int n,m;
static int answer=Integer.MAX_VALUE;
public static void DFS(int L,int sum,Integer[] arr){
if(sum>m) return;
if(L>=answer) return;
if(sum==m) answer = Math.min(answer,L);
else{
for(int i=0; i<n; i++){
DFS(L+1,sum+arr[i],arr);
}
}
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
Integer[] arr = new Integer[n];
for(int i=0; i<n; i++){
arr[i] = sc.nextInt();
}
Arrays.sort(arr, Collections.reverseOrder());
//-->기본형 int 말고 객체형 int(Integer)만 정렬가능
//-->속도 높여주기 위해서 역순으로 정렬
m = sc.nextInt();
DFS(0,0,arr);
System.out.print(answer);
}
}풀이
1. 종착점 : 동전의 합이 m보다 클때 , 현재 저장된 answer의 동전 수 보다 동전의 수가 많아질 때
2.DFS를 호출하면서 for문과 함께 sum + arr[i]를 해준다.
[ 주요 기능 ]
이 DFS 탐색의 정답은 후반부에 있기 때문에 효율측면에서 극대화시키기 위해서
Arrays.sort를 역순으로 해줌으로써 코드 속도를 높인다.
Arrays.sort는 int형이 아닌, 객체형 int인 Integer를 써야만 정렬이 가능하다.
6.순열 구하기
//문제
10이하의 N개의 자연수가 주어지면 이 중 M개를 뽑아 일렬로 나열하는 방법을 모두 출력.
//입력
3 2
3 6 9
//출력
3 6
3 9
6 3
6 9
9 3
9 6public class ex6 {
static int n,m;
static int[] answer;
static int[] ch;
public static void DFS(int L,int[] num){
if(L==m) {
for(int x : answer) System.out.print(x + " ");
}
else{
for(int i=0; i<n; i++){
if(ch[i]==0){
ch[i]=1;
answer[L]=num[i];
DFS(L+1,num);
ch[i]=0;
}
}
}
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
int[] num = new int[n];
for(int i=0; i<n; i++){
num[i] = sc.nextInt();
}
answer = new int[m];
ch = new int[n];
DFS(0,num);
}
}
풀이
1.중복순열은 아니다. --> 체크 배열 사용.
2.L=0부터 시작해서 m이 되면 종착점으로써 출력.
3.체크배열로 체크하면서 answer[L]에 num[i]를 저장
4.DFS다음 L 호출. --> 호출 후에 끝나면 ch[i]==0으로 호출 해제
7.조합의 경우의 수(메모이제이션)
//문제
재귀를 이용해 조합수를 구해주는 프로그램을 작성하세요.
//입력
5 3
//출력
10public class ex7 {
static int[][] ch = new int[35][35];
public static int DFS(int n, int r){
if(ch[n][r]>0) return ch[n][r];
if(r==0 || n==r) return 1;
else {
return ch[n][r] = DFS(n-1,r-1) + DFS(n-1,r);
}
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int r = sc.nextInt();
System.out.println(DFS(n,r));
}
}풀이
1.(n-1)C9(r-1) + (n-1)C(r) 을 DFS로 만든다.
2.불필요한 계산을 막기 위해서 ch[][]배열을 활용한다.
8.💥순열 추측하기 (어려움)
//문제
N과 가장 밑에 있는 숫자가 주어져 있을 때 가장 윗줄에 있는 숫자를 구하는 프로그램을 작성하
시오. 단, 답이 여러가지가 나오는 경우에는 사전순으로 가장 앞에 오는 것을 출력하여야 한다.
3 1 2 4
4 3 6
7 9
16
//입력
4 16
//출력
3 1 2 4//순열 예측하기 = 조합 경우의 수 + 순열 구하기
public class ex8 {
static boolean flag=false;
static int n=0,f=0;
static int[] b,p,ch;
static int[][] dy = new int[35][35]; //combi 체크배열
public static int combi(int n, int r){
if(dy[n][r]>0) return dy[n][r];
if(r==0 || n==r) return 1;
else {
return dy[n][r] = combi(n-1,r-1) + combi(n-1,r);
}
}
public static void DFS(int L,int sum){
if(flag) return;
if(L==n){
if(sum==f){
for(int x : p) System.out.print(x + " ");
flag=true;
}
}else{
for(int i=1; i<=n; i++){
if(ch[i]==0){
ch[i]=1;
p[L]=i;
DFS(L+1, sum+(p[L]*b[L]));
ch[i]=0;
}
}
}
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
f = sc.nextInt();
b = new int[n];
p = new int[n];
ch = new int[n+1];
for(int i=0; i<n; i++){
b[i] = combi(n-1,i);
}
DFS(0,0);
}
}풀이
1.조합 경우의 수 함수를 작성한다. -> b[]에 담는다.
2.정답을 담을 p[]과 조합 경우의수를 담고있는 b[]을 곱한 값을 sum에 더하면서 다음 재귀를 호출한다.
9.조합 구하기
//문제
1부터 N까지 번호가 적힌 구슬이 있습니다. 이 중 M개를 뽑는 방법의 수를 출력하는 프로그램을 작성.
//입력
4 2
//출력
1 2
1 3
1 4
2 3
2 4
3 4public class ex9 {
static int n=0,m=0;
static int[] combi;
public static 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){
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
combi = new int[m];
DFS(0,1);
}
}풀이
1.입력받은 m크기를 저장할 combi배열 선언
2.L==m이면 종착점으로써 값 출력
3.i=s부터 n (1~4) 까지 combi[L]에 i값을 저장하고 다음 DFS를 호출한다.
4.이때 s(start point)를 +1을 해준다.
10.미로탐색(DFS)
//문제
7*7 격자판 미로를 탈출하는 경로의 가지수를 출력하는 프로그램을 작성하세요.
//입력
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
//출력
8public class ex10 {
static int[] dx={-1,0,1,0};
static int[] dy={0,1,0,-1};
static int[][] board;
static int answer;
public static void DFS(int x,int y) {
if(x==7 && y==7){
answer++;
}
else {
for(int i=0; i<4; i++){
int nx=x+dx[i];
int ny=y+dy[i];
if(nx>=1 && nx<=7 && ny>=1 && ny<=7 && board[nx][ny]==0){
board[nx][ny]=1;
DFS(nx,ny);
board[nx][ny]=0;
}
}
}
}
public static void main(String[] args){
Scanner sc = 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]=sc.nextInt();
}
}
board[1][1]=1;
DFS(1,1);
System.out.println(answer);
}
}풀이
1.상하좌우 좌표움직임을 나타내는 dx,dy를 선언한다.
2.7x7크기의 board를 만든다.
3.1,1위치의 값은 1로 두면서 DFS(1,1)를 호출해서 시작한다.
4.DFS함수에서 i를 12,3,6,9시 까지 돌린다. 이때 if문의 조건에 들어맞으면 board[nx][ny]=1로 체크하고 DFS(nx,ny)를 호출하면서 다음 위치로 이동.
5.빽트래킹될때는 돌아가야하기 때문에 board[nx][ny]를 0으로 돌려준다.
6.x,y좌표가 7이 되면 answer+ +해준다.
11.미로의 최단거리 통로(BFS)
//문제
7*7 격자판 미로를 탈출하는 최단경로의 길이를 출력하는 프로그램을 작성하세요.
//입력
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 1 0 0 0
1 0 0 0 1 0 0
1 0 1 0 0 0 0
//출력
12class Point{
public int x,y;
Point(int x,int y){
this.x = x;
this.y = y;
}
}
public class ex11 {
static int[] dx={-1,0,1,0};
static int[] dy={0,1,0,-1};
static int[][] board,dis;
public static 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 tmp=Q.poll();
for(int i=0; i<4; i++){
int nx = tmp.x+dx[i];
int ny = tmp.y+dy[i];
if(nx>=1 && nx<=7 && ny>=1 && ny<=7 && board[nx][ny]==0){
board[nx][ny]=1;
Q.offer(new Point(nx,ny));
dis[nx][ny] = dis[tmp.x][tmp.y] + 1; //dis->거리 측정배열
}
}
}
}
public static void main(String[] args){
Scanner sc = 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]=sc.nextInt();
}
}
BFS(1,1);
if(dis[7][7]==0) System.out.println(-1);
else System.out.println(dis[7][7]);
}
}풀이
1.최단거리는 BFS방식으로 Q를 이용해서 푸는 문제. Q에 x,y좌표를 담기위한 Point객체를 생성한다.
2.일반 적인 미로탐색과 같이 dx,dy를 선언해서 좌표이동을 나타내고, board[][]를 선언해서 7x7로 만든다.그러고 BFS(1,1)로 함수 호출.
3.Q를 선언하고 Q.offer(new Point(x,y));를 해준다. 그러고 board[x][y]현재위치에 1를 저장하고 while문으로 시작한다.
4.Q에있는 걸 Q.poll()해서 뺀다음에 for문으로 i를 4번 돌아가게 한 다음, int nx = tmp.x+dx[i]; int ny = tmp.y+dy[i]; 를 해서 다음좌표를 설정해준다.
5.nx,ny좌표 설정을 마치면 if문으로 조건에 해당하면 좌표를 이동시킨다.
6.board[nx][ny]에 1을 저장해주고, Q.offer(new Point(nx,ny));를 해준다.
7.마지막으로 거리측정 배열 dis[]에 dis[nx][ny] = dis[tmp.x][tmp.y] + 1;를 해주면서 거리를 측정한다.
8.dis[7][7]에 어떤 값이 저장되어있는지 출력한다. 그것이 최단거리이다.
-->최단거리인 이유. : dis[7][7]에 어떤 경로가 먼저 도착하면 board[7][7]=1로 체크되어서 if문이 성립되지 않아서 다음 nx,ny들은 의미가없어지고 while문이 종료된다.
12.💥 토마토(BFS 활용)
//문제
토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들
의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로
그램을 작성하라. 단, 상자의 일부 칸에는 토마토가 들어있지 않을 수도 있다
//입력
6 4
0 0 -1 0 0 0
0 0 1 0 -1 0
0 0 -1 0 0 0
0 0 0 0 -1 1
//출력
4public class ex12 {
static int n=0,m=0;
static Queue<Point> Q = new LinkedList<>();
static int[][] board,dis;
static int[] dx={-1,0,1,0};
static int[] dy={0,1,0,-1};
static int answer = 0;
public static 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){
Scanner sc = new Scanner(System.in);
m=sc.nextInt();
n=sc.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]=sc.nextInt();
if(board[i][j]==1) Q.offer(new Point(i,j));
}
}
BFS();
boolean flag=true;
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.println(answer);
}
else System.out.println(-1);
}
}
풀이
1.우선 x,y좌표를 선언할 Point객체를 만들고 실제 입력값을 저장할 board[][]와 일수(길이)를 저장할 dis[][]를 선언한다. 그리고 이미 익어있는 토마토위치를 Q에 삽입해둔다.(한 개가 아니라 여러 개 일수도 있어서) 그리고 나서 BFS()호출.
2.4가지 방향을 dx,dy로 선언하고 BFS의 while문을 돌린다. Q.poll()을 한 다음, 그 poll()한 값으로 다음 nx,ny좌표를 구한다. 그리고 if문으로 탐색조건이 일치하면 재방문 못하게 왓던곳은 1로 체크해준다. Q.offer(new Point(ny,nx))로 다음 좌표를 Q에 삽입. 그리고 dis[ny][nx] = dis[Q.poll().x][Q.poll().y] + 1 값을 저장한다.
3.이 문제에서 출력을 토마토가 다 안익는경우는 -1 , 그게 아니면 토마토가 익는 최단기간을 출력해야한다. 그래서 flag를 이용해서 출력해준다.
13.섬나라 아일랜드(DFS)
//문제
N*N의 섬나라 아일랜드의 지도가 격자판의 정보로 주어집니다. 각 섬은 1로 표시되어 상하좌
우와 대각선으로 연결되어 있으며, 0은 바다입니다. 섬나라 아일랜드에 몇 개의 섬이 있는지
구하는 프로그램을 작성
//입력
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
//출력
5public class ex13 {
static int answer=0,n=0;
static int[] dx={-1, -1, 0, 1, 1, 1, 0, -1};
static int[] dy={0, 1, 1, 1, 0, -1, -1, -1};
public static void DFS(int x,int y,int[][] board){
for(int i=0; i<8; i++){ //8방향
int nx= x+dx[i];
int ny= y+dy[i];
if(nx>=0 && nx<n && ny>=0 && ny<n && board[nx][ny]==1){
board[nx][ny]=0;
DFS(nx,ny,board);
}
}
}
public static void solution(int[][] board){
//board를 돌면서 섬을 찾아다닌다. 여기서 DFS가 들린곳은 0으로 만들어준다.
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
if(board[i][j]==1){
answer++;
//DFS에서 주변 8방향 들린곳을 0으로 만들어 줌.
DFS(i,j,board);
}
}
}
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
n=sc.nextInt();
int[][] board = new int[n][n];
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
board[i][j]=sc.nextInt();
}
}
solution(board);
System.out.println(answer);
}
}
풀이
1.일단 8방향 좌표 dx,dy를 선언, board[][]를 선언. solution을 호출한다.
2.solution에서 2중 for문으로 board를 다 돌려서 1이 나오면 answer++ 해주고 DFS()를 호출한다.
3.DFS()에서 8방향으로 nx,ny를 정해주고 if문 조건에 들어맞으면 board[nx][ny]로 이동하고 0(바다)으로 만들어버린다. 그러고 DFS()계속 호출
14.섬나라 아일랜드(BFS)
//문제
N*N의 섬나라 아일랜드의 지도가 격자판의 정보로 주어집니다. 각 섬은 1로 표시되어 상하좌
우와 대각선으로 연결되어 있으며, 0은 바다입니다. 섬나라 아일랜드에 몇 개의 섬이 있는지
구하는 프로그램을 작성
//입력
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
//출력
5public class ex14 {
static int answer=0, n;
static int[] dx={-1, -1, 0, 1, 1, 1, 0, -1};
static int[] dy={0, 1, 1, 1, 0, -1, -1, -1};
static Queue<Point> Q = new LinkedList<>();
public static void BFS(int x, int y, int[][] board){
Q.offer(new Point(x, y));
while(!Q.isEmpty()){
Point pos = Q.poll();
for(int i=0; i<8; i++){
int nx=pos.x+dx[i];
int ny=pos.y+dy[i];
if(nx>=0 && nx<n && ny>=0 && ny<n && board[nx][ny]==1){
board[nx][ny]=0;
Q.offer(new Point(nx, ny));
}
}
}
}
public static void solution(int[][] board){
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
if(board[i][j]==1){
answer++;
board[i][j]=0;
BFS(i, j, board);
}
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
int[][] board=new int[n][n];
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
board[i][j]=sc.nextInt();
}
}
solution(board);
System.out.println(answer);
}
}
풀이
1.DFS방식과 똑같이 8방향으로 dx,dy를 선언해주고 board[i][j]를 입력 후 solution(board)호출.
2.solution에서는 board[i][j]가 1이 나오면 answer++를 해주고 BFS()를 호출한다.
3.BFS()에서는 Q.offer(new Point(x,y))를 하고 while문을 돌려준다. Q.poll()를 해서 8방향으로 nx,ny를 정해주고, if문에 들어맞으면 들린 곳은 0으로 바꿔버리고 Q.offer(new Point(nx,ny));를 해주는 식으로한다. DFS와 유사하다.
