[BOJ/C++] 백준 15649번: N과 M (1)

Introduction

---

15649번: N과 M (1)

 

오늘 풀어볼 문제는 백준 15649번, N과 M (1)입니다. 자연수 N과 M이 주어질 때, 1부터 N까지의 자연수 중 중복 없이 M개를 고른 수열을 모두 구하는 코드를 짜는 게 오늘의 목표입니다. 입력과 출력은 아래와 같습니다.

입력	자연수 N, M (1 ≤ M ≤ N ≤ 8)
출력	한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력해서는 안된다. 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다.

 

이제 본격적으로 문제를 풀어보도록 하겠습니다. 글의 순서는 어떤 사고의 흐름으로 계획을 짰는지 서술하고, 손으로 끄적인 flowchart를 이쁘게 diagrams.net을 활용해 보여드릴 겁니다. 마지막으로는 source code를 통해 마무리할 것입니다. 정답지가 궁금하신 분들은 마지막 항목으로 바로 가셔도 무방합니다.

 

Planning

---

무지성으로 for문 사용하고 싶다.

 

처음 문제를 접했을 때는 조금 황당하지만 위와 같은 생각이 들었습니다. N이 row, M이 column을 결정하는 brute-force 문제에 해당해 보였습니다. 하지만 N, M 값이 정해지지 않은 상태에서 동적으로 for문을 할당하기에는 매우 귀찮기 때문에 매우 조금만 더 고급스럽게 문제를 풀어보기로 했습니다. 바로 재귀함수를 사용해 문제를 푸는 것입니다. 재귀적으로 문제를 접근하면 동적인 반복문과 같은 역할을 할 수 있습니다.

BFS와 DFS 중 어느 방법을 사용할지 고민하다가 우선 출력 기댓값을 생각해 봤습니다. 사전 순으로 증가하는 순서로 출력한다는 부분은 BFS/DFS 모두 가능합니다. 중복되는 수열을 여러 번 출력해서는 안되지만, 순서가 바뀌는 건 해당되지 않아 이 제약 조건 역시 BFS/DFS 모두 가능합니다.

출력 기댓값에서는 원하는 결과를 얻지 못해 다음으로는 BFS/DFS 고유의 특징을 생각해 봤습니다. 사실 이 문제는 모든 노드를 방문하면 되고, 경로마다 깊이도 같기 때문에 둘 중 어떤 방법을 사용해도 괜찮습니다. 그래서 저는 N, M이 모두 8일 때 그래프의 사이즈가 충분히 방대해질 수 있다고 생각했습니다. 또한, 최단거리 문제가 아닌데 BFS를 사용할 필요성을 느끼지 못해 결론적으로 DFS를 적용해 문제를 풀기로 결정했습니다.

 

Flowchart

---

아래는 문제를 풀기 위해 끄적인 flowchart의 예시입니다. Flowchart rule 같은 것들은 무시하고 임의로 그린 자료이니 참고용으로만 봐주시면 좋을 것 같습니다.

BOJ 15649 flowchart using dfs

 

Source Code

---

/**
 * @file q15649.cpp
 * @author YoungJ-Baek (qordudwls1@gmail.com)
 * @brief solution for BOJ #15649, https://www.acmicpc.net/problem/15649
 * @version 0.1
 * @date 2023-01-24
 *
 * @copyright Copyright (c) 2023
 *
 */
#include <iostream>
#define MAX 9

int N, M;           // two inputs, N(range of sequence), M(size of sequence)
int sequence[MAX];  // array for generated sequences
bool visited[MAX];  // array for checking dfs

void dfs(int cnt);

int main() {
  std::cin >> N >> M;
  dfs(0);
}

void dfs(int cnt) {
  if (cnt == M)  // array size reaches maximum size
  {
    for (int index = 0; index < M; index++) std::cout << sequence[index] << ' ';
    std::cout << '\n';
    return;
  } else {
    for (int index = 1; index <= N; index++) {
      if (visited[index] == false) {
        visited[index] = true;
        sequence[cnt] = index;
        dfs(cnt + 1);
        visited[index] = false;
      }
    }
  }
}

 

Appendix

---

사실 이 문제를 풀면서 가장 난관은 알고리즘을 짜는 시간이 아니었습니다. 분명 깔끔하게 잘 풀었다고 생각했는데 제출만 하면 시간 초과!!!! 녀석이 절 반겨줬습니다. 처음에는 연습용으로 추가한 주석들이 문제인가? 하는 이상한 생각으로 주석들을 지우고 제출해 봤습니다. 당연히 결과는 시간 초과였죠. 그다음에는 standard library namespace 지정을 안 해주면 매번 link를 해주나? 또 이상한 생각을 했습니다. 당연히 결과는 시간 초과죠. 워낙 코딩 테스트 문제를 푼 적이 오래되어 간단한 팁들을 까먹고 있었는데, 이 문제 역시 그중 하나였습니다. 문제의 주범은 'std::endl'이었습니다. 저 녀석을 사용하면 시간 초과에 걸리고 '\n'을 사용하면 통과가 되었습니다. 어떻게 생각하면 당연한 건데 평상시에는 문제가 되지 않아 잊고 있던 원인이었죠. 덕분에 한번 더 점검할 수 있는 기회가 되었습니다.

[C++] std::endl이 \n과 다른 점 - 출력버퍼 이해하기

저는 아래 블로그를 통해 궁금증을 해소했으며, 추후 기회가 된다면 저 역시 내용을 정리한 포스트를 업로드하도록 하겠습니다.