관심이 가는 개발 보물창고

풀이

재밌는 문제다.

좌표상에서 U, D, R, L 조작을 해서 내가 건너간 다리가 처음 다리라면 경우의 수를 추가해주고, 이미 건넜던 다리라면 그냥 건너가기만 하면 된다.

핵심은 내가 건너간 다리가 처음 방문한 다리인지 아닌지를 체크하는 것이다.

어떻게 체크할까?

시작 좌표는(0, 0) 에서 U이라는 명령을 받았다면 내가 건너게 될 다리는 다음과 같다.

(0,0) -> (-1,0)

(-1,0) <- (0,0)

이렇게 양방향으로 하는 이유는 둘 다 동일한 다리이기 때문이다.

이렇게 건넌 다리를 체크하기 위해서 Node라는 구조체를 만들고, 방문 배열에 해당 Node를 추가하는 방식으로 방문 배열을 만들었다. 다리를 통과할 때 해당 다리를 전에 방문했는지 안 했는지 체크는 배열을 돌면서 다리와 일치하면 이미 건넌 다리고 아니라면 처음 건너는 다리로 구현해주면 된다.

다 풀고 다른 사람이 푼 것을 봤는데 아래의 방법도 좋은 방법이다.

1. 방문 배열을 4차원 배열로 설정하는 방법

bool vis[x1][y1][x2][y2];

2. set 자료구조를 이용하는 방법

set<pair<pair<int, int>, pair<int, int> > > s;
//양방향으로 넣어주고
s.insert({{x1,y1},{x2,y2}});
s.insert({{x2,y2},{x1,y1}});
//마지막에 답을 도출할 때 2로 나눠주면 끝
ans = s.size() / 2;

#include <string>
#include <queue>
#include <map>
#include <vector>
using namespace std;

struct Node {
public:
    int x1, y1;
    int x2, y2;

    Node(int a, int b, int c, int d) : x1(a), y1(b), x2(c), y2(d) {}
    bool operator==(const Node& other) {
        if(x1 == other.x1 && y1 == other.y1 && x2 == other.x2 && y2 == other.y2) return true;
        if(x1 == other.x2 && y1 == other.y2 && x2 == other.x1 && y2 == other.y1) return true;
        return false;
    }
};

int solution(string dirs) {
    map<char, pair<int, int>> m;
    m['U'] = { -1,0 };
    m['D'] = { 1,0 };
    m['R'] = { 0,1 };
    m['L'] = { 0,-1 };
    int x = 0;
    int y = 0;
    int ans = 0;
    queue<char> q;
    vector<Node> vis;
    for (char c : dirs) q.push(c);
    while (!q.empty()) {
        int nx = x + m[q.front()].first;
        int ny = y + m[q.front()].second;
        q.pop();

        if (nx < -5 || ny < -5 || nx > 5 || ny > 5) continue;
        Node node(x, y, nx, ny);
        bool ok = true;
        for (Node n : vis) {
            if(n == node) {
                ok = false;
                break;
            }
        }
        if (ok) {
            vis.push_back(node);
            ans++;
        }
        x = nx;
        y = ny;
    }
    return ans;
}

풀이

N명의 순서대로 영어 끝말잇기를 진행하는데, 모두 올바른 답을 했다면 [0, 0]을 리턴하고, 아니라면

틀린 사람의 번호와 몇 번째로 틀렸는지를 리턴하면 된다.

문제를 쪼개서 해결해보자.

한 번 말했던 단어는 다시 등장하면 안 된다. 어떻게 체크할까?

여러 가지 방법이 있지만 et 자료구조를 이용하면 쉽게 중복을 체크할 수 있다.

s.find(words[i]) != s.end()
-> 조건을 만족한다면 아직 해당 단어는 처음 등장한 단어다.
-> 조건을 만족하지 못한다면 이미 전에 등장했던 단어를 의미한다.

사람의 번호 사이클은 어떻게 구할까?

