[Java] 백준 #15649 : N과 M (1)

문제분류

백트래킹

문제

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

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

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

입력
첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

예제 입력 1

3 1

예제 출력 1

1
2
3

예제 입력 2

4 2

예제 출력 2

1 2
1 3
1 4
2 1
2 3
2 4
3 1
3 2
3 4
4 1
4 2
4 3

예제 입력 3

4 4

예제 출력 3

1 2 3 4
1 2 4 3
1 3 2 4
1 3 4 2
1 4 2 3
1 4 3 2
2 1 3 4
2 1 4 3
2 3 1 4
2 3 4 1
2 4 1 3
2 4 3 1
3 1 2 4
3 1 4 2
3 2 1 4
3 2 4 1
3 4 1 2
3 4 2 1
4 1 2 3
4 1 3 2
4 2 1 3
4 2 3 1
4 3 1 2
4 3 2 1

Solution

• N과 M을 각각 입력받습니다.

• 각 숫자의 방문여부를 확인하는 visited(boolean[])을 N 크기로 초기화해줍니다.

• 재귀탈출 조건 충족시 만들어지는 순열을 저장할 임시공간인 순열(int[])을 M 크기로 초기화해줍니다.

• getPermutation(int idx)는 순열의 각 자리수(순열[idx])에 들어올 수 있는 수를 지정하는 역할을 합니다.

• 만약, idx가 순열의 크기(M)와 같아지면 순열은 다 채워진 것이므로, for문을 이용해 StringBuilder sb에 순열을 추가하고, return; 해줍니다.

• 그 아래에서는, for문을 활용해 각 자리에 들어올 숫자들을 지정합니다.

• 만약, visited[i]가 true(방문했다면)라면, 이번 루프에서 i는 순열[idx]의 값이 될 수 없으므로, continue;를 통해 건너뜁니다.

• visited[i]가 false(방문하지 않았다면)라면, visited[i]를 방문처리(true) 해주고, 순열의 idx 자리에 숫자를 넣습니다. (이때, 들어가는 숫자는 1~N이므로, i+1을 해주어야 합니다.)

• 이번 자리수(idx)를 지정했다면, 다음 자리 수 지정을 위해, idx를 1 증가시켜서 getPermutation(idx + 1);와 같이 재귀함수를 호출합니다.

• 재귀를 통해 방문을 마쳤다면 i의 다음 값 루프를 위해 i를 방문해제 처리(false) 합니다.

코드

import java.util.*;
import java.io.*;

public class Main {
    static int N, M;
    static boolean[] visited;
    static int[] 순열;
    static StringBuilder sb = new StringBuilder();

    static void getPermutation(int idx) {
        if (idx == M) {
            for (int i = 0; i < M; i++) {
                sb.append(순열[i]).append(" ");
            }
            sb.append("\n");
            return;
        }

        for (int i = 0; i < N; i++) {
            if (visited[i])
                continue;
            visited[i] = true;
            순열[idx] = i + 1;
            getPermutation(idx + 1);
            visited[i] = false;
        }
    }

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);

        // N과 M 입력받기
        N = sc.nextInt();
        M = sc.nextInt();

        // 각 배열 초기화
        visited = new boolean[N];
        순열 = new int[M];

        // 인덱스 0에서 재귀함수 시작
        getPermutation(0);

        // StringBuilder에 추가된 모든 순열 출력
        System.out.println(sb);
    }
}

느낀 점

최근 스터디를 시작하면서, 순열과 백트래킹 기법을 처음 접하게 되었습니다.

스터디 첫 날이었던 어제는 정신없이 몇 시간동안 문제만 보고 있다보니 도저히 풀리지 않아서, 다른 블로거의 게시글 중 순열과 백트래킹 부분을 찾아 보고 나서 풀이를 진행했습니다.

그 자료에 있던 예시 중 하나가 "N과 M" 문제였습니다.

방문체크하면서 불필요한 경우를 제외시키는 저 방법을 무작정 외워서 사용해보았는데, 점점 이해가 되기 시작했습니다.
많이 익숙해지고 나서는 기존에는 감도 잡히지 않던 순열과 백트래킹 문제들의 해결방법들을 떠올릴 수 있었습니다.

기존에 알고리즘 공부할 때는 조금하다가 어려워, 안해~ 하고 포기하곤했는데, 이번 학습을 통해서 이론과 예시를 충분히 외우거나 학습하고 문제를 여러번 풀다보면 실력이 금방금방 늘 것 같다고 느꼈습니다.

요약 == 순열 뽑는 방법 저거 외워서 편했다. 앞으로도 많이 외우고 많이 풀자 ㅎ