[백준] 15649: N과 M (1)(Java)

Yoon Uk·2022년 6월 30일

DFS Java 백준 백트래킹 알고리즘

알고리즘 - 백준

목록 보기

6/130

문제

BOJ 15649: N과 M https://www.acmicpc.net/problem/15649

개념 정리

백트래킹(Backtracking)

단어 그대로 되추적 하는 알고리즘이다.

모든 경우의 수를 찾아보지만 그 중에서 가능성이 있는 경우의 수만 찾아보는 방법이다.

어떤 노드를 확인하여 가능성이 있다면 자식 노드로, 가능성이 없다면 부모 노드로 되돌아가며 탐색한다.

DFS

트리순회의 한 형태이다.

백트래킹의 한 형태로 백트래킹에 사용되는 대표적인 탐색 알고리즘이다.

노드의 끝(가장 깊은 곳)까지 먼저 탐색하는 방법이다.

브루트포스

모든 경우의 수를 찾아보는 알고리즘이다.

원하는 값을 100% 찾아낼 수 있지만 경우의 수가 많을 수록 자원을 많이 소모한다.

풀이

재귀를 이용하여 해결한다.
방문하지 않은 값만 탐색하기 위해 boolean 배열인 isVisited 을 사용한다.
탐색 과정에서 값을 담을 int형 배열 arr을 사용한다.
dfs 함수에depth 변수를 추가로 입력받게 하여 depth를 통해 재귀가 깊어질 때 마다 1씩 증가시켜주고 그 depth가 M과 같아지면 재귀를 호출하지 않고 arr값을 출력한 뒤 종료한다.
- 재귀호출 시 depth++을 하게 되면 depth변수의 값 자체가 1이 증가하기 때문에 재귀에서 빠져나와도 증가된 값은 그대로 유지된다. -> dfs 재귀호출 다음 줄에 depth--을 해줘야 한다.
- 반면에 depth + 1은 Java 내부에서 임시로 depth + 1 값을 복사하여 해당 값을 사ㅣ용하기 때문에 재귀에서 빠져나오면 depth + 1값이 날아가버린다.

코드

import java.util.*;
import java.io.*;

public class Main {
	
	static int[] arr;
	static boolean[] isVisited;
	
	public static void main(String[] args) throws IOException{
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		int m = sc.nextInt();
		
		sc.close();
		
		arr = new int[n];
		isVisited = new boolean[n];
		
		dfs(n, m, 0);
	}
	
	static void dfs(int n, int m, int depth) {
		if(depth == m) { // 내가 원하는 깊이까지 오면 종료한다
			for(int i = 0; i < depth; i++) {
				int value = arr[i];
				System.out.print(value + " ");
			}
			System.out.println();
			return;
		}
		
		for(int i=0; i<n; i++) {
			if(!isVisited[i]) { // 방문하지 않은 노드만 탐색하기 위해
				isVisited[i] = true; // 현재 노드는 확인 안 해도 되니깐 true로 처리
				
				arr[depth] = i+1; // 해당 깊이를 index로 하여 i + 1 값을 저장
				dfs(n, m, depth + 1); // 재귀 호출
				
				isVisited[i] = false; // 자식 노드까지 갔다가 돌아오면 다시 false로 바꿔줌
			}
			
		}
		
	}
}