📝9663번: N-Queen
문제 설명
N-Queen
해결 방법
문제를 요약하자면 퀸은 특성상 x축, y축, 대각선을 자유자재로 움직일 수 있는데, NxN 체스판에서 퀸을 모든 행에 한 개씩 두면서 서로의 이동 경로가 겹치지 않는 경우의 수를 찾는 것이다.
퀸을 첫번째 행부터 마지막 행까지 가능한 열에 차례대로 두다가 해당 방법이 올바르지 않으면 이전에 두었던 퀸으로 거슬러 올라가 다시 두는 백트리킹 알고리즘을 사용한다.문제를 해결하기 위해서 NxN 2차원 배열을 직접 만들 필요 없이, 크기가 N인 일차원 배열을 만든 후, 각 인덱스를 체스판의 열로 사용하고 해당 인덱스의 값을 체스판의 행으로 사용하면 어디에 퀸이 있는지를 나타낼 수 있다. 다음 예시를 참고하자.
board라는 1차원 배열 선언board[0] = 1 # 0열 1행에 퀸 존재 board[1] = 3 # 1열 3행에 퀸 존재 board[2] = 0 # 2열 0행에 퀸 존재 board[3] = 2 # 3열 2행에 퀸 존재다음에 퀸을 둘 수 있는지를 판단하며 재귀적으로 다음 열로 넘어간다.
is_promising: 퀸을 둘 수 있는지 여부를 판단하는 함수다. i는 x좌표를 의미하고, board[i]는 y좌표를 의미한다. 퀸은 상하좌우, 대각선 방향으로 겹치면 안된다. x축, y축 좌표의 차이가 같으면 같은 대각선에 있는 것으로 생각할 수 있다.
N_Queen: 백트래킹을 시도하는 함수로 퀸을 둘 수 있는 경우의 수를 카운트(g_cnt)한다. 우선 퀸을 두고 다음 자리에 퀸을 둘 수 있는지(is_promising) 체크하고 다음 열에 퀸을 두기 위해 재귀적으로 호출한다. cdx가 N이 되면 모든 행에 퀸을 두었다는 의미이므로 g_cnt를 증가시킨다.
💻소스코드
#include <iostream>
#include <cmath>
using namespace std;
int g_cnt = 0;
bool is_promising(int* board, int cdx) {
int i = 0;
while (i < cdx) {
if (board[i] == board[cdx] || cdx - i == abs(board[cdx] - board[i]))
return false;
i++;
}
return true;
}
void N_Queen(int* board, int N, int cdx) {
int i;
if (cdx == N)
g_cnt++;
else {
i = 0;
while (i < N) {
board[cdx] = i;
if (is_promising(board, cdx))
N_Queen(board, N, cdx + 1);
i++;
}
}
}
int main()
{
// N-Queen
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int N;
cin >> N;
int *board = new int[N];
N_Queen(board, N, 0);
cout << g_cnt << "\n";
return 0;
}📝14888번: 연산자 끼워넣기
문제 설명
연산자 끼워넣기
해결 방법
op 배열에 순서대로 + - * / 를 넣고 num 배열에 입력받은 숫자들을 넣는다. 연산자를 백트래킹을 사용하여 골라 모든 가능한 경우의 수를 최댓값과 최솟값을 갱신하면서 res_max와 res_min에 저장하고 출력한다.
💻소스코드
#include <iostream>
using namespace std;
int N;
int op[4]; // +, -, *, /
int num[11];
int res_max = -1000000001;
int res_min = 1000000001;
// 깊이는 입력 받는 num 순서
void dfs(int depth, int result) {
if (depth == N - 1) {
if (result > res_max)
res_max = result;
if (result < res_min)
res_min = result;
}
else {
for (int i = 0; i < 4; i++) {
if (op[i] > 0) {
op[i]--;
if (i == 0)
dfs(depth + 1, result + num[depth + 1]);
else if (i == 1)
dfs(depth + 1, result - num[depth + 1]);
else if (i == 2)
dfs(depth + 1, result * num[depth + 1]);
else
dfs(depth + 1, result / num[depth + 1]);
op[i]++;
}
}
}
}
int main()
{
// 연산자 끼워넣기
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N;
for (int i = 0; i < N; i++)
cin >> num[i];
for (int i = 0; i < 4; i++)
cin >> op[i];
dfs(0, num[0]);
cout << res_max << '\n' << res_min;
return 0;
}📝14889번: 스타트와 링크
문제 설명
스타트와 링크
해결 방법
dfs를 활용, N명의 사람중 N/2명을 뽑는 조합의 모든 경우의 수를 찾고, 이를 바탕으로 팀을 나눴을 때 두 팀의 능력치의 차이가 가장 최소가 될 때의 값을 저장하여 출력하면 되는 문제다.
중복되지 않게 두 팀을 짜기 위해 visited 배열에 true로 표시된 값들은 start 팀으로 능력치를 더하고, false로 표시된 값들은 link 팀으로 능력치를 더한다.
만약 i를 0부터 라고 하면 00 01 02 03 10 11 12 ... 해서 팀을 구성할 수 없는 조합을 계속 구성하게 된다면 연산 시간이 많아져 시간초과를 경험하게 된다. 그렇기 때문에 이미 0번째를 팀으로 구성했다면 다음 선수는 0이 될수 없으므로 검사할 필요가 없다. 그래서 i = num으로 설정하고 dfs에 i + 1을 넘겨주어 오름차순으로 중복을 방지했다.
💻소스코드
#include <iostream>
#include <cmath>
using namespace std;
int ans = -1, N;
int arr[20][20] = { 0, };
bool visited[20];
void dfs(int depth, int num) {
if (depth == N / 2) {
int start = 0, link = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (visited[i] && visited[j])
start += arr[i][j];
if (visited[i] == false && visited[j] == false)
link += arr[i][j];
}
}
int min = abs(start - link); // 스타트 팀과 링크 팀의 능력치 차이
if (ans > min || ans == -1) // 처음 ans 계산과 능력치 차이의 최소
ans = min;
} else {
for (int i = num; i < N; i++) {
if (!visited[i]) {
visited[i] = true;
dfs(depth + 1, i + 1); // 시간 초과 방지 + 중복방지, 오름차순 dfs
visited[i] = false;
}
}
}
}
int main(void)
{
// 스타트와 링크
ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> N;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> arr[i][j];
}
}
dfs(0, 0);
cout << ans << '\n';
}