[Algorithm] 순열 분석

문제

---

서로 다른 n개의 원소들 중에서 r개만을 뽑아 일렬로 나열하는 것을 순열이라 한다. 예를 들어, 3개의 원소 a, b, c 중에서 2개만을 뽑아 나열하면 ab, ac, ba, bc, ca, cb 의 6가지 경우가 있다. n과 r이 주어질 때, n개의 소문자 중에서 r개만을 뽑아 나열하는 모든 경우를 출력하는 프로그램을 작성하시오. 단, a부터 시작하여 연속으로 n개의 알파벳을 갖고 있다고 하자.  

입력

---

첫 번째 줄에 n과 r이 주어진다. ( 1 ≤ n ≤ 10, 0 ≤ r ≤ min(n, 7) )  

출력

---

각 줄에 n개의 소문자 중에서 r개만을 뽑아 나열하는 경우를 사전순으로 나열한 결과를 출력한다.

 

예제 입력

4 2

예제 출력

ab
ac
ad
ba
bc
bd
ca
cb
cd
da
db
dc

[접근] 순열을 스왑 + 재귀호출을 이용해서 풀 수 있는 블로그들이 많았다. 

         하지만 함께 공부하는 친구가 그래프를 이용해 푸는 것을 보고, 이 점을 참고하여 공부해보았다.

<코드>

#include<iostream>

#include<cstdio>

#include<vector>

using namespace std;

int n,r;

char arr[26];

bool isVisited[26];

vector<char> v;

void dfs(){

  if(v.size() == r){

    for(int i=0; i<v.size(); i++){

      printf("%c",v[i]);

    }

    printf("\n");

    return;

  }  

  for(int i=0; i<3; i++){

    if(isVisited[i] == false){

      isVisited[i] = true;

      v.push_back(arr[i]);

      dfs();

      v.pop_back();

      isVisited[i] = false;

    }

  }

}  

int main(){

   scanf("%d %d",&n,&r); 

  for(int i=0; i<n; i++){

    arr[i] = 'a' + i;

  }

  dfs();

  return 0;

}

- 핵심부분

(1)

 

(2)

(이해)

3개의 문자 a,b,c 중 서로 다른 2개의 문자를 뽑아 나열하는 방식을 재귀 호출의 흐름에서 그려보았다.

(이해2)

처음에 이해가 잘 되지 않았는데, 이렇게 그림을 그려보니 이해가 되었다.

재귀 호출을 사용할 때 가장 중요한 것은 탈출하는 조건을 설정하는 것과 방문을 체크하는 배열을 이용하는 것임을 느낄 수 있었다.