코딩 테스트 준비! (백준)/DFS

[DFS] 백준 15649번 N과 M (1,2,3) (C++)

lee-soo 2025. 4. 5. 14:56

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

 

이 문제를 풀면서 나에게도 큰 시련이 찾아왔다.

 

도저히 못풀겠다

 

사실 글쓴이는 아직 코테 초보수준이라 해본게 

브루트 포스랑, dp 랑.. 자료구조 뭐 이런것들인데

 

이게뭐야

 

사실 저번에 테트로미노도 브루트포스인줄 알았는데 dfs로 풀었던 것처럼  이것도 브루트 포스인줄 알았는데 , 브루트 포스로 풀면 진짜 너무너무 복잡해진다.

 

왜 dfs인가?

1. 모든 경우의 수를 확인해야 함

2. 조건이 존재함 ( 오름차순..? )

3. 그리고 검색해보니까 dfs로 해야된다 한다

 

나는 솔직히... 브루트 포스로 풀려했지만 도저히 생각나지 않아서 찾아서 한거다..

 

dfs란 것을 알면 식짜는 것은 쉬워질 것 이다

 

maybe,,?

 

backtraking이 주요요소인데

 

gpt에서 설명해준 트리구조다

1에서 1로갔는데, 안되니까 다시 뒤로(backtraking)

.. 이걸 계속 반복하면 된다

 

정답코드로 더 자세한 설명을 해주겟따

#include <iostream>
#include <cmath>
#include <vector>
bool visited[10];
using namespace std;
void print_(int n, int m, int depth);
vector<int> v;
int main()
{
    int n, m;

    cin >> n >> m;

    print_(n, m, 0);
}
void print_(int n, int m, int depth)
{

    if (depth == m)
    {
        for (int i = 0; i < m; i++)
        {
            cout << v[i] << " ";
        }
        cout << "\n";
        return;
    }

    for (int i = 1; i <= n; i++)
    {

        if (!visited[i])
        {
            visited[i] = true;
            v.push_back(i);
            print_(n, m, depth + 1);
            visited[i] = false;
            v.pop_back();
        }
    }
}
print_는 dfs 함수이다.
쨋든 코드를 보자

 

 
 if (depth == m)
    {
        for (int i = 0; i < m; i++)
        {
            cout << v[i] << " ";
        }
        cout << "\n";
        return;
    }

처음 부분은 계속된 재귀호출을 반복했을 때, 중첩된 경우의 수가 출력

 

for (int i = 1; i <= n; i++)
    {

 

        if (!visited[i])
        {
            visited[i] = true;
            v.push_back(i);
            print_(n, m, depth + 1);
            visited[i] = false;
            v.pop_back();
        }
    }
 
이게 핵심 부분이다.
 
처음에 어떤 수를 들어갈 때, 방문하지 않은 노드라면 (!visited)
그 노드를 가진 상태로 새롭게 함수를 들어가서, 방문하지 않은 i번째를 찾는다
 

이렇게 말이다.

 

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

그렇다면 2번을 보자

  

 

 

뭐가 달라졌는가?

바로 오름차순이다.

 

그럼 그냥 저 코드에 조건문 하나만 달아주면 된다.

 

#include <iostream>
#include <cmath>
#include <vector>
bool visited[10];
using namespace std;
void print_(int n, int m, int depth);
vector<int> v;
int main()
{
    int n, m;

    cin >> n >> m;

    print_(n, m, 0);
}
void print_(int n, int m, int depth)
{

    if (depth == m)
    {
        for (int i = 0; i < m; i++)
        {
            cout << v[i] << " ";
        }
        cout << "\n";
        return;
    }

    for (int i = 1; i <= n; i++)
    {

        if (!visited[i] && (v.empty() || v.back() < i))
        {
            visited[i] = true;
            v.push_back(i);
            print_(n, m, depth + 1);
            visited[i] = false;
            v.pop_back();
        }
    }
}
 
if (!visited[i] && (v.empty() || v.back() < i))
원래는 visit했는가만 확인했지만, 가장 끝에 있는 숫자가 새로 들어오는 숫자보다 작아야 그것을 넣어준다. 
자동으로 오름차순이 될 것이다
그리고 가장 처음에 벡터에 내부 원소가 없는 상태에서  v.back 을 하게 된다면 조건문을 만족하지 못하니
v.empty()도 넣어준다
 

 

다음은 n과m 3이다

 

보니까 같은수를 여러번 구해도 된다 한다.

그렇다면 visit이 필요없고, 오름차순을 구현하기 위해 사용한 조건문도 뺴면 된다.

#include <iostream>
#include <cmath>
#include <vector>
bool visited[10];
using namespace std;
void print_(int n, int m, int depth);
vector<int> v;
int main()
{
    int n, m;

    cin >> n >> m;

    print_(n, m, 0);
}
void print_(int n, int m, int depth)
{

    if (depth == m)
    {
        for (int i = 0; i < m; i++)
        {
            cout << v[i] << " ";
        }
        cout << "\n";
        return;
    }

    for (int i = 1; i <= n; i++)
    {

        v.push_back(i);
        print_(n, m, depth + 1);

        v.pop_back();
    }
}
 
끝ㄲ튺튺ㅌ