N-Queen[프로그래머스]

접근법:

DFS를 기반으로 하되 도중에 불가능하다고 판단되면 즉시 포기하고 돌아가는 백트래킹을 활용한 방식입니다.

board[i] = j : i번째 행의 j 번째 열에 퀸이 놓여 있다는 뜻
- 1차원배열 을 사용하면, 행이 겹치는 경우를 자동으로 배제
새로운 퀸을 자리에 놓은뒤 검사한다.
- 같은 열에 있는지 검사한다
- 행의차이와 열의차이가 같다면 대각선상에 있다.

#include <string>
#include <vector>
#include <cmath>
using namespace std;
int answer = 0;
vector<int> board;

bool check(int r)
{
    for(int i = 0; i < r; ++i)
    {
        if(board[i] == board[r] || abs(board[r] - board[i]) == abs(r - i))
        {
            return false;
        }
    }
    return true;
}

void dfs(int r, int n)
{
    if(r == n)
    {
        answer++;
        return;
    }
    
        
    for(int c = 0; c < n; ++c)
    {
        board[r] = c;
        if(check(r))
            dfs(r + 1, n);
    }
}

int solution(int n) {
    board.assign(n, 0);
    dfs(0, n);
    return answer;
}

혼자서 하는 틱택토[프로그래머스]

Reflection - 01. 목적과 전체 흐름