그 사람이 말했던 단어는 몇 번째로 틀렸을까?

n = 3이라고 하면, mod 연산을 이용하면 쉽게 구할 수 있다.

person = index % n;

cycle = index  / n;

주의할 점은 사람의 번호는 1번부터 시작하므로 마지막에 각각 +1씩 해야 된다.

#include <string>
#include <vector>
#include <set>
using namespace std;

vector<int> solution(int n, vector<string> words) {
    vector<int> answer(2, 0);
    int person_num = 0;
    set<string> s;
    string previous;
    for(int i = 0; i < words.size(); i++) {
        person_num = i % n;
        if(previous == "") previous = words[i];
        else if(previous.back() != words[i].front() || s.find(words[i]) != s.end()) {
            answer[0] = person_num + 1;
            answer[1] = i / n + 1;
            break;
        }
        s.insert(words[i]);
        previous = words[i];
    }
    return answer;
}

풀이

핵심은 선택하지 않는 경우를 고려해야 한다.

입출력 예시를 보면

headgear에는 yellowhat, green_turban 2개

eyewear에는 bluesunglasses 1개

위장을 하려면 headgear만 쓰거나 eyewear만 쓰거나 혹은 headgear, eyewear 같이 쓰는 경우다.

그런데 headgear만 쓴다는 것은 eyewear는 쓰지 않는다는 것을 의미하니 다음과 같이 생각할 수 있다.

[headgear, x]

[eyewear, x]

[headgear, eyewear]

위를 고려하면,

heargear는 기존 2개에 +1(선택하지 않는 경우) => 3개

eyewear는 기존 1개에 +1(선택하지 않는 경우) => 2개

두 옷을 골라서 조합하면

3 x 2 = 6가지가 나오게 되는데, 위장은 최소 한 개의 옷은 입어야 하므로 마지막의 경우에 [x, x] 는 빼줘야 한다.

따라서 6 - 1 = 5가지가 나오게 된다.

#include <string>
#include <vector>
#include <map>
using namespace std;

int solution(vector<vector<string>> clothes) {
    map<string, int> m;
    for(auto v : clothes) {
        m[v[1]]++;
    }
    
    int answer = 1;
    for(auto iter = m.begin(); iter != m.end(); iter++) {
        answer *= (iter->second + 1);
    }
    return answer - 1;
}

풀이

주어진 문자열을 왼쪽으로 X칸만큼 회전시켰을 때, 주어진 문자열이 올바른 괄호 문자열이면 개수를 카운트하는 문제다. 쪼개서 문제를 해결해보자.

올바른 괄호 문자열인지 판단하는 방법은 stack 자료구조를 이용하면 쉽게 판별할 수 있다.

여는 괄호 '(', '{', '[' 가 들어오면 stack에 push

닫는 괄호 ')', '}', ']' 가 나오면 아래의 조건을 체크해야 한다.

1. 스택이 비어있는데 닫는 괄호가 나오면 이 문자열은 올바른 괄호 문자열이 아니다.

2. 스택이 비어있지 않다면 가장 윗단의 여는 괄호와 닫는 괄호를 비교해서 맞다면 pop 아니라면 올바른 괄호 문자열이 아니다.

왼쪽으로 x칸만큼 회전시키는 방법은 deque 자료구조를 이용하면 쉽게 구현할 수 있다.

deque는 양쪽에 삽입 및 삭제가 가능하기 때문이다.

따라서 해당 x칸만큼 반복문을 돌려서 앞에서 빼고, 뒤에 삽입하면 된다.

#include <string>
#include <vector>
#include <deque>
#include <iostream>
#include <stack>
using namespace std;

