완전탐색(DFS/BFS) VS 백트래킹+순열과 조합(백준N과 M)

String start = "\"재귀함수가 뭔가요\"\n"; String cont = "\"잘 들어보게.\"\n"; Strng fin = "\"재귀함수는 자기 자신을 호출하는 함수라네.\"\n"; int N; // 반복 횟수 void recur(int level) { System.out.print("_"*level + start); if(level==N) { // 종료 조건 System.out.print(fin); return; } System.out.print(cont); recur(level+1); // 다음 단계 }

public class Main { static boolean[] isSelected = new boolean[5]; static int[] arr = {0,1,2,3,4}; public static void main(String[] args) { recur(0); } public static void recur(int level) { if(level==5) { // 종료 조건 for(int i=0; i<5; i++){ if(isSelected[i]) System.out.print(arr[i] + " "); } System.out.println(); return; } isSelected[level] = true; // Case 1_ 쓴다 (0,1,2,3,4) (4, recur(level+1); // 다음 단계 1,2,3,4,5(리턴) 5 isSelected[level] = false; // Case 2_ 안 쓴다 (4) (3,4) recur(level+1); // 5(리턴) 4,5(리턴) } }

public class Main { public static void main(String[] args) { int n=5; int r=3; int[] arr = {0,1,2,3,4}; int[] perm = new int[n]; // 순열 boolean[] isSelected = new boolean[n]; // 방문 여부 recur(arr, perm, isSelected, 0, n, r); } public static void recur(int[] arr, int[] perm, boolean[] isSelected, int level, int n, int r) { if(level==r) { // 종료 조건 for(int i=0; i<r; i++){ System.out.print(perm[i] + " "); } System.out.println(); return; } for(int i=0; i<n; i++) { if(isSelected[i]) continue; perm[level] = arr[i]; isSelected[i] = true; // Case 1 recur(arr, perm, isSelected, level+1, n, r); // 다음 단계 // perm[level] = 0; isSelected[i] = false; // Case 2 } } }

import java.util.*; public class Main { static boolean visited[]; static ArrayList<Integer>[] A; public static void main(String[] args) { Scanner scan = new Scanner(System.in); int N = scan.nextInt(); // 노드 개수 int M = scan.nextInt(); // 에지 개수 int Start = scan.nextInt(); // 시작점 // 1. 인접 리스트로 그래프 표현하기 A = new ArrayList[N+1]; for(int i=1; i<=N; i++) { // 노드 초기화 A[i] = new ArrayList<Integer>(); } for(int i=0; i<M; i++) { // 엣지의 양끝 노드 입력받기 int S = scan.nextInt(); int E = scan.nextInt(); A[S].add(E); A[E].add(S); // 양방향이라서 양쪽 노드에 엣지 추가 } for(int i=1; i<=N; i++) { // 번호 작은 것 먼저 방문하기 위해 각 노드의 엣지들 정렬 Collections.sort(A[i]); } // DFS // 2. 방문 배열 초기화하기 visited = new boolean[N+1]; // 3. 시작 노드 스택에 삽입하기(여기선 스택 대신 재귀함수 사용) DFS(Start); System.out.println(); // BFS // 2. 방문 배열 초기화하기 visited = new boolean[N+1]; // 3. 시작 노드 큐에 삽입하기 BFS(Start); System.out.println(); } public static void DFS(int Node) { System.out.print(Node + " "); // 현재 노드 출력하기 visited[Node] = true; // 현재 노드 방문 기록하기 // 인접한 미방문 노드로 DFS 실행하기 for(int i: A[Node]) { // 현재 노드의 엣지들 if (!visited[i]) { DFS(i); } } } public static void BFS(int Node) { Queue<Integer> queue = new LinkedList<Integer>(); queue.add(Node); // 시작 노드 큐에 삽입하기 visited[Node] = true; // 시작 노드 방문 기록하기 // 인접한 미방문 노드로 BFS 실행하기 while(!queue.isEmpty()) { // 큐에서 현재 노드 가져와서 출력하기 int new_Node = queue.poll(); System.out.print(new_Node + " "); for(int i: A[new_Node]) { // 현재 노드의 엣지들 if(!visited[i]) { queue.add(i); // 인접한 미방문 노드 큐에 삽입하기 visited[i] = true; // 인접한 미방문 노드 방문 기록하기 } } } } }