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

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

15649번: N과 M (1)

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 백트래킹

 

---

 

⊙ 문제 접근 과정

 

DFS를 이용하여 백트래킹을 했다.

재귀를 통해 순열을 구하기 위해 DFS를 통해 문제를 접근했는데 방법과 개념만 잡혀있으면 구현하기가 비교적 간단하다고 생각한다.

 

어렵다. 어려워( + 2021.08.10 내용 추가 )

무슨 오만인지 예전에 적었을 때, 쉽다고 적었을까. 다시 백트래킹을 보는데 생각보다 더 어렵다.

그래서 내용 추가와 주석을 줄마다 적기 위해 다시 이 글을 찾아왔다.

 

visited을 이용하여 방문을 하였는지 안 하였는지 체크표시해준다.

그리고 M까지 깊게 들어갔을 시, 배열 arr에 저장된 값을 M개만큼 출력해주자.

---

 

⊙ 문제 풀이

 

#include <iostream>

using namespace std;
#define MAX 9

int N,M;
int arr[MAX];
bool visited[MAX];

void dfs(int k) { //현재 위치
    if(k==M) { //목표인 M까지 도달했다면
        for(auto i =0;i<M;i++)
            cout << arr[i] << " "; //arr에 저장한 값 M개 만큼 출력
        cout << "\n";
    }else { //목표에 도달하지 않았다면
        for(auto i=1; i<=N;i++) {
            if(!visited[i]) { //방문 안 했다면
                visited[i]=true; //방문 표시
                arr[k]=i; // i값을 arr에 저장
                dfs(k+1); //더 깊게 들어가자. (M까지)
                visited[i]=false; //백트래킹 설정
            }
        }
    }
}

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

---

⊙ 결과

 

---

⊙ 마무리

 

 

15649번 : N과 M (1)

15650번 : N과 M (2)

15651번 : N과 M (3)

15652번 : N과 M (4)

15654번 : N과 M (5)

15654번 : N과 M (6)

15656번 : N과 M (7)

15657번 : N과 M (8)

15663번 : N과 M (9)

15664번 : N과 M (10)

15665번 : N과 M (11)

15666번 : N과 M (12)

 

 

좋아요는 로그인하지 않아도 누를 수 있습니다!