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

문제 링크

15650번: N과 M (2)

 

www.acmicpc.net

---

주의사항

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

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

---

문제 설명

---

접근 방법

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

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

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

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

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

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

• current는 현재 몇 번째 수열을 저장하였는지 표시하는 매개변수입니다.
• curNum은 오름차순으로 정렬되므로 수열에 들어갈 수 있는 최소 값입니다.
• for문에 범위를 curNum을 이용하여 범위를 조정하여서 오름차순으로 재귀를 진행되도록 하였습니다.
• current의 값이 길이 M과 동일하면 수열 값을 저장한 배열 result를 System.out.println()를 사용하여 출력하였습니다.

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	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());
    	result = new int[M];
    	backTracking(N, M, 0, 1);	
    	br.close();
	}
	public static void backTracking(int N, int M, int current, int curNum) {
   	 //-----------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=curNum;i<=N;i++) {
			result[current] = i;
			backTracking(N, M, current+1, i+1);
		}
		return;
	}
}