int solution(string s) {
    int answer = 0;
    int loop = s.size();
    bool isValid;
    deque<char> dq(s.begin(), s.end());
    while(loop--) {
        dq.push_back(dq.front());
        dq.pop_front();
        stack<char> st;
        isValid = true;
        for(int i = 0; i < dq.size(); i++) {
            if(dq[i] == '[' || dq[i] == '(' || dq[i] == '{') st.push(dq[i]);
            else {
                if(st.empty()) {
                    isValid = false;
                    break;
                }
                else if(dq[i] == ']' && st.top() == '[') st.pop();
                else if(dq[i] == ')' && st.top() == '(') st.pop();
                else if(dq[i] == '}' && st.top() == '{') st.pop();
            }
        }
        
        if(!st.empty()) isValid = false;
        if(isValid) answer++;
    }
    
    
    return answer;
}

풀이

문제가 길지만 결국 요약하면 A라는 사람과 B라는 사람이 만나게 되는 대진표가 몇 번째 라운드인지만 출력하면 된다.

N명의 사람만큼 배열을 채워 넣고, 대진을 비교하면 된다.

언제까지 비교하면 될까?

8 -> 4 -> 2 -> 1

8명이라면 총 3번의 토너먼트만 돌리면 된다.

매칭 비교는

A라는 사람 혹은 B라는 사람이 다른 사람과 매칭 하게 되면 반드시 A 혹은 B가 이기고,

그 외에는 왼쪽 사람이 이긴다고 가정하면 된다. (왼쪽이나 오른쪽이나 누가 올라와도 결국 A와 B가 이기게 되므로)

#include <iostream>
#include <vector>
using namespace std;

int solution(int n, int a, int b)
{
    vector<int> v(n, 0);
    for(int i = 0; i < n; i++) v[i] = i + 1;
    int round = 0;
    while(n != 1) {
        vector<int> win;
        round++;
        for(int i = 1; i <= n; i+=2) {
            if((v[i-1] == a && v[i] == b) || (v[i-1] == b && v[i] == a)) return round;
            else if(v[i-1] == a || v[i-1] == b) win.push_back(v[i-1]);
            else if(v[i] == a || v[i] == b) win.push_back(v[i]);
            else win.push_back(v[i-1]);
        }
        v = win;
        n /= 2;
    }
    return -1;
}

풀이

문제는 간단한데 생각보다 어려운 문제였다.

어려웠던 부분은 "어떻게 하면 쪼개서 나열할 수 있을까?" 였다.

이 과정에서 결국 답을 봤지만, 생각보다 간단했다.

쪼개고, 순열 돌리기

주어진 numbers의 문자열을 하나씩 문자 형태로 쪼개서 배열에 넣어준 다음에,

그 배열을 정렬하고 순열을 돌리면 된다.

예시를 보자.

numbers = "17"; 이라는 문자열이 들어오게 되면
paper[0] = '1';
paper[1] = '7';

이렇게 쪼개서 넣어준 다음에, 해당 배열을 정렬한다.

정렬하는 이유는 순열을 돌리기 위한 전제 조건이기 때문에 꼭 해주자. 정렬을 하지 않으면 처음부터 끝까지 모든 순열의 정보를 얻을 수 없기 때문이다.

순열을 돌리면 아래와 같이 2가지의 경로가 나오게 된다.

차례대로 하나씩 정수형으로 변환하여 넣어주면 아래와 같게 만들어진다.

첫 번째 순열 결과 : '1', '7' -> "1", "17" -> 1, 17
두 번째 순열 결과 : '7', '1' -> "7", "71" -> 7, 71

set<int> : 1, 7, 17, 71

여기서 set을 사용한 이유는 중복될 수 있기 때문에 사전에 중복된 숫자는 지워주기 위해서 사용했다.

종이로 만들 수 있는 모든 숫자를 만든 뒤에 해당 숫자가 소수인지 아닌지 파악하는 간단한 소수 함수를 만들어서 판별하면 답을 구할 수 있게 된다.

