[백준] 단계별로 풀어보기(단계:14,백트래킹,JAVA)15649번, N과 M(1)

문제 링크

15649번: N과 M (1)

 

www.acmicpc.net

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

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

---

문제 설명

---

접근 방법

백트래킹이란 깊이 우선 탐색을 바탕으로 탐색 중 오답을 만나면 이전 분기점으로 돌아가서 다른 해결방법이 있는지 확인하고 더 이상 없으면 더 이전에 분기점으로 돌아가서 해결방법을 찾아보는 방식입니다.깊이 우선 탐색은 모든 경우의 수를 검색하게 되지만 백트래킹은 오답으로 판단될시 그에 해당하는 자식 노드들은 모두 무시하고 넘어가기 때문에 더욱 효율적으로 코드가 진행됩니다.

검은색 : 실행되지 않은 노드

빨간색 : 오답으로 판단한 노드

초록색 : 올바른 값이라고 판단한 노드

위에 그림처럼 부모노드가 틀리다고 판정되면 자식노드 무시하고 이전 분기점으로 돌아가서 확인하는 방식으로 코드가 전개되어 가는 방식입니다.

• 수열을 저장할 배열 result와 오답을 체크하기 위한 배열 check를 만들었습니다.
• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 사용하여 띄어쓰기 기준으로 숫자를 나누었습니다.
• M길이의 수열을 구하는 함수 backTracking을 만들었습니다.

• current는 현재 몇 번째 수열을 저장하였는지 표시하는 매개변수입니다.
• 재귀를 통해서 숫자를 사용하였다면 check배열에 true로 변경하고 사용하지 않았다면 false로 저장하였습니다.
• check배열을 통해서 숫자가 사용되었다면 오답으로 판정해 넘어가고 사용되지 않았다면 배열에 값을 저장하였습니다.
• current의 값이 길이 M과 동일하면 수열 값을 저장한 배열 result를 System.out.println()를 사용하여 출력하였습니다.

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	static boolean[] check;		//오답 확인 배열
	static int[] result;		//수열 값 저장 배열
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //BufferedReader를 통해 입력 값 받기
        //띄어쓰기 기준 나누기
    	StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        //----------입력값 저장 및 배열 초기화, 함수 실행--------
    	int N = Integer.parseInt(st.nextToken());
    	int M = Integer.parseInt(st.nextToken());
		check = new boolean[N];
		result = new int[M];
    	backTracking(N,M,0);
    	br.close();
	}
    //수열 출력하는 함수
	public static void backTracking(int N, int M,int current){
    //-----------current 값이 길이와 같을 때 결과 출력-------
		if(current==M) {
			for(int i=0;i<result.length;i++) 
					System.out.print(result[i] + " ");
			System.out.println();
			return;
		}
    //-----------backTracking을 통해 수열의 값 배열에 저장-------
		for(int i=0;i<check.length;i++) {
			if(!check[i]) {
				result[current] = i+1;
				check[i]=true;
				backTracking(N, M, current+1);
				check[i]=false;
			}
		}
		return;
	}
}