백준) 15649외 3문제 - N과 M (1~4)

DFS를 공부했으니 DFS를 써보고 싶었다.

근데 역시나 여러운것......ㅎㅎ....

그냥 일단 해보자는 식으로 했다.

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

보통 예제 입출력을 보고 종이에다 끄적여보는데 정말 .....ㅜㅜㅜㅜㅜㅜ

그동안 너무 대충 공부한거 같았다 ㅜㅜ (반성......)

 

일단 첫번째 코드는 다음과 같다. (15649번)

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

int n,m;
int arr[MAX] = {0,};
bool visited[MAX] = {0,};

void dfs(int cnt)
{
    if(cnt == m)
    {
        for(int i = 0; i < m; i++)
            cout << arr[i] << ' ';
        cout << '\n';
        return;
    }
    for(int i = 1; i <= n; i++)
    {                                //1 
        if(!visited[i])
        {                            //2
            visited[i] = true;       //3
            arr[cnt] = i;            //4
            dfs(cnt+1);              //5
            visited[i] = false;      //6
        }
    }
}

int main() {
    cin >> n >> m;
    dfs(0);
}

1부터 N까지 차근차근 확인해가면서 알아보면 초기값은 다음과 같다!(편의상 arr[0]이 1번이라 생각 ㅎㅎ...)

	1	2	3	4
visitied	F	F	F	F
arr	0	0	0	0

//1 i = 1이고, 아직 아무것도 한게 없으니 if문으로 들어가게 된다..!!!!!

그리곤, visited[1]을 true로 바꿔줘서 중복이 안되게 바꿔주는 것이다!!!!

arr[0]에 1을 넣은 상태로 다시 재귀함수!!!!!

여기서 //6 은 잠시 기다리고 다시 위로 올라간다!!!!!! 

	1	2	3	4
visitied	T	F	F	F
arr	1	0	0	0

다시 //1 에서는 visited[1]이 true값이니 if문에 들어가지 않고 for문을 돌린다.

i=2 에서는 visited[2]가 false이므로, if문에 들어가서 true로 바뀌고

arr[1] = 2를 넣고 다시 재귀!!!!!

여기서 다시 //6은 기다린다.

	1	2	3	4
visitied	T	T	F	F
arr	1	2	0	0

cnt값이 M(2)가 되었으므로 arr를 출력해준 뒤에 return해주게 되고, 

방금 했던 cnt = 1 에서 visited[2]가 true로 바뀌었던 그 순간으로 돌아가서 계속 진행하게 된다!

visited[2] = false로 바뀌고 for문이 계속 돈다!!!!

 

이런 방식으로 계속 진행하게 되면 예시의 출력처럼 나오게 된다.

 

어떻게 써야할지 모르겠지만 대충 느낌 알게 되면 생각대로 풀리는 듯 하다.

N과 M 2, 3, 4는 전부 조금씩만 다르니 코드만 첨부!

 

N과 M (2)

#include <iostream>
#define MAX 9

using namespace std;

int N, M;
int arr[MAX] = { 0, };
bool check[MAX] = { 0, };

void dfs(int cnt) {
	if(cnt == M) {
		for(int i = 0; i < M; i++) {
			cout << arr[i] << " ";
		}
		cout << endl;
		return;
	}
	
	for(int i = 1; i <= N; i++) {
		if(!check[i]) {
			check[i] = true;
			arr[cnt] = i;
			dfs(cnt+1);
			for(int k = i+1; k <= N; k++)
				check[k] = false;
		
		}		
	}
}

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

 

N과 M (3)

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

int n,m;
int arr[MAX] = {0,};
bool visited[MAX] = {0,};

void dfs(int cnt)
{
    if(cnt == m)
    {
        for(int i = 0; i < m; i++)
            cout << arr[i] << ' ';
        cout << '\n';
        return;
    }
    for(int i = 1; i <= n; i++)
    {
            arr[cnt] = i;
            dfs(cnt+1);
    }
}

int main() {
    cin >> n >> m;
    dfs(0);
}

 

N과 M (4)

#include <iostream>
#define MAX 9

using namespace std;

int N, M;
int arr[MAX] = { 0, };
bool check[MAX] = { 0, };

void dfs(int cnt) {
	if(cnt == M+1) {
		for(int i = 1; i < M+1; i++) {
			cout << arr[i] << " ";
		}
		cout << endl;
		return;
	}
	
	for(int i = 1; i <= N; i++) {
		if(!check[i]) {
			if(arr[cnt-1] <= i) {
				arr[cnt] = i;
				dfs(cnt+1);
				check[i] = false;
			}
		}
	}
}

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