bool isPrime(int n) {
    if (n == 0 || n == 1) return false;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

전체 소스 코드

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <set>
using namespace std;

bool isPrime(int n) {
    if (n == 0 || n == 1) return false;
    for (int i = 2; i * i <= n; i++) {
        if (n % i == 0) return false;
    }
    return true;
}

int solution(string numbers) {
    int answer = 0;
    vector<char> paper;
    set<int> s;
    for (char c : numbers) paper.push_back(c);

    sort(paper.begin(), paper.end());
    do {
        string temp;
        for (int i = 0; i < paper.size(); i++) {
            temp += paper[i];
            s.insert(stoi(temp));
        }
    } while (next_permutation(paper.begin(), paper.end()));

    for (int n : s) {
        if (isPrime(n)) answer++;
    }

    return answer;
}

풀이

여러 개의 전화번호 목록들이 있을 때, 한 전화번호가 다른 전화번호의 접두어와 똑같다면 false를 리턴하고, 아니라면 true를 리턴하면 된다.

전화번호의 목록의 크기가 최대 100만이므로, 2중 포문은 안될 것 같고, 더 빠른 방법을 찾던 도중에 정렬을 하면 편하게 비슷한 숫자들끼리 뭉쳐있어서 양 옆의 비교가 가능할 것 같았다.

전화번호의 목록들을 일단 정렬한 다음에 앞의 전화번호에서 뒤의 전화번호의 접두어만 비교해서 같으면 false를 리턴하게 하고, 그러한 부분이 없다면 true를 리턴하면 된다.

#include <string>
#include <vector>
#include <algorithm>
using namespace std;

bool solution(vector<string> phone_book) {
    sort(phone_book.begin(), phone_book.end());
    for(int i = 0; i < phone_book.size() - 1; i++) {
        string previous = phone_book[i];
        string current = phone_book[i+1].substr(0, previous.size());
        if(previous == current) 
            return false;
    }
    return true;
}

풀이

문제에 명시된 대로 (x1, y1) ~ (x2, y2) 범위를 시계방향으로 회전시킨 후, 회전된 값들 중에서 가장 작은 값을 찾아내는 문제다. 단순 빡구현 문제.

처음에 문제를 보자마자 살짝 겁을 먹었으나, 하나하나 천천히 살펴보면서 구현하니까 생각보다 어렵지 않은 문제였다.

어떻게 하면 시계방향으로 돌릴 수 있을까?

하나의 큰 직사각형 혹은 정사각형을 4 부위로 나눠서 옮기기로 생각했다.

1. 왼쪽에 있는 사각형 옮기기

가장 왼쪽에 있는 사각형 부터 한 칸씩 위로 올려주면 된다. 이때 주의할 점이 있는데 가장 처음 지점 [x1][y1]을 temp라는 임시공간에 저장해둔다. 이러한 이유는 있다가 살펴보고 우선 한 칸씩 이동한다는 점에서 생각하는 것이다.

(2, 2) <- (3, 2) 로

(3, 2) <- (4, 2) 로

(4, 2) <- (5, 2) 로

규칙을 보면, (row, column)에서 column은 y1으로 고정되어 있고, row 값만 변동되는 것을 알 수 있다.

for(int i = x1; i < x2; i++) {
	board[i][y1] = board[i+1][y1];
}

2. 아래쪽에 있는 사각형 옮기기

한 번만 더 생각해보자. 빨간색 화살표는 아래 지점의 사각형들을 한 칸씩 옮기는 과정이다.

(5, 2) <- (5, 3)

(5, 3) <- (5, 4)

규칙을 찾았는가? row가 x2로 고정되어 있고, column만 변동하고 있다.

for(int i = y1; i < y2; i++) {
   board[x2][i] = board[x2][i+1];
}

3. 오른쪽에 있는 사각형 옮기기

살짝의 순서만 바뀌고 규칙만 찾으면 쉽게 해결할 수 있다.

for(int i = x2; i > x1; i--) {
   board[i][y2] = board[i-1][y2];
}

4. 위쪽에 있는 사각형 옮기기

for(int i = y2; i > y1; i--) {
   board[x1][i] = board[x1][i-1];
}

아까 저장했던 temp 임시 공간에 저장된 수는 다 옮기고 나서 마지막에 넣어준다.

이유는 한 칸씩 밀렸을 때 board [x1][y1+1] 은 board [x1][y1]으로 덮혀씌워지게 되는데 처음에 왼쪽 사각형부터 옮겼으므로 board[x1][y1] 값은 이미 board[x1+1][y1] 값으로 갱신된다. 따라서 기존에 임시 공간에 저장해둔 board[x1][y1] 수를 board [x1][y1+1]에 넣어주는 것이다.

board[x1][y1+1] = temp;

이렇게 행렬을 시계방향으로 옮기고 나서, 문제에서 요구한 가장 작은 숫자를 찾는 방법은 어떻게 할까?

처음에 temp의 값을 변수에 넣어주고, 이후에 회전을 할 때마다 그 값과 비교해서 min 값을 갱신해주면 된다.

#include <string>
#include <vector>
#include <iostream>
using namespace std;

vector<int> solution(int rows, int columns, vector<vector<int>> queries) {
    vector<vector<int> > board(rows + 1, vector<int>(columns + 1));
    for(int i = 1; i <= rows; i++) {
        for(int j = 1; j <= columns; j++) {
            board[i][j] = ((i-1) * columns + j);
        }
    }
    
    vector<int> answer;
    for(int i = 0; i < queries.size(); i++) {
        int x1 = queries[i][0];
        int y1 = queries[i][1];
        int x2 = queries[i][2];
        int y2 = queries[i][3];
        int temp = board[x1][y1];
        int num = temp;
        
        for(int i = x1; i < x2; i++) {
            board[i][y1] = board[i+1][y1];
            num = min(num, board[i][y1]);
        }
        
        for(int i = y1; i < y2; i++) {
            board[x2][i] = board[x2][i+1];
            num = min(num, board[x2][i]);
        }
        
        for(int i = x2; i > x1; i--) {
            board[i][y2] = board[i-1][y2];
            num = min(num, board[i][y2]);
        }
        
        for(int i = y2; i > y1; i--) {
            board[x1][i] = board[x1][i-1];
            num = min(num, board[x1][i]);
        }
        
        board[x1][y1+1] = temp;
        
        answer.push_back(num);
    }
    return answer;
}

풀이

문제의 지문이 엄청 길지만 요약하면 다음과 같다.

두 문자열이 주어지는데, 두 문자열에서 교집합과 합집합을 구한 다음에 교집합 / 합집합의 결과를 65536으로 곱한 값을 리턴하면 된다.

하나씩 확인해보자.

1. 문자열에서 영문자로 된 글자 쌍만 유효하며, 아래와 2글자씩 문자열을 쪼개서 넣어놔야 한다.

어떻게 쪼갤 수 있을까?

string의 substr을 이용해서 간단하게 쪼갤 수 있다. 또한 영문자가 아니라면 무시하자.

또 문제에서 보면, "AB" = "Ab" = "ab" 모두 같은 문자로 취급하므로 다 소문자로 만들어서 넣어준다.

vector<string> a;
vector<string> b;
for (int i = 0; i < str1.size() - 1; i++) {
    string s = str1.substr(i, 2);
    if (isalpha(s[0]) && isalpha(s[1])) {
        s[0] = tolower(s[0]);
        s[1] = tolower(s[1]);
        a.push_back(s);
    }
}

for (int i = 0; i < str2.size() - 1; i++) {
    string s = str2.substr(i, 2);
    if (isalpha(s[0]) && isalpha(s[1])) {
        s[0] = tolower(s[0]);
        s[1] = tolower(s[1]);
        b.push_back(s);
    }
}

2. 쪼개는 놨는데, 합집합과 교집합은 어떻게 구할까?

주의할 점이 있는데, 교집합을 구할 때 a의 string과 b의 string이 같다면 단순히 카운트를 하면 안 되고 check 배열을 각각 만들어서 서로 교집합을 체크했다면 true로 체크하면서 중복 여부를 피해 줘야 한다.

int t1 = 0, t2 = 0; // 교집합 수, 합집합 수
vector<bool> a_check(a.size(), false);
vector<bool> b_check(b.size(), false);
for (int i = 0; i < a.size(); i++) {
    for (int j = 0; j < b.size(); j++) {
        if (a[i] == b[j] && !a_check[i] && !b_check[j]) {
            a_check[i] = true;
            b_check[j] = true;
            t1++;
        }
    }
}

합집합은 간단하다. a와 b의 크기를 더한 다음에 교집합의 크기를 빼면 그것이 바로 합집합의 크기다.

t2 = a.size() + b.size() - t1;

만약에 교집합과 합집합이 0이라면 문제에서 바로 65536을 리턴하라고 했으므로 65536을 리턴하고,

아니라면 주어진 공식대로 65536 곱한 다음 소수점을 제외한 값을 리턴하면 된다.

t2 = a.size() + b.size() - t1;
if (a.size() == 0 && b.size() == 0) return 65536;
return (int)((double)t1 / t2 * 65536);

전체 소스 코드는 다음과 같다.

#include <string>
#include <vector>
#include <iostream>
using namespace std;

int solution(string str1, string str2) {
    vector<string> a;
    vector<string> b;
    for (int i = 0; i < str1.size() - 1; i++) {
        string s = str1.substr(i, 2);
        if (isalpha(s[0]) && isalpha(s[1])) {
            s[0] = tolower(s[0]);
            s[1] = tolower(s[1]);
            a.push_back(s);
        }
    }

    for (int i = 0; i < str2.size() - 1; i++) {
        string s = str2.substr(i, 2);
        if (isalpha(s[0]) && isalpha(s[1])) {
            s[0] = tolower(s[0]);
            s[1] = tolower(s[1]);
            b.push_back(s);
        }
    }

    int t1 = 0, t2 = 0;
    vector<bool> a_check(a.size(), false);
    vector<bool> b_check(b.size(), false);
    for (int i = 0; i < a.size(); i++) {
        for (int j = 0; j < b.size(); j++) {
            if (a[i] == b[j] && !a_check[i] && !b_check[j]) {
                a_check[i] = true;
                b_check[j] = true;
                t1++;
            }
        }
    }

    t2 = a.size() + b.size() - t1;
    if (a.size() == 0 && b.size() == 0) return 65536;
    return (int)((double)t1 / t2 * 65536);
}

풀이

N X N 체스판 위에 N개의 퀸을 서로 공격할 수 없게 놓는 문제다.

단순하게 생각하면 N^N^2(true, false) 모든 경우의 수를 비교해서 찾을 수 있지만, N의 크기가 커질수록 연산량이

감당할 수 없는 수준으로 된다. 따라서 가지치기(Pruning)를 하면서 문제를 해결해야 한다.

가치지기란?

어떤 강을 건너기 위해 돌다리를 두들겨보듯이 그 돌이 안전한지 안한지, 유망했는지 아닌지를 검사해서 유망하면 건너가고 아니라면 다시 돌아와서 다른 길을 선택하는 방법이다.

기존의 DFS처럼 주먹구구식으로 끝까지 가보는 것은 어떤 문제에서는 좋지만 이 문제에서는 연산량이 감당이 되지 않기 때문에 DFS처럼 탐색은 하지만 유망한 지 안 한 지를 검사해서 탐색의 범위를 좁혀가면서 문제를 해결한다.

N-Queen에서는 가지치기는 내가 어떠한 행(row)에 0 ~ N 중 하나의 열(col)에 Queen을 둔다고 가정했을 때,

다음 행(row + 1)에 Queen을 두기 전에 내가 두었던 Queen이 기존 [0 ~ row-1]까지 Queen들과 서로 공격하지 않는 범위에 두었는지를 체크하는 방법이다.

위에 그림처럼

row = 2인 행에 0번째 열에 Queen을 배치했다고 생각하자.

그러면 지금 둔 Queen이 적절한 배치인지를 확인하기 위해서 0번째 행에 배치한 Queen, 1번째 행에 배치한 Queen과의 충돌이 일어나지 않는지를 체크하면 된다.

체크할 때는 같은 행에 있는지 체크는 배제하면 된다. 이유는 해당 행에는 한 개의 Queen만 배치하기 때문이다.

체크하는 코드를 보자. 우리가 유망한지 체크하는 방법은 같은 열에 걸리거나 대각선에 걸리면 그것은 유망하지 않다.

이럴 경우에는 다시 해당 row에 Queen을 배치하지 않고 다른 열에다가 배치하고 유망한 지를 검사해보고,

만약에 유망하다면 row + 1에 Queen을 배치하러 가면 된다.

int col[15]; // col[i] = j : (i,j)에 Queen을 배치

bool isPromising(int row)
{
	// [0 ~ row) 단계 같은 열, 대각선 체크
	for (int i = 0; i < row; i++)
	{
		if (col[i] == col[row]) return false;
		if (abs(i - row) == abs(col[i] - col[row])) return false;
	}

	return true;
}

그렇다면 언제까지 Queen을 탐색할까?

row가 N까지 Queen을 잘 배치했다면, N x N 체스판 위에 N개의 Queen을 서로 공격할 수 없게 배치한 것이므로 이것은 문제에서 구하는 정답의 경우의 수 중 하나이기 때문에 개수를 하나 카운트하면 된다.

즉, row가 N이면 정답을 +1 증가시켜준다.

// row행 까지는 퀸을 놓은 상태,
void dfs(int row)
{
	if (row == n)
	{
		ans++;
		return;
	}
	// row행에 퀸을 배치하고 유망한지 체크
	// 유망하다면 다음 행에 퀸을 배치하러 가고,
	// 유망하지 않다면 다음 열에 다시 퀸을 배치하고 유망한지 검사한다.
	for (int i = 0; i < n; i++)
	{
		col[row] = i;
		if (isPromising(row))
			dfs(row + 1);
	}
}

정리하면,

각 단계(행)에서 어떤 열에 Queen을 둘지 정하고, Queen을 배치했다면 이전 단계에서 배치했던 모든 Queen들과 서로 공격하지 않는지를 검사해서 유망하다면 다음 단계로 넘어가고, 아니라면 그 단계에서 다음 열에 다시 Queen을 배치하는 방식으로 진행한다. 이렇게 하면 기존 DFS 탐색보다 빠르게 유망한 지 안 한 지 가지치기를 통해 더 빠르게 답을 구할 수 있을뿐더러 끝까지 탐색하지 않아도 된다는 장점이 있다.

전체 소스코드는 다음과 같다.

#include <iostream>
#include <cmath>
using namespace std;

int n, ans;
int col[15]; // col[i] = j : (i,j)에 Queen을 배치

bool isPromising(int row)
{
	// [0 ~ row) 단계 같은 열, 대각선 체크
	for (int i = 0; i < row; i++)
	{
		if (col[i] == col[row]) return false;
		if (abs(i - row) == abs(col[i] - col[row])) return false;
	}

	return true;
}

// row행 까지는 퀸을 놓은 상태,
void dfs(int row)
{
	if (row == n)
	{
		ans++;
		return;
	}
	// row행에 퀸을 배치하고 유망한지 체크
	// 유망하다면 다음 행에 퀸을 배치하러 가고,
	// 유망하지 않다면 다음 열에 다시 퀸을 배치하고 유망한지 검사한다.
	for (int i = 0; i < n; i++)
	{
		col[row] = i;
		if (isPromising(row))
			dfs(row + 1);
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	dfs(0);
	cout << ans << '\n';
	return 0;
}