본문 바로가기
Computer Science/알고리즘 문제

C - [백준 15649, 15650] N 과 M 시리즈 정복하기 (feat. 백트래킹, 순열)

by rnasterofmysea 2025. 1. 3.
반응형

참조 포스트

 

2024.12.30 - [Computer Science/자료구조 & 알고리즘] - [자료구조 & 알고리즘] 백트래킹 (feat. DFS, 재귀)

 

[자료구조 & 알고리즘] 백트래킹 (feat. DFS, 재귀)

DFS2024.12.19 - [Computer Science/자료구조 & 알고리즘] - [자료구조 & 알고리즘] 그래프 + DFS [자료구조 & 알고리즘] 그래프 + DFS그래프에 대해 기초부터 차근차근 학습해보겠습니다. 그래프는 DFS와 BFS를

rnasterofmysea.tistory.com

 

 

백트래킹의 기본 문제는 N과 M 문제는 (1)~(12)등 여러가지 문제가 존재하는데,

BOJ_15649,  BOJ_15650 두 문제만 재대로 이해해도 나머지 문제를 해결하는 데에 전혀 어려움이 없었습니다.

 

 

 


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

 

[BOJ_15649] N과 M (1)

 

문제 설명:
자연수 N과 M이 주어졌을 때, 1부터 까지 자연수 중에서 길이가 M인 수열을 모두 구하는 문제입니다.
각 수열은 중복 없이 순서를 지켜서 출력해야 합니다.

예제 입력 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

 

 

Checkpoint

해당 문제를 통해 백트래킹에서 DFS가 어떻게 사용되는지 느낌을 받을 수 있는 좋은 문제라고 생각합니다.

DFS 알고리즘과 이를 구현하기 위한 변수들의 역할을 이해하면 문제를 쉽게 풀 수 있습니다. 특히, 백트래킹을 올바르게 구현하려면 visited 배열의 역할이 매우 중요합니다.

 

visited 배열은 각 숫자가 이미 사용되었는지를 기록하는 데 사용됩니다.

  • 역할: 중복된 숫자가 선택되지 않도록 보장합니다.
  • DFS 탐색 과정에서 선택된 숫자는 visited 배열에서 1로 표시됩니다. 이후, 다른 숫자를 선택하고 탐색을 마치면 백트래킹 단계에서 다시 0으로 초기화됩니다.
  • 이 과정은 다른 조합을 탐색할 수 있도록 현재 상태를 되돌리는 핵심 메커니즘입니다

2024.12.19 - [Computer Science/자료구조 & 알고리즘] - [자료구조 & 알고리즘] 그래프 + DFS

2024.12.30 - [Computer Science/자료구조 & 알고리즘] - [자료구조 & 알고리즘] 백트래킹 (feat. DFS, 재귀)

 

두 포스트를 참고해주세요!

 

기본 DFS가 아닌 백트래킹을 재대로 구현하기 위해서는 visited 배열의 역할이 중요합니다. 

구현 코드

#include <stdio.h>

int N, M;
int arr[8]; // 순열을 저장할 배열
int visited[9]; // 방문 여부를 체크할 배열

void dfs(int depth) {
    if (depth == M) { // M개의 숫자를 모두 선택한 경우
        for (int i = 0; i < M; i++) {
            printf("%d ", arr[i]);
        }
        printf("\n");
        return;
    }

    for (int i = 1; i <= N; i++) {
        if (!visited[i]) { // 아직 방문하지 않은 숫자인 경우
            visited[i] = 1; // 방문 표시
            arr[depth] = i; // 순열 배열에 추가
            dfs(depth + 1); // 다음 숫자 선택
            visited[i] = 0; // 백트래킹: 방문 표시 해제
        }
    }
}

int main() {
    scanf("%d %d", &N, &M);
    dfs(0); // DFS 시작
    return 0;
}

 

코드 해설

1️⃣ 변수 선언

int N, M;      // 입력값 N과 M
int arr[8];    // 현재 선택된 숫자를 저장할 배열
int visited[9]; // 숫자의 방문 여부를 체크할 배열
  • M은 최대 8이므로 arr 배열 크기를 8로 설정.
  • 1부터 N까지의 숫자 방문 여부를 저장하기 위해 visited 배열 크기를 N+1로 설정.

2️⃣ DFS 함수

