(Baekjoon) backtracking - (1) 로또

https://www.acmicpc.net/problem/6603

6603번: 로또

 

7을 입력하고 

 

1 - 2 - 3 - 4 - 5 - 6 - 7

로 끝까지 dfs로 들어간후 한단계씩 backtracking하는것

 

visited로 방문을 확인할 필요가 없는것은 오름차순이기때문이다.

2-3-5-6-1-4 일경우에는 visited로 

for(i = v+1)이 아닌 for( i = 0) 으로 0부터 탐색을 전부해줘야한다.

package backtracking;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.nio.Buffer;
import java.util.Scanner;

public class _6603 {
    static Scanner sc = new Scanner(System.in);
    static int n;
    static int number[] = new int[13];
    static int count;
    static StringBuffer bf = new StringBuffer();
    public static void dfs(int a,String str){

        if(count == 6){
            bf.append(str+"\n"); // 6개가 채워지면은 bf에다가 넣고 엔터
        }
        else{
            for (int i = a + 1; i < n; i++) { // 1 - 2 - 3 - 4 - 5 - 6 - 7 (오름차순으로 되어있기 떄문에) a+1부터 n까지
                count++;
                dfs(i,str+number[i]+" ");  // 다음꺼에 넘겨주기
            }
        }
    
        count--;    // 끝나면 지금까지 더해졌던 count를 --해야지 그전에서 실행됨

    }
    public static void main(String args[]){

        while((n = sc.nextInt()) != 0){
        
            for (int j = 0; j < n; j++) {
                number[j] = sc.nextInt();
            }

            for (int i = 0; i < n; i++) { // 1-2-3-4-... 백트래킹
                count=1;                  // 2-3-4-5-... 백트래킹
                dfs(i,number[i]+" ");     // 3-4-5-6.... 백트래킹
            }
            bf.append("\n");

        }
        System.out.println(bf.toString());

    }

}

 

 

 

 

백준문제풀이Github : 

https://github.com/sdk0213/baekjoon-study

sdk0213/baekjoon-study