[C언어] 백준 15649 : N과 M (1)

사진이 조금 잘렸는데, 그냥 순열을 출력하면 된다.
N과 M(3)을 보고 난 뒤 다른건 혼자 할 수 있을거라고 생각했는데, 아직 그정도 실력이 안되는 것 같다.
문제유형을 익히고, 양치기를 하더라도 실력을 단기간에 쌓고싶다. 문제유형을 익혀보자.

처음에는 순열을 구하는 법을 구글링했다. swap을 사용하면서 정렬했다. 하지만 이 문제는 swap을 굳이 사용할 필요가 없다. 결국 답을 보고 익히기로 했다. 시간을 갈아도 더 나아질 기미가 보이지 않았기 때문이다.

다른 사람 코드

#include <stdio.h>

int n, m;
int result[1000];
int check[1000];

void DFS(int depth)
{
    int i;

    if (depth == m)
    {
        for (int i = 0; i < m; i++)
            printf("%d ", result[i]);
        printf("\n");
    }
    else
    {
        for (i = 1; i <= n; i++)
        {
            if (check[i] == 0)
            {
                result[depth] = i;
                check[i] = 1;
                DFS(depth + 1);
                check[i] = 0;
            }
        }
    }
}

int main(void)
{
    scanf("%d %d", &n, &m);
    DFS(0);
    return 0;
}

https://velog.io/@seochan99/15649-N-%EA%B3%BC-M-1 여기에서 도움을 받았다.

이전에 N과 M(3)을 풀었던 곳에서 (1)을 보았었고, 그 외에도 다양하게 검색을 해봤었다. 근데 확실히 처음부터 반복문을 돌리는 것 보다, if로 케이스를 먼저 나눈 뒤 반복문을 돌리는게 이해가 더 잘되었다. 그래서 이 방법을 선택했다.

N=4, M=2 이고,
depth = 0,i=1일때
1. DFS[0]-> result[0]=1 -> check[1]=1 -> DFS(1)
2. DFS[1]-> (i=2일때)result[1]=2 -> check[2]=1 -> DFS(2)
3. DFS[2] -> (1,2) 출력
-> 2번으로 돌아가서 체크 초기화하고 i++ 해서(1,3),(1,4)출력
-> 1번으로 돌아가서 체크 초기화 하고 i++해서 같은 방식으로 (2,1),(2,3),(2,4) 출력..
반복 !!!

위 벨로그에 있던 풀이방법이다. 확실히 더 직관적인 것 같다.

같은 방식으로, N과 M (3) 풀이이다.

N과 M (3)

#include <stdio.h>

int n, m;
int result[1000];

void DFS(int depth)
{
	int i;

	if (depth == m)
	{
		for (int i = 0; i < m; i++)
			printf("%d ", result[i]);
		printf("\n");
	}
	else
	{
		for (i = 1; i <= n; i++)
		{
			result[depth] = i;
			DFS(depth + 1);
		}
	}
}

int main(void)
{
	scanf("%d %d", &n, &m);
	DFS(0);
	return 0;
}

(1)에서 check를 없애주어 모든 경우를 출력해주었다. 반대로 말하면, check로 순열을 구한다는 것이다.

처음부터 반복문을 돌리면서, 그 안에 if를 처리하는 방법과
처음에 if를 걸어주고 그 뒤에 반복문을 돌리는 방법 두가지를 알았다. 두개의 차이점을 이해하고, 상황에 따라서 사용해보자.