void dfs(int depth) {
    if (depth == M) { // M개의 숫자를 모두 선택한 경우
        for (int i = 0; i < M; i++) {
            printf("%d ", arr[i]);
        }
        printf("\n");
        return;
    }
  • depth는 현재까지 선택한 숫자의 개수를 나타냅니다.
  • depth == M이면 M개의 숫자를 모두 선택한 것이므로 arr 배열을 출력하고 종료.
    for (int i = 1; i <= N; i++) {
        if (!visited[i]) { // 아직 방문하지 않은 숫자인 경우
            visited[i] = 1; // 방문 표시
            arr[depth] = i; // 순열 배열에 추가
            dfs(depth + 1); // 다음 숫자 선택
            visited[i] = 0; // 백트래킹: 방문 표시 해제
        }
    }
}
  • 1부터 N까지의 숫자를 순회하며 아직 선택되지 않은 숫자만 선택.
  • 선택한 숫자는 visited[i] = 1로 방문 표시를 하고, 배열 arr에 저장.
  • dfs(depth + 1)로 다음 숫자를 선택.
  • 백트래킹 단계에서 visited[i] = 0으로 방문 여부를 초기화.

3️⃣ 메인 함수

int main() {
    scanf("%d %d", &N, &M);
    dfs(0); // DFS 시작
    return 0;
}
  • 사용자로부터 N과 M을 입력받고, 깊이 0에서 DFS를 시작합니다.

동작 원리

  1. DFS는 현재 선택 가능한 숫자를 하나씩 선택하며 순열을 생성합니다.
  2. 선택된 숫자는 visited 배열로 중복 선택을 방지합니다.
  3. M개의 숫자를 모두 선택하면 해당 순열을 출력하고, 이전 단계로 돌아가 다른 경우를 탐색합니다 (백트래킹).

예제 실행

입력

3 2

출력

1 2
1 3
2 1
2 3
3 1
3 2

핵심 포인트

  • 백트래킹: 선택한 숫자를 취소하고 이전 상태로 돌아가 다른 숫자를 탐색.
  • visited 배열: 중복 선택을 방지.
  • 순열 탐색: 모든 경우의 수를 탐색하기 위해 DFS 활용.

시간 및 공간 복잡도

  • 시간 복잡도: O(N^M)
    모든 순열을 탐색해야 하므로 N개의 숫자에서 M개를 선택하는 경우의 수.
  • 공간 복잡도: O(M)
    최대 M개의 숫자를 저장하는 배열과 방문 체크 배열.

 

 

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

Checkpoint

 

해당 문제는 따로 설명하지 않고 예제를 바로 비교하면서 차이점을 파악하겠습니다. 차이점만 파악이 되었다면 상단의 N과 M(1) 문제에 코드를 조금만 변형해도 해결할 수 있습니다.

 

N과 M (1) 문제와 N과 M (2) 문제의 핵심 차이는 다음과 같습니다:

  • N과 M (1): 숫자의 순서를 고려하며 모든 순열을 출력합니다. 예를 들어, (1,2)와 (2,1) 모두 출력됩니다.
  • N과 M (2): 중복된 순서를 제거하여 (1,2)만 출력하며, (2,1)은 출력하지 않습니다. 즉, 조합만 출력합니다.

해결 접근

중복 값을 제거하기 위해 결과값을 배열에 저장하고 이를 비교할 수도 있지만, 이는 비효율적일 수 있습니다.
따라서 백트래킹에서 중복 조건을 자연스럽게 피할 수 있는 방법을 사용합니다.

중복 조건 분석

조합에서 중복이 발생하는 조건은 이전 숫자보다 작은 숫자를 선택할 때입니다.
예를 들어, 1, 2 일 경우 2가 1보다 크니까 허용되지만,

                  2,1 의 경우, 1이 2보다 작으므로 중복입니다.

 

 

