15649 N과 M (1)

 

 

ㅎㅎㅎ...

N 퀸 문제... 

마스터...

 

퀸 풀 때 처럼 풀었다. 

 

https://burningjeong.tistory.com/174

N queen

 

전에 수업시간에 이렇게 배워서 계속 사골처럼 코드 우려먹는 중.. 퀸이랑 다른 점이라 하면 퀸은 놓을 자리를 확인하고 놓는다면 이 문제는 일단 넣어보고 그 다음 맞는지 확인한다. 

 

확인하는 부분은 배열에 같은 게 있는지 / 없는지를 체크하는데 이걸 깔쌈하게 sort - unique - erase로 하려다가 배열 크기 때문에 그냥 하나씩 확인했다. 만약 위의 방식대로 쓰려면 append로 하나씩 넣어야 하지 않을까? 앗 게다가 기존의 배열 순서도 섞여버리네. 이게 최선인 것 같다. 

 

#include <iostream>
#include <vector>

using namespace std;

void    print_vector(int m, vector<int> v)
{
    for (int i = 0; i < m; i++)
    {
        printf("%d ", v[i]);
    }
    printf("\n");
}

bool    promising(int index, vector<int> v)
{
    for (int i = 1; i <= index; i++)
    {
        for (int j = 0; j < i; j++)
        {
            if (v[i] == v[j])
                return (false);
        }
    }
    return (true);
}

void    find_sequence(int index, int n, int m, vector<int> v)
{
    if (index == m)
        print_vector(m, v);
    else
    {
        for (int i = 1; i <= n; )
        {
            v[index] = i++;
            if (!promising(index, v))
            {
                continue;
            }
            find_sequence(index + 1, n, m, v);
        }
    }
}

int     main()
{
    int n, m;
    scanf("%d %d", &n, &m);
    vector<int> v(m, 0);
    
    find_sequence(0, n, m, v);
}

 

---

 

북님한테 받은 참고코드

재귀 특징 : 한번에 이해 몬한다

뇌가 손에 달린 사람이라 쓰면서 생각했다ㅋㅋ 이걸로 n과 m 다시 풀면서 익숙해지면 될 듯

#include <iostream>
#include <vector>

using namespace std;

bool    visited[10];
vector  <int> v;

void    select(int n, int k)
{
    if (k == 0)
    {
        for (auto& s : v)
            printf("%d ", s);
        printf("\n");
        return ;
    }
    for (int i = 1; i <= n; i++)
    {
        if (visited[i])
            continue ;
            
        visited[i] = true;
        v.push_back(i);
        
        select(n, k - 1);
        
        v.pop_back();
        visited[i] = false;
    }
}

int     main()
{
    int n, m;

    scanf("%d %d", &n, &m);
    select(n, m);
    return (0);
}