[백준 / BOJ] 15649번 N과 M (1) (C++, Python)

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

15649번: N과 M (1)

---

문제

---

문제 풀이

백트래킹 + DFS 문제다. 수열은 사전 순으로 증가해야 하며, 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열이므로 DFS를 활용하면 되겠다는 생각이 들었다.

 

C++과 파이썬의 풀이가 살짝 다르지만 이번 문제는 모든 분이 C++ 상세 풀이를 보시면 도움이 될 것 같습니다.

 

C++ 상세 풀이

void dfs(std::vector<int> &v, int N, int M, int val)

우선, dfs 인자로 벡터, 입력받은 값인 N, M, 그리고 탐색을 시작할 val을 주었다. (벡터는 전역변수로 선언해서 인자로 주지 않을 수도 있다.)

 

if (val == M + 1) {
    for (int i = 1; i <= M; ++i) 
        std::cout << v[i] << " ";

    std::cout << "\n";
    return;
}

우선, 코드를 짤 때 알아보기 쉽도록 i가 1부터 시작하도록 했다. 그래서 vector 크기도 하나 커지고, DFS 호출을 몇 번을 했는지 알려주는 val도 본래면 M과 같을 시 출력되어야 하지만 +1을 해주었다. (즉, val이 0부터 시작되었을 때 호출이 3번 되었으면 vector 안에 요소가 2개가 있으므로 val == M으로 조건을 주면 되지만 여기서는 1부터 시작하므로 val == M + 1로 조건을 주었다.)

 

for (int i = 1; i <= N; i++) {
    if (!visited[i]) {
        visited[i] = true;
        v[val] = i;
        dfs(v, N, M, val + 1);
        visited[i] = false;
    }
}

핵심 코드이다. val이 1부터 시작하도록 받았으니, i도 1부터 시작하도록 한다. for문을 돌면서, 

만약 i를 방문하지 않았다면

=> i를 방문했다고 표시하고, (visited[i] = true)

=> 현재 호출된 순번의 벡터 자리를 i로 바꿔주고, (v[val] = i)

=> 다시 dfs를 호출해준다. 호출을 한번 더 하는 것이므로 val + 1을 인자로 넘겨준다.  i를 방문해서 벡터에 넣어줬으므로 다음 i를 찾기 위해 다시금 호출해주게 된다.

=> 호출을 마치고 되돌아오면 i는 모두 사용했으니 방문했다는 표시를 없애준다. (visited[i] = false)

Python 상세 풀이

두 가지 풀이를 첨부했는데, 첫 번째는 C++과 완전히 같은 방법이고, 두 번째는 파이썬에 있는 if _ in _을 이용해 조금 더 간단하게 풀어보았다. 물론 시간 복잡도는 더 좋지 않다.

 

for i in range(1, N + 1):
    if not visited[i]:
        visited[i] = True
        res.append(i)
        dfs(res, visited, N, M, val + 1)
        visited[i] = False
        res.pop()

 

C++의 코드와 유사한 점이 많다. 물론 다른 점은 res 리스트를 선언하고 여기에 추가(append)했다가 삭제(pop)하는 식으로 구현했다. 

 

C++ 코드 전문

 

Python 코드 전문

 

소감

백트래킹 파트의 첫 문제다! 앞으로 3문제가 이 아이디어를 그대로 활용하는데, DFS 연습을 할 수 있어서 아주 좋은 것 같다.