[백준(BOJ)] 15663번 : N과 M (9) - C++[CPP]

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

15663번: N과 M (9)

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 백트래킹

 

---

 

⊙ 문제 접근 과정

 

수열의 중복을 막기 위해 set을 사용했다.

vector에 수열의 값을 저장을 M개만큼 저장하고 그 값들을 set에 저장한다.

 

이번 문제의 point!

이번 9탄에서는 방문처리인 visited을 사용하지 않으면 시간 초과가 발생한다.

 

N과 M 9탄에서 드디어 방문 표시를 해야 하는 이유를 몸소 확인할 수 있었다.

 

그리고 for each문을 사용하지 않아도 시간 초과가 발생한다.

따라서 이번에는 출력문을 main()함수로 옮기고 for each문을 사용했다.

 

---

 

⊙ 문제 풀이

 

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;
#define MAX 9

int N,M;
int first[MAX];
int arr[MAX];
bool visited[MAX];
set<vector<int>> s; //중복 제거!

void dfs(int k) { //현재 위치
    if(k==M) { //목표인 M까지 도달했다면
        vector<int> v;
        for(auto i=0;i<M;i++)
            v.push_back(arr[i]);
        s.insert(v); //set에 추가
        v.clear(); //vector 초기화
    }else { //목표에 도달하지 않았다면
        for(auto i=0; i<N;i++) {
            if(!visited[i]) { //방문 안 했다면
                visited[i]=true; //방문 표시
                arr[k]=first[i]; // 정렬한 N값을 arr에 저장
                dfs(k+1); //더 깊게 들어가자. (M까지)
                visited[i]=false; //백트래킹 설정 
            }
        }
    }
}

int main() {
    cin >> N >> M;

    for(int i=0;i<N;i++)
        cin >> first[i];
    
    sort(first,first+N); //정렬

    dfs(0);

    for(auto vector:s) {
        for(auto temp:vector)
            cout << temp << " ";
        cout << "\n";
    }
}

---

⊙ 결과

 

---

⊙ 마무리

 

15649번 : N과 M (1)

15650번 : N과 M (2)

15651번 : N과 M (3)

15652번 : N과 M (4)

15654번 : N과 M (5)

15654번 : N과 M (6)

15656번 : N과 M (7)

15657번 : N과 M (8)

15663번 : N과 M (9)

15664번 : N과 M (10)

15665번 : N과 M (11)

15666번 : N과 M (12)

 

 

좋아요는 로그인하지 않아도 누를 수 있습니다!