[백준 / BOJ] 15649 : N과 M (1) (JAVA)
문제
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
- 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
입력
첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
출력
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
전체 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
public class Main {
static int N;
static int M;
static LinkedList<Integer> list = new LinkedList<>();
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
N = Integer.parseInt(input[0]);
M = Integer.parseInt(input[1]);
func(0);
}
public static void func(int k) {
if (k == M) {
for (Integer i : list) {
System.out.print(i + " ");
}
System.out.println();
return;
}
for (int i = 1; i <= N; i++) {
if (!list.contains(i)) {
list.add(i);
func(k+1);
list.removeLast();
}
}
}
}
풀이
백트래킹을 이용한 기본적인 문제다.
코드의 아이디어는 유튜브 알고리즘 강의를 참고하였다.
재귀 방식으로 백트래킹을 통해 가능한 모든 수열을 출력하는 방식으로 구현하였다.
핵심 알고리즘 부분은 func 메소드인데, 먼저 패러미터인 k는 list의 size이자, 수열의 현재 길이를 의미한다.
(배열로 구현하게 되면 배열의 인덱스를 의미하게 된다.)
k가 수열의 최종 길이인 M에 도달하게 되면 list의 원소들을 출력하여 수열을 출력한다.
func 메소드에서 재귀적 호출을 실행하는 부분은 바로 if 문 다음에 나오는 for 문이다.
여기서 for 문 안의 i가 의미하는 바는 가능한 숫자의 범위이다.
처음 func 메소드를 호출할 때 인자로 0을 넣고 있는데, 이는 리스트의 첫번째(수열의 첫번째) 자리에 들어갈 수를 의미한다.
여기서 1부터 N까지의 수가 가능하기 때문에, 첫번째 자리에 올 수 있는 수를 for 문을 통해 돌려주는 것이다.
그리고 !list.contains(i)라는 조건문을 이용한 다음 리스트에 삽입 -> k+1 재귀 호출 -> 리스트에서 삭제와 같은 로직으로 진행한다.
여기서 list.contains는 이미 사용한 원소를 제거하기 위한 조건문이다. 만약 list.contains(i)가 true라면 해당 수는 이미 사용했던 값이기 때문에 중복 없이 고른다는 문제 조건에 위배된다. 따라서 !list.contains(i)를 이용해 중복을 제거하는 것이다.
(이를 배열로 구현한다면, isUsed와 같은 배열을 이용 가능하다)
그 이후 k+1을 패러미터로 func를 재귀 호출하게 되는데, 이는 현재 "상태"에서 다음 자리(k+1)에 올 수를 결정하는 것이다.
여기서 현재 상태라는 의미는 k번째 자리의 값이 결정된 상태를 의미한다. 만약 func(0)로 처음 호출된 상태면, 여기서의 현재 상태는 리스트의 첫번째 자리로 1, 2, 3, 4가 선택된 4가지 상태가 존재할 수 있을 것이다. 그리고 예를 들어 첫번째 상태로 "2"가 선택된 상태에서는 func(1)이 호출되고 두번째 상태로 1, 3, 4가 선택되는 3가지 상태가 존재할 수 있다.
이런식으로 각 상태에서 가능한 경우의 수를 모두 탐색하여 출력하면 문제의 조건에 맞게 수열을 출력할 수 있게 된다.
이번에 처음 백트래킹 알고리즘을 공부하였는데, 재귀 호출을 사용하기 때문에 알고리즘을 정확히 이해하지 않고서는 코드를 구현하기가 어려웠다. 특히 재귀 호출 부분은 직접 숫자를 대입해가며 머리 속으로 또는 필기를 통해 시뮬레이션 하는 과정이 많이 도움이 되었다.
또한 배열을 이용한 풀이와, 리스트를 이용한 풀이를 각각 해보면서 재귀 호출 과정을 어느 정도 이해하게 되었다.
N과 M 문제 시리즈는 BOJ에서 백트래킹을 연습하는데 대표적인 문제로, 앞으로도 더 많은 문제들을 학습하면서 백트래킹을 익혀보도록 해야겠다.