congcoding

1. 문제 링크

www.acmicpc.net/problem/2580

2. 문제 설명

빈칸이 0으로 표시된 스도쿠판을 입력받은 후, 모든 빈칸이 채워진 스도쿠 판의 최종 모습을 출력하는 문제입니다.

스도쿠 판을 규칙대로 채울 수 없는 경우의 입력은 주어지지 않고, 스도쿠 판을 채우는 방법이 여럿인 경우에는 그중 하나만 출력하면 됩니다.

스도쿠판을 채우려면 다음 세 가지 조건을 모두 만족해야 합니다.

1. 한 행(row)에는 1부터 9까지 숫자가 한 번씩만 사용되어야 한다.

2. 한 열(col)에는 1부터 9까지 숫자가 한 번씩만 사용되어야 한다.

3. 3 * 3으로 나눈 정사각형 안에는 1부터 9까지 숫자가 한 번씩만 사용되어야 한다.

스도쿠판을 2차원 배열로 표현한 표 입니다.

괄호 안의 숫자는 행과 열을 나타내고, 괄호 옆의 숫자는 몇 번째 3 * 3으로 나눈 정사각형인지 표시했습니다.

1번 조건을 확인하기 위해 bool check_row[9][10]배열을 만들어서 각각의 row에 1부터 9까지 숫자가 쓰였으면,

check_row[row][num]을 true로, 안 쓰였으면 false로 표시합니다.

넣을 수 있는 숫자가 1 ~ 9이므로 이 숫자를 그대로 index로 사용하기 위해 10칸으로 선언해줍니다. 

예를 들어 스도쿠의 0번째 행이 문제에서 제공하는 예제처럼 0, 3, 5, 4, 6, 9, 2, 7, 8인 경우

check_row[0] = [false, false, true, true, true, true, true, true, true, true] 입니다.

check_row[0][0]은 사용하지 않는 칸이므로 처음 초기화 된 대로 false이고,

check_row[0][1]은 0번째 행에 숫자 1이 사용되지 않았으므로 false입니다.

check_row[0][2]는 0번째 행에 숫자 2가 사용됐으므로 true입니다.

2번 조건은 1번 조건과 같은 방법으로 bool check_col[9][10]배열을 만들어 사용합니다.

예를 들어 스도쿠의 0번째 열이 문제에서 제공하는 예제처럼 0, 7, 0, 3, 8, 5, 9, 6, 2인 경우

check_col[0] = [false, false, true, true, false, true, true, true, true, true] 입니다.

3번 조건은 check_square[9][10]배열을 만들어서 각각의 square에 1부터 9까지 숫자가 쓰였으면,

check_square[square][num]을 true로, 안 쓰였으면 false로 표시합니다.

이 때, square(몇 번째 3 * 3으로 나눈 정사각형인지)을 row, col을 이용해서 구해보면 ((row / 3) * 3) + (col / 3)임을 알 수 있습니다.

예를 들어 스도쿠의 0번째 3 * 3으로 나눈 정사각형이 문제에서 제공하는 예제처럼 0, 3, 5, 7, 8, 2, 0, 6, 0인 경우

check_square[0] = [false, false, true, true, false, true, true, true, true, false] 입니다.

3. 소스코드

BOJ 2580번 스도쿠 C++ 풀이입니다.

#include <iostream>
using namespace std;

int map[9][9];
bool check_row[9][10];
bool check_col[9][10];
bool check_square[9][10];

void sudoku(int row, int col)
{
	if (row == 9) {
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++)
				cout << map[i][j] << ' ';
			cout << '\n';
		}
		exit(0);
	}

	if (map[row][col] != 0)
		col == 8 ? sudoku(row + 1, 0) : sudoku(row, col + 1);
	else {
		for (int num = 1; num <= 9; num++) {
			if (check_row[row][num] || check_col[col][num] || check_square[((row / 3) * 3) + (col / 3)][num])
				continue;
			map[row][col] = num;
			check_row[row][num] = true;
			check_col[col][num] = true;
			check_square[((row / 3) * 3) + (col / 3)][num] = true;
			col == 8 ? sudoku(row + 1, 0) : sudoku(row, col + 1);
			map[row][col] = 0;
			check_row[row][num] = false;
			check_col[col][num] = false;
			check_square[((row / 3) * 3) + (col / 3)][num] = false;
		}
	}
}

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	for (int i = 0; i < 9; i++) {
		for (int j = 0; j < 9; j++) {
			cin >> map[i][j];
			if (map[i][j] != 0) {
				check_row[i][map[i][j]] = true;
				check_col[j][map[i][j]] = true;
				check_square[((i / 3) * 3) + (j / 3)][map[i][j]] = true;
			}
		}
	}

	sudoku(0, 0);

	return 0;
}

4번 라인 : 스도쿠판을 저장할 배열 map[9][9]를 선언합니다.

5번 라인 : 현재 행에 사용된 숫자를 확인하기 위해 bool check_row[9][10]을 선언합니다.

6번 라인 : 현재 열에 사용된 숫자를 확인하기 위해 bool check_col[9][10]을 선언합니다.

7번 라인 : 현재 3 * 3 으로 나눈 정사각형에 사용된 숫자를 확인하기 위해 bool check_square[9][10]을 선언합니다.

44, 45, 46번 라인 : 스도쿠를 입력받습니다.

47번 라인 : 입력받은 수(map[i][j])가 0이 아니면,

48번 라인 : 현재 행 i에 숫자 map[i][j]이 사용되었음을 표시하기 위해 check_row[i][map[i][j]]에 true를 대입합니다.

49번 라인 : 현재 열 j에 숫자 map[i][j]이 사용되었음을 표시하기 위해 check_col[j][map[i][j]]에 true를 대입합니다.

50번 라인 : 현재 3 * 3으로 나눈 정사각형 ((i / 3) * 3) + (j / 3)에 숫자 map[i][j]이 사용되었음을 표시하기 위해

check_square[((i / 3) * 3) + (j / 3)][map[i][j]]에 true를 대입합니다.

55번 라인 : (0, 0)부터 스도쿠를 풀기 위해 sudoku(0, 0)을 호출합니다.

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을 사용하지 않았다는 표시를 해줍니다.

1. 문제 링크

www.acmicpc.net/problem/9663

2. 문제 설명

N을 입력받아 크기가 N * N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓을 수 있는 방법의 수를 출력하는 문제입니다.

퀸이 서로 공격할 수 없게 놓으려면 각각의 퀸이 다음 세 가지 조건을 모두 만족해야 합니다.

1. 한 행(row)에는 하나의 퀸만 있어야 한다.

2. 한 열(col)에는 하나의 퀸만 있어야 한다.

3. 대각선(diagonal)에는 하나의 퀸만 있어야 한다.

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를 대입합니다.

37번 라인 : 재귀가 끝났으므로 최종 결과를 출력합니다.

1. 문제 링크

www.acmicpc.net/problem/14888

2. 문제 설명

N개의 수와 N-1개의 연산자를 입력받은 후 만들 수 있는 식의 결과의 최댓값과 최솟값을 출력하는 문제입니다.

주어진 수의 순서를 바꾸면 안 되고, 식의 계산은 연산자 우선순위를 무시하고 왼쪽에서 오른쪽으로 진행해야 합니다.

따라서 연산자로 순열을 만들고 모든 경우의 수에 대하여 계산해보면 됩니다.

3. 소스코드

BOJ 14888번 연산자 끼워넣기 C++ 풀이입니다.

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

int main(void)
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N, temp, min_result = 1000000000, max_result = -100000000;
	vector<int> v, op;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> temp;
		v.push_back(temp);
	}
	for (int i = 0; i < 4; i++) {
		cin >> temp;
		for (int j = 0; j < temp; j++)
			op.push_back(i);
	}

	do {
		int result = v[0];
		for (int i = 0; i < N - 1; i++) {
			if (op[i] == 0)
				result += v[i + 1];
			else if (op[i] == 1)
				result -= v[i + 1];
			else if (op[i] == 2)
				result *= v[i + 1];
			else if (op[i] == 3)
				result /= v[i + 1];
		}
		min_result = min(min_result, result);
		max_result = max(max_result, result);
	} while (next_permutation(op.begin(), op.end()));
	cout << max_result << '\n' << min_result;

	return 0;
}

11번 라인 : 숫자의 개수 N, 임시로 사용할 변수 temp를 선언하고, 최솟값을 저장할 변수 min_result를 문제에서 주어진 최댓값인, 10억으로 초기화하고, 최댓값을 저장할 변수 max_result를 문제에서 주어진 최솟값인 -100으로 초기화합니다.

12번 라인 : 숫자를 저장할 vector v와 연산자를 저장할 vector op를 선언합니다.

13 ~ 17번 라인 : N과 v를 입력받습니다.

18 ~ 22번 라인 : op를 입력받습니다. 예를 들어 2, 1, 3, 1이 입력된다면 op vector에는 [0, 0, 1, 2, 2, 2, 3]이 입력되도록 이중 for문을 사용했습니다.

24, 38번 라인 : do ~ while문과 next_permutation을 이용해서 op vector로 만든 순열의 모든 경우의 수를 차례로 구합니다.

25번 라인 : 계산 결과를 저장할 result변수를 v[0](첫 번째 숫자)로 초기화합니다.

26 ~ 35번 라인 : i번째 op의 값에 따라 해당하는 연산자를 이용하여 result와 v[i + 1]을 연산합니다.

36번 라인 : min_result와 result값을 비교하여 더 작은 값을 min_result에 저장합니다.

37번 라인 : max_result와 result값을 비교하여 더 큰 값을 max_result에 저장합니다.

39번 라인 : max_result와 min_result를 출력합니다.