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

문제 링크

15652번: N과 M (4)

 

www.acmicpc.net

---

주의사항

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

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

---

문제 설명

---

접근 방법

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

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

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

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

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

• 수열을 저장할 배열 result을 만들었습니다.
• BufferedReader를 사용하여 입력 값을 받았습니다.
• StringTokenizer를 사용하여 띄어쓰기 기준으로 숫자를 나누었습니다.
• M길이의 중복을 허용하는 비내람차식 수열을 구하는 함수 backTracking을 만들었습니다.
• System.out.println()을 사용하여 StringBuilder를 출력하였습니다.

• current는 현재 몇 번째 수열을 저장하였는지 표시하는 매개변수입니다.
• curNum은 비내림차순으로 for문에 범위를 조정할 때 사용하는 매개변수입니다.
• for문을 통해 backTracking 함수를 재귀하여 수열의 값들을 result에 저장하였습니다.
• current의 값이 길이 M과 동일하면 수열 값을 StringBuilder에 저장하였습니다.

결과 코드

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