#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문을 돌면서,
속성의 데이터 타입은 INT(정수), SMALLINT(INT보다 작은 정수), CHAR(n)(길이가 n인 고정 길이의 문자열), VARCHAR(n)(최대 길이가 n인 가변 길이의 문자열), NUMERIC(p, s)(고정 소수점 실수, p는 소수점을 제외한 전체 숫자의 길이고, s는 소수점 이하 숫자의 길이), FLOAT(n)(길이가 n인 부동 소수점 실수), REAL(부동 소수점 실수), DATE(연, 월, 일로 표현되는 날짜), TIME(시, 분, 초로 표현되는 시간), DATETIME(날짜와 시간) 등이 있습니다.
ON DELETE 옵션에는 NO ACTION(튜플을 삭제하지 못하게 함), CASCADE(관련 튜플을 함께 삭제함), SET NULL(관련 튜플의 외래키 값을 NULL로 변경함), SET DEFAULT(관련 튜플의 외래키 값을 미리 지정한 기본 값으로 변경함)이 있습니다.
ON UPDATE 옵션에는 NO ACTION(튜플을 변경하지 못하도록 함), CASCADE(관련 튜플에서 외래키 값을 함께 변경함), SET NULL(관련 튜플의 외래키 값을 NULL로 변경함), SET DEFAULT(관련 튜플의 외래키 값을 미리 지정한 기본 값으로 변경함)이 있습니다.
3. ALTER
새로운 속성의 추가
ALTER TABLE 테이블이름 ADD 속성이름 데이터타입 [NOT NULL] [DEFAULT 기본값];
#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번째 계단을 밟았을 때의 점수 중에서 큰 값을 출력합니다.
2. 화살표 case 라벨, 다중 case 라벨 (switch1, enhancedSwitch1)
switch (day) {
case MONDAY:
case FRIDAY:
case SUNDAY:
System.out.println(6);
break;
case TUESDAY:
System.out.println(7);
break;
case THURSDAY:
case SATURDAY:
System.out.println(8);
break;
case WEDNESDAY:
System.out.println(9);
break;
}
day의 길이를 출력하는 기존 switch 문 예제입니다.
day가 MONDAY, FRIDAY, SUNDAY인 경우 fall through를 이용하여 6을 출력하는 것을 볼 수 있습니다.
이를 화살표 case 라벨과 다중 case 라벨을 사용한 개선된 switch문으로 바꾸면 아래와 같습니다.
switch (day) {
case MONDAY, FRIDAY, SUNDAY -> System.out.println(6);
case TUESDAY -> System.out.println(7);
case THURSDAY, SATURDAY -> System.out.println(8);
case WEDNESDAY -> System.out.println(9);
}
fall through를 사용하지 않고 다중 case 라벨(,)을 사용하여 case MONDAY, FRIDAY, SUNDAY라고 표현한 것이 훨씬 가독성이 좋습니다.
또, 화살표 case 라벨(->)을 사용하면 마지막에 break를 사용한 것과 동일합니다.
이때 주의해야 할 점은 case 라벨(:)을 사용할 때는 실행문이 여러 개여도 중괄호({})로 묶어줄 필요가 없었지만,
화살표 case 라벨(->)을 사용할 때 실행문이 여러 개(즉, 2줄 이상)일 때는 중괄호로 묶어줘야 합니다.
한마디로 화살표 case 라벨(->)을 사용할 때는 if 문이나 for 문처럼 실행문이 1줄일 때만 중괄호를 생략할 수 있습니다.
3. switch 연산식 (switch2, enhancedSwitch2)
int numLetters;
switch (day) {
case MONDAY:
case FRIDAY:
case SUNDAY:
numLetters = 6;
break;
case TUESDAY:
numLetters = 7;
break;
case THURSDAY:
case SATURDAY:
numLetters = 8;
break;
case WEDNESDAY:
numLetters = 9;
break;
default:
numLetters = -1;
}
numLetters 변수에 day의 길이를 저장하는 기존 switch 문 예제입니다.
case 문에서 numLetters 변수에 값을 저장하는 방식을 사용해야 합니다.
이를 switch 연산식을 사용한 향상된 switch 문으로 바꾸면 아래와 같습니다.
int numLetters = switch (day) {
case MONDAY, FRIDAY, SUNDAY -> 6;
case TUESDAY -> 7;
case THURSDAY, SATURDAY -> 8;
case WEDNESDAY -> 9;
};
화살표 case 라벨(->) 뒤에 있는 값을 return하여 numLetters에 바로 대입할 수 있습니다.
만약 case TUESDAY -> 7;에서 7을 System.out.println(7)이나 "Seven" 등으로 바꾸면 int type이 아니므로 에러가 발생합니다.
numLetters의 type을 Object로 바꿔주면 "Seven"은 가능하지만,
System.out.println(7)은 return type이 void이므로 여전히 에러가 발생합니다.
즉, switch 연산식을 사용할 때 화살표 case 라벨(->) 뒤에 있는 값이 void type이면 에러가 발생합니다.
4. yield 예약어 사용 (enhancedSwitch3, enhancedSwitch4)
yield는 키워드가 아니라 제한된 식별자(restricted identifier)이기 때문에 var처럼 식별자로 사용할 수 있습니다.
방금 전에 본 switch 연산식에서 길이를 return하기 전에 특정 메시지를 출력하고 싶으면 아래와 같이 사용하면 됩니다.
int numLetters = switch (day) {
case MONDAY, FRIDAY, SUNDAY -> {
System.out.print("Six ");
yield 6;
}
case TUESDAY -> 7;
case THURSDAY, SATURDAY -> 8;
case WEDNESDAY -> 9;
};
향상된 switch 문에서는 중괄호 안에서만 yield 예약어를 사용할 수 있습니다.
따라서 case TUESDAY -> yield 7; 이라고 하면 에러입니다.
int numLetters = switch (day) {
case MONDAY, FRIDAY, SUNDAY:
System.out.print("Six ");
yield 6;
case TUESDAY:
yield 7;
case THURSDAY, SATURDAY:
yield 8;
case WEDNESDAY:
yield 9;
};
yield 예약어는 case 라벨(:)에도 사용 가능합니다.
case 라벨(:)은 실행문이 여러 개일 때 중괄호를 사용하지 않아도 됩니다.
5. 열거 타입(enum)을 사용하는 이유
static int switchError(String s) {
return switch (s) {
case "MONDAY", "FRIDAY", "SUNDAY" -> 6;
case "TUESDAY" -> 7;
case "THURSDAY, SATURDAY" -> 8;
case "WEDNESDAY" -> 9;
default -> -1;
};
}
위의 메서드에서 default를 주석 처리하면 "'switch' expression does not cover all possible input values" 에러 메시지를 볼 수 있습니다.
가능한 모든 값에 대하여 일치하는 case 라벨이 하나라도 없으면 위와 같은 에러를 볼 수 있습니다.
위의 예제에서는 String type이므로 가능한 모든 값은 거의 무한대나 마찬가지입니다.
String대신 int type이고, default를 사용하지 않는다면 int 범위의 모든 값에 대하여 case를 사용해야 할 것입니다.
따라서 default를 사용하거나, 필요한 값들로 열거 타입(enum)을 만들어서 사용해야 합니다.
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을 사용하지 않았다는 표시를 해줍니다.
