[백준] 5568번 카드 놓기 JAVA (자바) 풀이

문제 5568  (백트래킹)

 

 : 카드 n장 (4 ≤ n ≤ 10)
   각 카드 1이상 99이하의 정수

 : 카드 k장 (2 ≤ k ≤ 4) 선택 후 가로로 나란히 정수를 만들기

 : 만들 수 있는 정수는 모두 몇 가지일까?

 

[입력]

 

: 첫째 줄에 n, 둘째 줄에 k
: 셋째 줄 ~ n개 줄에는 카드에 적혀있는 수

 

[출력]

 

: 만들 수 있는 카드 개수

 

 

[과정]

 

조합 중복 방지 vs 결과 중복 방지

• 조합 중복 (백트래킹으로 해결)
  
  조합 중복 방지란 (1,1)이 아닌 (1,2)처럼 서로 다른 조합을 말한다 
  
  
• 결과 중복 (hashset으로 해결)
  
  결과 중복 방지란 (1,2)와 (2,1)을 같은 값으로 처리하는 것을 말한다 

 

 

 [코드]

import java.io.*;
import java.util.*;
public class Main{
    static int N,k,arr[];
    static HashSet<String> card = new HashSet<>(); 
    static boolean visit[];
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N=Integer.parseInt(br.readLine());
        k=Integer.parseInt(br.readLine());
        arr=new int[N];
        visit=new boolean[N];
       
        
        for(int i=0; i<N; i++){
            arr[i]=Integer.parseInt(br.readLine());
        }
        
        back(0,"");
        System.out.println(card.size());
        
    }
    
    public static void back(int depth, String a){
        if(depth==k){
           card.add(a);
            return;
        }
        
        for(int i=0; i<N; i++){
            if(!visit[i]){
                visit[i]=true;
                back(depth+1,a+arr[i]);
                visit[i]=false;
            }
        }
    }
}

 

 [해설]
     

 :  static int N,k,arr[];  입력받기
    static HashSet<String> card = new HashSet<>();  결과 중복 방지
    static boolean visit[];  방문기록

 

 :  N=Integer.parseInt(br.readLine());  첫번째줄
    k=Integer.parseInt(br.readLine());  두번째줄
    arr=new int[N];  세번째줄
    visit=new boolean[N];  방문기록
       
        
 :  for(int i=0; i<N; i++){
            arr[i]=Integer.parseInt(br.readLine());  세번째줄 차례로 입력
    }
        
        back(0,"");  백트래킹 시작
        System.out.println(card.size());  hashset 크기 출력
        
    }
    
 : public static void back(int depth, String a){  깊이, 문자로 숫자 붙이기
        if(depth==k){  깊이가 k만큼 되면 종료
           card.add(a);  hashset에 만든 숫자배열 추가
           return;
        }
        
        for(int i=0; i<N; i++){ 
            if(!visit[i]){  방문하지 않은 것들만
                visit[i]=true;  방문처리
                back(depth+1,a+arr[i]);  층 바꿔서 다음 인덱스에 들어올 숫자 백트래킹 반복
                visit[i]=false;
            }
        }
    }


 

 

이제 풀어보러 갈께요 :)

 

 

 

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

5568번: 카드 놓기

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *