[2주차] 백준 15649번: N과 M (1)_C++

백준 15649: N과 M (1)

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

15649번: N과 M (1)

---

-> N과 M을 입력받는다

-> N개의 숫자 중에 M개를 뽑아 배열한다.  

---

문제에 접근조차 하기가 어려웠다.

처음에는 while문을 쓰는 건가 했는데 그것도 안되고, 엄청 고민하다가 구글링했다.

결론은 백트래킹!

이 문제는 DFS를 통해 백트래킹을 해주면 해결되는 문제라고 하는데,

문제는 백트래킹도, DFS도 처음 들어봤다. 

---

- DFS(깊이 우선 탐색)

: 가능한 모든 경로(후보)를 탐색한다. 

-> 재귀함수나 스택으로 구현한다

-> 노드 방문 시 방문여부를 반드시 검사해야함   // 아니면 무한루프에 빠질 수 있음

 

[참고] https://better-tomorrow.tistory.com/entry/DFS-BFS-%EC%9D%B4%ED%95%B4%ED%95%98%EA%B8%B0

 

- 백트래킹 

: DFS(깊이 우선 탐색)를 기반으로 하는 알고리즘으로, DFS의 구조를 적용할 수 있는 문제에 적용될 수 있다.

-> 후보해의 집합에서 최적해 집합을 찾아내는 문제에 사용될 수 있다

*후보해 : 해가 될 가능성이 있는 모든 조합

*최적해 : 문제에서 정하는 답으로서의 기준을 만족하는 해

 

-> 백트래킹 알고리즘의 핵심은 흔히들 '가지치기'라고들 한다. 

가지치기란 말은 백트래킹이 트리 구조를 기반으로 하기 때문에 트리(나무)에서 애초에 조건에 맞지않는 노드는 가지를 쳐버리자(더 이상 DFS로 깊이 탐색을 진행하지 말자)는 뜻이다. 쉽게 말해 DFS + 조건문인 셈이다.

 

[참고] https://pangtrue.tistory.com/71

https://devyoseph.tistory.com/161?category=972355

 

+) 백트래킹 문제: https://www.acmicpc.net/problem/9663

 

---

개념을 알아도 바로 풀리지는 않았다..

스스로 응용해보려고 노력하다가 안되길래 일단은 구글링해서 코드 분석해봤다! 

이번 문제는 특히나 그냥 넘어가지 말고 백트래킹,DFS 문제들을 더 풀어봐야 될 것 같다.

약간 막막하지만 그래도 계속 보다보면 언젠가는 익숙해지겠지~~

---

// [참고] https://tooo1.tistory.com/191

#include <iostream>
using namespace std;
#define MAX 9

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

void dfs(int k) {	
	if (k == M) {
		for (auto i = 0; i < M; i++) {
			cout << arr[i] << " ";
		}
		cout << "\n";
	}
	else {
		for (auto i = 1; i <= N; i++) {
			if (!visited[i]) {
				visited[i] = true;
				arr[k] = i;
				dfs(k + 1);
				visited[i] = false;
			}
		}
	}
}

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

 

- k는 현재 위치 , M은 목표 위치

- 목표에 도달했다면 -> arr에 저장한 값 M개 만큼 출력

- 목표에 도달하지 않았을 때

-> 방문 안했을 경우 (!visited[i]) : 방문 표시 후 i값을 arr에 저장 / k+1로 들어가서 백트래킹 설정!

---

구글링한 코드라서 완벽하게 이해를 하지는 못했지만, 개념을 다시 이해하고 스스로 응용해서

다음에 복습할 때에는 내가 처음부터 끝까지 코드 작성해서 다시 풀 것이다!