#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int dis[20001];
const int INF = 2147483647;
vector<pair<int, int> > adj[20001];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int V, E, K;
cin >> V >> E >> K;
for (int i = 0; i < E; i++) {
int u, v, w;
cin >> u >> v >> w;
adj[u].push_back(make_pair(w, v));
}
fill(dis, dis + V + 1, INF);
dis[K] = 0;
priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
pq.push(make_pair(dis[K], K));
while (!pq.empty()) {
pair<int, int> cur = pq.top();
pq.pop();
int dist = cur.first;
int idx = cur.second;
if (dis[idx] != dist)
continue;
for (int i = 0; i < adj[idx].size(); i++) {
pair<int, int> next = adj[idx][i];
int cost = next.first;
int nidx = next.second;
if (dis[nidx] > dist + cost) {
dis[nidx] = dist + cost;
pq.push(make_pair(dis[nidx], nidx));
}
}
}
for (int i = 1; i <= V; i++) {
if (dis[i] == INF)
cout << "INF\n";
else
cout << dis[i] << "\n";
}
return 0;
}
7번 라인 : 시작점에서 다른 모든 정점으로의 최단거리를 저장할 배열 dis를 선언합니다. 정점의 최대 개수가 20000이므로 dis[20000]으로 접근할 수 있도록 20001의 크기로 선언했습니다.
8번 라인 : 무한대를 표현하기 위해 int의 최댓값을 INF라는 상수로 선언했습니다.
9번 라인 : 간선을 인접리스트형태로 저장하기 위해 vector 배열 adj을 선언했습니다. 정점 번호와 가중치를 함께 저장해야 하기 때문에 pair를 사용했습니다.
20번 라인 : 입력받은 간선을 adj에 추가합니다. 아래에서 priority queue를 사용하여 min heap을 만들 때 가중치를 기준으로 정렬해야 하므로 가중치(w), 정점 번호(v)순으로 pair를 만들어서 추가합니다.
22번 라인 : dis배열을 INF로 초기화합니다.
24번 라인 : 시작점에서 시작점으로의 거리는 문제에서 제시한대로 0으로 바꿔줍니다.
25번 라인 : priority_queue를 선언합니다. priority_queue<자료형, 구현체, 비교 연산자>의 형태로 사용해야 하므로 구현체는 기본값인 vector를 사용했고, 비교 연산자는 greater를 사용하여 min heap을 만들었습니다. (참고 링크 : koosaga.com/9)
26번 라인 : pq에 시작점을 추가합니다.
27번 라인 : 힙이 비어있지 않는 동안
28 ~ 31번 라인 : 가중치가 가장 작은 간선을 꺼내서 dis에 가중치를, idx에 정점을 저장합니다.
32 ~ 33번 라인 : dis[idx]와 dist가 다르면, 이전에 저장할 때보다 더 짧은 경로를 찾은 것이므로 continue합니다.
34번 라인 : 인접 리스트에서 idx번 정점과 연결되어 있는 간선을 모두 돌면서
35 ~ 37번 라인 : cost에 가중치, nidx에 다음 정점을 저장하고,
38번 라인 : 현재 저장되어 있는 최단 거리(dis[nidx])보다 dist + cost한 값이 작으면
39 ~ 40번 라인 : dis[nidx]에 dist + cost를 저장하여 최단 거리를 갱신하고, pq에 추가합니다.
44 ~ 49번 라인 : 1번 정점부터 V번 정점까지 돌면서 경로가 존재하지 않는 경우에는 INF를 출력하고, 시작점부터 i번째 점까지의 최단 거리를 출력합니다.
도착점(N, M)과 0(이동할 수 없는 칸)과 1(이동할 수 있는 칸)로 이루어진 미로를 입력받은 후,
출발점(1, 1)에서 도착점까지 최단 거리를 출력하는 문제입니다. 따라서 bfs를 사용해야 합니다.
칸을 셀 때에는 시작 위치와 도착 위치도 포함해야 합니다.
3. 소스코드
BOJ 2178번 미로 탐색 C++ 풀이입니다.
#include <iostream>
#include <queue>
using namespace std;
string map[100];
int dis[100][100];
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
int N, M;
queue<pair<int, int> > q;
cin >> N >> M;
for (int i = 0; i < N; i++)
cin >> map[i];
q.push(make_pair(0, 0));
dis[0][0] = 1;
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int i = 0; i < 4; i++) {
int nx = x + dx[i];
int ny = y + dy[i];
if (0 <= nx && nx < N && 0 <= ny && ny < M
&& dis[nx][ny] == 0 && map[nx][ny] == '1') {
q.push(make_pair(nx, ny));
dis[nx][ny] = dis[x][y] + 1;
}
}
}
cout << dis[N - 1][M - 1];
return 0;
}
5번 라인 : 미로를 이루고 있는 수들은 붙어서 입력으로 주어지므로 string을 이용하여 한 줄씩 처리하기 위해 string배열을 선언했습니다.
6번 라인 : 방문여부를 체크하고, 거리를 저장할 배열 dis를 이차원 배열로 선언합니다.
7, 8번 라인 : 미로를 그래프로 생각해보면 연결된 정점은 상, 하, 좌, 우 이므로 4방향 좌표를 미리 선언합니다.
15번 라인 : 좌표 형식으로 이루어져 있으므로 queue<pair<int, int>>로 선언합니다.
17, 18번 라인 : 미로를 한줄씩 입력받아 string 배열인 map에 저장합니다.
20번 라인 : 시작점을 make_pair(0, 0)을 이용해 만든 후 q에 push합니다.
21번 라인 : 시작점도 칸을 셀 때 포함해야 하므로 dis[0][0]을 1로 바꿔줍니다.
22번 라인 : q가 비어있지 않는 동안
23번 라인 : x에 현재 방문한 x좌표(q.front().first)를 저장합니다.
24번 라인 : y에 현재 방문한 y좌표(q.front().second)를 저장합니다.
25번 라인 : q.pop()을 이용하여 q에서 빼주고,
26번 라인 : 총 4번(상, 하, 좌, 우) 돌면서
27번 라인 : nx에 다음에 방문할 x좌표(x + dx[i])를 저장하고,
28번 라인 : ny에 다음에 방문할 y좌표(y + dy[i])를 저장합니다.
29번 라인 : nx와 ny가 미로의 범위 안에 있고,
30번 라인 : nx, ny를 방문한 적이 없고 (dis[nx][ny] == 0), 이동할 수 있는 칸(map[nx][ny] == '1')이면,
31번 라인 : make_pair(nx, ny)를 이용해 q에 push한 후,
32번 라인 : dis[nx][ny]는 현재 방문한 좌표의 거리(dis[x][y])에 1을 더하여 저장합니다.
36번 라인 : bfs를 이용했으므로 dis[N - 1][M - 1]에는 (0,0)에서 (N, M)까지의 최단 거리가 저장되어 있고, 이를 출력합니다.
정점의 개수, 간선의 개수, 탐색을 시작할 정점의 번호, 간선이 연결하는 두 정점의 번호를 입력받아서
DFS를 수행한 결과와 BFS를 수행한 결과를 출력하는 문제입니다.
방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문해야 합니다.
3. 소스코드
BOJ 1260번 DFS와 BFS C++ 풀이입니다.
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
vector<int> e[1001];
bool check[1001];
void dfs(int v) {
check[v] = true;
cout << v << " ";
for (int i = 0; i < e[v].size(); i++) {
int next = e[v][i];
if (!check[next])
dfs(next);
}
}
void bfs(int v) {
queue<int> q;
q.push(v);
check[v] = true;
while (!q.empty()) {
int cur = q.front();
q.pop();
cout << cur << " ";
for (int i = 0; i < e[cur].size(); i++) {
int next = e[cur][i];
if (!check[next]) {
check[next] = true;
q.push(next);
}
}
}
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
int N, M, V, from, to;
cin >> N >> M >> V;
for (int i = 0; i < M; i++) {
cin >> from >> to;
e[from].push_back(to);
e[to].push_back(from);
}
for (int i = 1; i <= N; i++)
sort(e[i].begin(), e[i].end());
dfs(V);
cout << '\n';
memset(check, false, sizeof(check));
bfs(V);
return 0;
}
8번 라인 : 인접 리스트를 저장할 vector를 정점의 최대 개수가 1000이므로 e[1000]으로 접근할 수 있도록 1001의 크기로 선언했습니다.
9번 라인 : 정점의 방문을 체크할 배열 check도 마찬가지 이유로 1001의 크기로 선언했습니다.
45 ~ 49번 라인 : 입력으로 주어지는 간선은 양방향이므로 인접 리스트에 양방향으로 저장합니다.
51 ~ 52번 라인 : 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문해야 하기 때문에 오름차순으로 정렬합니다.
53번 라인 : 탐색을 시작할 정점 V를 넘겨주면서 dfs 함수를 호출합니다.
11 ~ 19번 라인 : 재귀함수를 이용한 dfs입니다.
12번 라인 : 정점을 방문할 때 마다 check[v]를 true로 바꿔주면서 방문한 것을 표시하고,
13번 라인 : 해당 정점을 출력합니다.
14번 라인 : 다음에 방문할 정점을 찾기 위해 현재 방문한 정점과 이어져 있는 정점의 개수만큼 for문을 돌면서,
15번 라인 : next변수에 현재 방문한 정점과 이어져 있는 정점을 저장하고,
16번 라인 : next정점을 방문한 적이 없으면(check[next] == false)
17번 라인 : next정점을 넘겨주면서 dfs 함수를 호출합니다.
55번 라인 : check 배열을 다시 false로 초기화하기 위해 memset함수를 이용합니다.
56번 라인 : 탐색을 시작할 정점 V를 넘겨주면서 bfs 함수를 호출합니다.
21 ~ 37번 라인 : queue를 이용한 bfs입니다.
23번 라인 : 처음 방문한 정점 v를 q에 push합니다.
25번 라인 : 처음 방문한 정점을 표시하기 위해 check[v]를 true로 바꿔줍니다.
25번 라인 : q가 비어있지 않는 동안
26번 라인 : cur변수에 현재 방문한 정점을 q.front()를 이용하여 저장하고,
27번 라인 : q.pop()을 이용하여 q에서 빼주고,
28번 라인 : 현재 방문한 정점을 출력합니다.
29번 라인 : 다음에 방문할 정점을 찾기 위해 현재 방문한 정점과 이어져 있는 정점의 개수만큼 for문을 돌면서,
#include <iostream>
#include <algorithm>
using namespace std;
int d[1000];
int a[1000];
int main(void)
{
ios::sync_with_stdio(0);
cin.tie(0);
int N;
cin >> N;
for (int i = 0; i < N; i++)
cin >> a[i];
d[0] = 1;
for (int i = 1; i < N; i++) {
d[i] = 1;
for (int j = 0; j < i; j++) {
if (a[j] < a[i])
d[i] = max(d[i], d[j] + 1);
}
}
cout << *max_element(d, d + N);
return 0;
}
5번 라인 : 다이나믹 프로그래밍으로 문제를 풀기 위해 길이가 수열의 크기의 최댓값(1000)인 배열을 선언했습니다. d[i]에는 i번째 수열의 항을 마지막으로 포함하는 부분 수열의 길이의 최댓값을 저장합니다.
6번 라인 : 수열의 각 항의 값을 입력받기 길이가 1000인 배열을 선언했습니다.
16번 라인 : 수열의 각 항의 값을 입력받아 배열 a에 저장합니다.
18번 라인 : d[0]은 0번째 항을 마지막으로 포함하는 부분 수열의 길이의 최댓값이므로 {a[0]}을 의미합니다. 따라서 1을 저장합니다.
19번 라인 : i = 1부터 N - 1까지 for문을 돌 때
20번 라인 : d[i]의 최솟값은 {a[i]}로 길이가 1이므로 일단 1로 초기화합니다.
21번 라인 : d[i]는 i번째 항을 마지막으로 포함하는 부분 수열의 길이의 최댓값이므로 for문을 이용해 j = 0부터 j < i까지 돌면서,
22번 라인 : j번째 수열의 항이 i번째 수열의 항보다 작다면 (예를 들어, a = {10, 30, 20}이고 i = 2라면 j = 0일 때는 10(a[j]) < 20(a[i])이므로 증가하는 부분 수열이 성립하지만, j = 1일 때는 30(a[j]) < 20(a[i])가 성립하지 않으므로 증가하는 부분 수열이 될 수 없습니다.)
23번 라인 : d[i]는 현재까지 i번째 항을 마지막으로 포함하는 부분 수열의 길이의 최댓값(d[i])과, j번째 항을 마지막으로 포함하는 부분 수열의 길이의 최댓값(d[j])에 i번째 항을 추가한 값인 d[j] + 1 중에서 큰 값을 d[i]에 저장합니다.
26번 라인 : d[0] ~ d[N - 1]까지의 값 중에서 최댓값을 출력하면 되고, 이를 구하기 위해 max_element함수를 사용했습니다.
계단의 개수와 각 계단의 점수를 입력받아, 계단 오르기 게임에서 얻을 수 있는 총점수의 최댓값을 출력하는 문제입니다.
계단 오르기 게임의 규칙은 다음과 같습니다.
1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.
다이나믹 프로그래밍으로 풀 수 있는 문제입니다.
3. 소스코드
BOJ 2579번 계단 오르기 C++ 풀이입니다.
#include <iostream>
#include <algorithm>
using namespace std;
int d[300][2];
int step[300];
int main(void)
{
ios::sync_with_stdio(0);
cin.tie(0);
int n;
cin >> n;
for (int i = 0; i < n; i++)
cin >> step[i];
d[0][0] = step[0];
d[1][0] = step[1];
d[1][1] = step[0] + step[1];
for (int i = 2; i < n; i++) {
d[i][0] = max(d[i - 2][0], d[i - 2][1]) + step[i];
d[i][1] = d[i - 1][0] + step[i];
}
cout << max(d[n - 1][0], d[n - 1][1]);
return 0;
}
5번 라인 : 다이나믹 프로그래밍으로 문제를 풀기 위해 계단의 개수의 최댓값인 300크기의 int형 배열을 선언합니다. 계단 오르기 게임의 규칙이 한 번에 한 계단씩 또는 두 계단씩 오를 수 있고, 연속된 세 개의 계단을 모두 밟아서는 안 되므로, 이 조건을 검사하기 위해 d[i][0]에는 계단을 연속해서 밟지 않는 경우(즉, i -2번째 계단을 밟은 후 i번째 계단을 밟는 경우)의 최대 점수값을 저장하고, d[i][1]에는 계단을 연속해서 밟는 경우(즉, i - 1번째 계단을 밟은 후, i번째 계단을 밟는 경우)의 최대 점수 값을 저장합니다.
6번 라인 : 각 계단의 점수를 저장할 step 배열을 선언합니다. 역시 계단의 개수의 최댓값이 300이므로 크기는 300으로 선언했습니다. d배열과 step배열 모두 0으로 초기화하기 위해 전역변수로 선언했습니다.
16번 라인 : 각 계단의 점수를 입력받아 step배열에 저장합니다. 문제에서는 1번째부터 시작하지만 편의를 위해 0번째부터 저장했습니다.
18번 라인 : 0번째 계단은 연속해서 밟을 수 없으므로 d[0][0]만 가능하므로 d[0][0]에 0번째 계단의 점수를 저장합니다.
19번 라인 : 1번째 계단은 연속해서 밟지 않는 경우 바로 1번째 계단을 밟는 것이기 때문에 d[1][0]에 1번째 계단의 점수를 저장합니다.
20번 라인 : 1번째 계단은 연속해서 밟는 경우, 0번째 계단, 1번째 계단을 밟는 것이기 때문에 d[1][1]에 0번째 계단의 점수와 1번째 계단의 점수의 합을 저장합니다.
21번 라인 : 2번째 계단부터 n - 1번째 계단까지 for문을 돌면서
22번 라인 : d[i][0]번째 계단에는 계단을 연속해서 밟지 않는 경우를 저장하기 때문에, i-2번째 계단을 밟은 후, i번째 계단을 밟는 경우입니다. 따라서 i-2번째 계단을 밟을 때 얻을 수 있는 점수인 d[i - 2][0]과 d[i - 2][1] 중에서 큰 값과 i번째 계단의 값을 더해서 저장합니다.
23번 라인 : d[i][1]번째 계단에는 계단을 연속해서 밟는 경우를 저장하기 때문에 i-1번째 계단을 밟은 후, i번째 계단을 밟는 경우입니다. 연속된 세 개의 계단을 밟을 수 없으므로 d[i - 1][1]을 선택할 수 없습니다. 따라서 d[i - 1][0]에 저장된 점수에 i번째 계단의 값을 더해서 저장합니다.
25번 라인 : 계단의 점수를 입력받을 때 0번째 부터 입력받았으므로, 최종적으로 n - 1번째 계단을 밟았을 때의 점수 중에서 큰 값을 출력합니다.
11번 라인 : 스도쿠는 9행이므로 row는 0 ~ 8인데 9가 되었으면 모든 행에 숫자를 넣어본 것이기 때문에
12 ~ 16번 라인 : 스도쿠를 출력하고,
17번 라인 : 스도쿠 판을 채우는 방법이 여럿인 경우에는 그중 하나만 출력해야 하기 때문에 프로그램을 종료합니다.
20번 라인 : map[row][col]이 0이 아닌 경우는 이미 숫자가 채워져 있기 때문에
21번 라인 : 다음칸(한 칸 오른쪽)을 확인하기 위해 sudoku(row, col + 1)을 호출합니다. 이때 col이 8인 경우 다음칸이 다음 열의 0번째 칸이기 때문에 sudoku(row + 1, 0)을 호출합니다.
22번 라인 : map[row][col]이 0인 경우 숫자를 채워봐야 하기 때문에
23번 라인 : 1부터 9까지 순서대로 for문을 돌립니다.
24, 25번 라인 : 같은 행에 이미 num을 사용했거나(check_row[row][num] == true), 같은 열에 이미 num을 사용했거나(check_col[col][num] == true), 같은 3 * 3으로 나눈 정사각형에 이미 num을 사용했으면(check_square[((row / 3) * 3) + (col / 3)][num] == true) 현재 칸(map[row][col])을 num으로 채울 수 없기 때문에 다음 숫자로 채워보기 위해 continue합니다.
26번 라인 : 24번 라인 if 조건의 값이 모두 false이면 현재 칸(map[row][col])을 num으로 채울 수 있으므로, map[row][col]에 num을 대입합니다.
27번 라인 : 현재 칸을 num으로 채웠으므로 현재 행에 num을 사용했다고 표시하기 위해 check_row[row][num]에 true를 대입합니다.
28번 라인 : 현재 칸을 num으로 채웠으므로 현재 열에 num을 사용했다고 표시하기 위해 check_col[col][num]에 true를 대입합니다.
29번 라인 : 현재 칸을 num으로 채웠으므로 현재 3 * 3으로 나눈 정사각형에 num을 사용했다고 표시하기 위해 check_square[((row / 3) * 3) + (col / 3)][num]에 true를 대입합니다.
30번 라인 : 현재 칸을 num으로 채웠으므로 다음 칸(한 칸 오른쪽)을 확인하기 위해 sudoku(row,col+1)을 호출합니다.이때 col이 8인 경우 다음칸이 다음 열의 0번째 칸이기 때문에 sudoku(row + 1, 0)을 호출합니다.
31번 라인 : 31번 라인이 실행될 때는 현재 칸을 num으로 채웠을 때의 경우의 수를 모두 실행해본 후 돌아온 것이기 때문에, 현재 칸을 num보다 큰 다른 숫자로 채웠을 경우의 수를 확인해보기 위해서 map[row][col]에 0을 대입하여 num을 지웁니다.
32, 33, 34번 라인 : map[row][col]에 num을 사용하지 않으므로, check_row[row][num], check_col[col][num], check_square[((row / 3) * 3) + (col / 3)][num]에 false를 대입해서 num을 사용하지 않았다는 표시를 해줍니다.
N을 입력받아 크기가 N * N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓을 수 있는 방법의 수를 출력하는 문제입니다.
퀸이 서로 공격할 수 없게 놓으려면 각각의 퀸이 다음 세 가지 조건을 모두 만족해야 합니다.
1. 한 행(row)에는 하나의 퀸만 있어야 한다.
2. 한 열(col)에는 하나의 퀸만 있어야 한다.
3. 대각선(diagonal)에는 하나의 퀸만 있어야 한다.
(0,0)
(0,1) ♛
(0,2)
(0,3)
(1,0)
(1,1)
(1,2)
(1,3) ♛
(2,0) ♛
(2,1)
(2,2)
(2,3)
(3,0)
(3,1)
(3,2) ♛
(3,3)
N이 4일 때 퀸을 놓을 수 있는 방법 중 하나입니다.
1번 조건은 for문을 돌면서 한 행에 하나의 퀸만 놓아보면 되므로 생각하지 않아도 됩니다.
2번 조건은 현재 퀸이 놓여있는 열의 위치를 저장해놓는 bool check_col[15]배열을 만들고,
퀸이 있으면 true, 없으면 false로 표현해서 퀸을 놓기 전에 해당 열에 퀸이 있는지 확인해보면 됩니다.
3번 조건은 북동쪽 방향 대각선(왼쪽 아래에서 오른쪽 위)와, 남동쪽 방향 대각선(왼쪽 위에서 오른쪽 아래)을 모두 확인해봐야 합니다.
먼저, 같은 북동 대각선에 있는 경우 row + col의 값이 같은 것을 알 수 있습니다.
이 값의 범위는 0 ~ 2 * (N - 1)이므로 현재 퀸이 놓여있는 북동 대각선의 위치를 저장해놓는 bool check_diag_ne[30]배열을 만들고,
퀸이 있으면 true, 없으면 false로 표현해서 퀸을 놓기 전에 해당 북동 대각선에 퀸이 있는지 확인해보면 됩니다.
다음으로, 같은 남동쪽 방향 대각선(왼쪽 위에서 오른쪽 아래)에 있는 경우 row - col의 값이 같은 것을 알 수 있습니다.
이 값의 범위는 -(N - 1) ~ (N - 1)인데, 배열의 인덱스로 사용하기 위해 N을 더해주면 1 ~ (2 * N) - 1이므로
현재 퀸이 놓여있는 남동 대각선의 위치를 저장해놓는 bool check_diag_se[30]배열을 만들고,
퀸이 있으면 true, 없으면 false로 표현해서 퀸을 놓기 전에 해당 남동 대각선에 퀸이 있는지 확인해보면 됩니다.
3. 소스코드
BOJ 9663번 N-Queen C++ 풀이입니다.
#include <iostream>
using namespace std;
int N, cnt;
bool check_col[15];
bool check_diag_ne[30];
bool check_diag_se[30];
void nqueen(int row)
{
if (row == N) {
cnt++;
return;
}
for (int col = 0; col < N; col++) {
if (check_col[col] || check_diag_ne[row + col] || check_diag_se[row - col + N])
continue;
check_col[col] = true;
check_diag_ne[row + col] = true;
check_diag_se[row - col + N] = true;
nqueen(row + 1);
check_col[col] = false;
check_diag_ne[row + col] = false;
check_diag_se[row - col + N] = false;
}
}
int main(void)
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N;
nqueen(0);
cout << cnt;
return 0;
}
4번 라인 : N을 입력받을 int N과, 최종 정답을 출력할 int cnt를 선언합니다.
5번 라인 : 현재 퀸이 놓여있는 열을 체크하기 위해서 bool check_col[15]를 선언합니다.
6번 라인 : 현재 퀸이 놓여있는 북동쪽 방향 대각선(왼쪽 아래에서 오른쪽 위)을 체크하기 위해서 check_diag_ne[30]을 선언합니다.
7번 라인 : 현재 퀸이 놓여있는 남동쪽 방향 대각선(왼쪽 위에서 오른쪽 아래)을 체크하기 위해서 check_diag_se[30]을 선언합니다.
36번 라인 : 0번째 row부터 퀸을 놓아보기 위해서 nqueen(0)을 호출합니다.
11번 라인 : row가 N이면 퀸을 마지막 행까지 놓을 수 있는 것이기 때문에 cnt를 1 증가시키고 return 시킵니다.
16번 라인 : 현재 행의 몇번째 열에 퀸을 놓을지 결정하기 위해 0부터 N - 1까지 for문을 돌립니다.
17, 18번 라인 : 같은 열에 이미 퀸이 있거나(check_col[col] == true), 북동쪽 방향 대각선에 퀸이 있거나(check_diag_ne[row + col] == true), 남동쪽 방향 대각선에 퀸이 있으면(check_diag_se[row - col + N]) 현재 열에는 퀸을 놓을 수 없으므로 다음 열에 퀸을 놓아보기 위해서 continue합니다.
19, 20, 21번 라인 : 17번 라인 if조건의 값이 모두 false이면 현재 열에는 퀸을 놓을 수 있으므로, 퀸을 놓았다는 표시로 check_col[col], check_diag_ne[row + col], check_diag_se[row - col + N] 에 true를 대입합니다.
22번 라인 : 현재 행에 퀸을 놓았으므로 다음 행에 퀸을 놓아보기 위해 nqueen(row + 1)을 호출합니다.
23, 24, 25번 라인 : 23번 라인이 실행될 때는 현재 열에 퀸을 놓았을 때의 경우의 수를 모두 실행해본 후 돌아온 것이기 때문에 현재 열에 퀸을 놓지 않았을 때의 경우의 수를 확인해보기 위해서 퀸을 놓지 않았다는 표시로 check_col[col], check_diag_ne[row + col], check_diag_se[row - col + N] 에 false를 대입합니다.