[백준, 15649번] N과 M(1) (백트래킹, Java)

문제설명

입력 & 출력

나의 풀이

이번 "백준 - N과 M (1)" 문제는 1부터 N까지의 자연수 중에서 길이 M인 순열을 모두 구하는 문제입니다.

 

문제 접근 방식

1. 순열 생성

• 길이 M의 순열을 구성해야 하므로, 각 숫자가 중복되지 않도록 방문 여부를 체크.

2. 백트래킹

• 현재까지의 순열 상태에서 가능한 숫자를 추가하여 재귀적으로 탐색.

3. 종료 조건

• 순열의 길이가 M이 되면 결과를 출력.

순열(Permutation)이란, 주어진 원소들을 순서를 고려하여 배열한 경우의 수

전체 코드

 

이번 문제는 N과M이 주어졌을 때 1에서 N의 수에서 M길이의 순열을 출력하는 문제입니다. 

 

먼저 방문 여부(visited)와 순열을 저장할 배열(Permutation), 결과를 출력할 StringBuilder는 자주 초기화되기 때문에 static으로 선언하여 관리해줍니다.

 

문제에서 1~N의 수에서 순열을 구하는 것이기 때문에 방문여부는 +1을 추가하여 1부터 시작하도록 합니다.

 

순열 생성 함수 (getPermutation)

 

재귀함수를 사용할 때는 종료 시점이 중요하기 때문에 이 문제에서는 순열이 완성된다면 종료하고 다음으로 넘어가야 합니다. 따라서 순열이 완성된다면 결과를 출력하는 StringBuilder에 순열을 추가해주고 return해줍니다.

 

문제의 순열은 1~N이기 때문에 반복문 조건을 설정해주고, 방문 하지 않았다면 우선 방문처리(true)를 해주고, 순열을 저장하는 배열에 수를 재귀호출하여 순열을 계속해서 만들어줍니다.

 

그리고 그 후, 해당 수를 다시 다른 숫자와 조합할 수 있도록 방문 처리를 되돌려주기 위해 백트래킹을 해줍니다. 백트래킹을 통해 더 이상 진행할 수 없을 때 이전 상태로 돌아가서 다른 경로를 탐색하게 됩니다