즉 dfs 함수 내부의 조건 하나만 추가하면 해결됩니다.

    for (int i = 0; i < N; i++) {
        if (visited[i] == 0) {
            // 현재 숫자가 이전에 선택된 숫자보다 작으면 제외
            if (depth > 0 && arry[depth - 1] > i + 1) {
                continue;
            }

구현 코드

/*
BOj_15650_N과M(2)
https://www.acmicpc.net/problem/15650
*/
#include <stdio.h>

int M, N;
int visited[8];
int arry[8];

void dfs(int depth) {
    if (depth == M) {
        for (int i = 0; i < M; i++) {
            printf("%d ", arry[i]);
        }
        printf("\n");
        return;
    }

    for (int i = 0; i < N; i++) {
        if (visited[i] == 0) {
            // 현재 숫자가 이전에 선택된 숫자보다 작으면 제외
            if (depth > 0 && arry[depth - 1] > i + 1) {
                continue;
            }

            arry[depth] = i + 1;
            visited[i] = 1;
            dfs(depth + 1);
            visited[i] = 0; // 백트래킹
        }
    }
}

int main() {
    scanf("%d %d", &N, &M);
    dfs(0);
    return 0;
}

 

 

주요 코드 설명

1. 전역 변수 선언

int M, N;
int visited[8];
int arry[8];
  • M: 선택할 숫자의 개수.
  • N: 숫자의 범위 (1부터 N).
  • visited[8]: 방문 여부를 나타내는 배열. 특정 숫자가 이미 선택되었는지 확인하는 데 사용됩니다.
  • arry[8]: 선택된 숫자를 저장하는 배열.

2. DFS 함수 구현

void dfs(int depth) {
    if (depth == M) {
        for (int i = 0; i < M; i++) {
            printf("%d ", arry[i]);
        }
        printf("\n");
        return;
    }
  • depth: 현재까지 선택된 숫자의 개수를 나타냅니다.
  • 기저 조건:
    • depth == M인 경우 M개의 숫자를 선택한 상태이므로 이를 출력하고 함수를 종료합니다.

3. 숫자 선택 반복문

    for (int i = 0; i < N; i++) {
        if (visited[i] == 0) {
            if (depth > 0 && arry[depth - 1] > i + 1) {
                continue;
            }

            arry[depth] = i + 1;
            visited[i] = 1;
            dfs(depth + 1);
            visited[i] = 0; // 백트래킹
        }
    }
  • i: 현재 숫자를 의미하며, 1부터 N까지의 숫자를 탐색합니다.
  • visited[i] == 0: 숫자 i+1이 아직 선택되지 않은 경우에만 선택 가능합니다.

중복 조건 제거

if (depth > 0 && arry[depth - 1] > i + 1) {
    continue;
}
  • 현재 선택된 숫자(i + 1)가 이전 숫자보다 작으면 제외합니다.
    이를 통해 (2,1)과 같은 중복 순서를 방지하고 (1,2)만 출력하도록 제한합니다.

백트래킹

visited[i] = 1;
dfs(depth + 1);
visited[i] = 0;
  • 숫자를 선택한 후, 다음 단계로 이동합니다.
  • 이동 후에는 선택했던 숫자를 해제(visited[i] = 0)하여 다른 경우의 조합을 탐색할 수 있도록 합니다.

4. 메인 함수

int main() {
    scanf("%d %d", &N, &M);
    dfs(0);
    return 0;
}
  • 입력값 N과 M을 받아 DFS를 호출합니다.
  • dfs(0)은 깊이 0부터 탐색을 시작합니다.

실행 결과

입력 예시

4 2

출력 예시

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

 

 

 

해당 두 문제를 이해하셨다면 다른 N과 M 백트래킹 문제는 순열을 직접 입력받거나 ,중복값을 허용하는 등의 간단한 변형만 있어서 쉽게 해결할 수 있습니다.!

 

 

 

💡 도움이 되셨다면 댓글과 공감 부탁드립니다! 😊
📌 더 많은 알고리즘 풀이와 프로그래밍 자료는 블로그에서 확인하세요!
✉️ 문의나 피드백은 댓글이나 이메일로 남겨주세요.

 

반응형

'Computer Science > 알고리즘 문제' 카테고리의 다른 글

C - [백준 1987] 알파벳 (feat. 백트래킹, DFS & 최장거리 탐색)  (0) 2025.01.05
C - [백준 9663] N-Queen (feat. 백트래킹, DFS)  (4) 2025.01.04
C - [백준 2447] 별 찍기 -10 (feat. 재귀)  (0) 2025.01.02
C - [백준 1992] 쿼드트리 (feat. 재귀)  (1) 2025.01.01
C - [백준1074] Z (feat. 재귀적 사고, 분할정복)  (2) 2024.12.31

관련글

티스토리툴바