[BOJ - JAVA] 6603 - 로또(백트래킹, 재귀)

# 주소

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

6603번: 로또

 

# 문제

 

# 문제 해설 및 코드 리뷰

import java.util.*;
public class Main{
    public static int[] arr, ans;
    public static boolean[] visit;
    public static int n;
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        
        while(true) {
            n = scan.nextInt();
            if(n == 0) {
            	break;
            }
            visit = new boolean[n];
            arr = new int[n];
            ans = new int[n];
            for(int i = 0	; i < n; i++){
                arr[i] = scan.nextInt();
            }
            dfs(0,0);
            System.out.println();
        }
    }
    public static void dfs(int start,int depth){
        if(depth == 6){
            for(int i = 0; i < 6; i++){
                System.out.print(ans[i] + " ");
            }
            System.out.println();
        }
        for(int i = start; i < n; i++){
            if(!visit[i]){
            	ans[depth] = arr[i];
                visit[i] = true;
                dfs(i + 1, depth + 1);
                visit[i] = false;
            }
        }
    }
}

 

 

 

백트래킹 문제입니다. 전 이걸 입력하면서 오류가 정~~~말 많이 나왔는데 아직도 이해가 잘 가지 않는군요...

dfs를 정의하는 코드랑 그 밑의 백트래킹 구문을 계속 수정하면서 답을 비교하는데, 이클립스에서는 정답이 맞게 나와도

50%쯤 올라가다가 틀렸다고 하더라고요.

그 이유도 사실 아직도 모릅니다.

 

문제에서 0을 입력하면 종료되게끔 나오도록 문제에 제기되어 있잖아요??

그래서 if(n == 0) break; 이렇게 제일 처음 썼는데도 자꾸만 이클립스에서 0을 입력하기도 전에 콘솔이 종료되서

적잖이 당황한 거도 있습니다.

한시간정도 고민한거같은데... 어떻게 끄적거리다 보니 정답은 맞췄지만 많이 찝찝한 문제였네요.

 

백트래킹은 제가 포스팅을 정말 많이 했기 때문에 자신있었던 문제였는데, 하도 오류가 나니까 다시 되짚어 봐야겠다고

생각한 문제였습니다.

 

문제 푸는 패턴은 늘 그랬듯이 똑같습니다. 조금 다른 점은 while문 안에서 입력을 받고 바로 재귀함수로 들어간다는 점이지요. 

 

감사합니다.