[백준] [15649] N과 M (1) (JAVA) (백트래킹)

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

15649번: N과 M (1)

---

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

512 MB

97373

61958

39904

62.690%

문제

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

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

입력

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

출력

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

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

---

※ JAVA 코드 (N과 M (1))

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

public class Main {
    public static int N, M;

    public static int[] a;
    public static boolean[] visit;
    public static List<Integer> lst;

    public static void main(String [] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        lst = new ArrayList<>();
        /* input */
        st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        a = new int[N + 1];
        visit = new boolean[N + 1];

        for(int i = 1; i <= N; i++) { a[i-1] = i; }

        solve(0, 0);
    }

    public static void solve(int idx, int cnt) {
        if(cnt == M) {
            for(int i = 0; i < M; i++) {
                System.out.print(lst.get(i) + " ");
            }
            System.out.println();
            return;
        }

        for(int i = idx; i < N; i++) {
            if(visit[i] == true) {
                continue;
            }
            visit[i] = true;
            lst.add(a[i]);
            solve(idx, cnt + 1);
            visit[i] = false;
            lst.remove(lst.size()-1);
        }
    }
}

---

※ 생각정리 (N과 M (1))

백트래킹이란 퇴각검색이라고도 하며, 일정방향으로 탐색을 진행하다가 더이상 해당 방향으로 탐색할 필요가 없을때 적당한 지점까지 퇴각후 다시 탐색을 이어나가는 방식을 뜻한다.

백트래킹을 하기전 DFS등의 탐색알고리즘을 선행할 필요가 있다. 이는 재귀 알고리즘에 대한 상당히 깊은 지식이 필요함을 뜻한다.

 

[DFS 알고리즘 선행]

 

dfs

 

깊이 우선 탐색 알고리즘을 보면, 현재 진행방향의 가장 깊은 곳까지 탐색하며 모든 노드를 방문한다.

 

그럼 본격적으로 N과 M문제를 생각해보자!

예제에 나온 N = 4, M = 2 인 경우를 예로 들어 문제를 해결할 수 있다.

1. 주어진 수 = { 1, 2, 3, 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}

 

backtraking

 

재귀를 통해 만들어지는 과정을 나타내 보았다. 처음 접했을 때 가장 이해가 안됬던 부분이 재귀였던 만큼 재귀를 기반으로 풀어지는 백트래킹은 문제 해결보다 해결과정에 중점을 두어 공부해야 한다.

 

코드설명 및 재귀 이해질문은 댓글 ~

 

- 새벽 코딩 -