백준 15649번: N과 M (1)

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

참고한 블로그 : https://cryptosalamander.tistory.com/54

백트래킹 문제를 풀어보려고 처음 손을 댔다. 검색을 해 보니 백트래킹이 DFS를 이용해서 전체 탐색을 하는 방법이라고 한다.

• 모든 solution을 탐색한다고 할 때, DFS를 이용하면 탐색하다가 정답과 아예 연관이 없는 경우 아래에 있는 노드들은 굳이 방문하지 않아도 당연히 정답이 아니므로 배제하기가 쉽다.
• BFS를 이용하면 너비 우선이기 때문에 거기까지 탐색을 하고 나서야 배제하므로 더 비효율적이라고 한다.
• 재귀 호출 or 스택을 이용한 DFS로 문제를 풀어나감
  
  <작성한 코드>

#include <iostream>
using namespace std;

int n, m, arr[9], visited[9];

void dfs(int cnt){
    if(cnt == m){
        for(int i = 0; i < m; i++){
            cout << arr[i] << " ";
        }
        cout << '\n';
        return ;
    }
    for(int i = 1; i <= n; i++){
        if(visited[i] == 0){ // 아직 방문을 안했으면 갈 수 있는 곳
            visited[i] = 1;
            arr[cnt] = i;
            dfs(cnt + 1);
            visited[i] = 0;
        }
    }
}

int main()
{
    cin >> n >> m;
    dfs(0);
}

블로그를 참고해서 이해한 후 코드를 작성해서 제출했는데 시간 초과가 떴다. 그래서 블로그 코드와 비교도 해 봤는데 다른 점이 거의 없었는데도 시간 초과가 떴다. 검색을 해 봤더니, 수열을 출력할 때 개행을 하는 부분에서 나는 보통 cout << endl;을 많이 썼는데, endl을 하면 뭔가 과정이 더 추가가 되어서 시간이 오래 걸린다고 한다. 귀찮지만 '\n'을 자주 사용하도록 해야겠다. 참고