[알고리즘 ] 백준 15649

layout: post
title: "백준 15649 N과M(1)"
date: 2022-02-17T00:00:00-00:00
author: sangyeop
categories: Algorithm

백준 15649 N과 M(1)

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

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

실패

• 반복문과 메서드 재귀호출을 이용하여StringBuilder에 숫자를 추가한다. 이후 String으로 변환한 뒤 다시 반복문을 이용해서 특정 숫자(문자)가 포함 되어 있는지 검사하여 중복 검사를 진행하고, 포함되어 있지 않은 숫자라고 하면 StringBuilder에 추가 한뒤 마지막에 ArrayList<String>으로 저장해주고 마지막에 이를 출력해주는 식으로 구현하려고 했으나실패하였다.

성공

백트랙킹이 무엇인지 찾아보고나서 문제를 해결 할 수 있었다. 필요한 내용은 이러하다

• 메서드 재귀호출

• 값을 저장할 배열

• 지나간 노드인지 검사할 수 있는 배열

import java.util.Scanner;

public class Baekjoon15649 {
    public static int N;
    public static int M;
    public static int[] numberLists;								// 숫자를 저장할 배열
    public static boolean[] isVisits;								// 방문한 노드인지 검사할 배열

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        N = scanner.nextInt();
        M = scanner.nextInt();

        numberLists = new int[M];		// M개 숫자를 뽑기 때문에 숫자 저장 배열 크기 또한 M
        isVisits = new boolean[N];	// 숫자 자리수가 N개 이므로 노드의 수도 N개 
				int depth = 0;							// 노드 트리의 깊이 ex) 1 - 2 - 3 - 4 이면 트리의 깊이는 0 - 1 - 2 - 3 이다

        backTracking(depth);
    }
    public static void backTracking(int depth) {
      	// 탐색 깊이 = M 이면 배열에 저장된 수를 출력해냄
        if (depth == M) {
            for (int number : numberLists) {
                System.out.print(number + " ");
            }
            System.out.println();
            return;
        }

        for (int i = 0; i < N; i++) {
            if (!isVisits[i]) {									// 아직 방문하지 않았다면
                isVisits[i] = true;							// 방문으로 체크하고
                numberLists[depth] = i + 1;			// 해당 깊이에 해당하는 인덱스를 배열 값에 i+1 부터 저장
                backTracking(depth + 1);				// 해당 노드 아래 깊이에 있는 노드를 탐색하기 위해 재귀 호출
                isVisits[i] = false;						// 모두 탐색했으면 방문 값들을 초기화
            }
        }
    }
}

알고 나면 단순한 방법이지만, 설명을 보기 전까지는 문제 풀이에 대한 감 조차 잡기가 어려웠다. 잊어버리지 않도록 반복해서 숙달할 필요가 있어보인다.