코딩하는 두꺼비

www.acmicpc.net/problem/9663

백트래킹의 대표적인 문제이다.

처음엔 2차원배열로 풀려고 했는데 결국 실패해서 힌트를 보고 풀 수 있었다. 어차피 하나의 열과 하나의 행에 하나의 퀸만 놓을 수 있기 떄문에 1차원 배열로 풀 수 있는 문제였다.

대각선 처리가 좀 까다로웠는데 각 행의 차이와 열의 차이가 동일하지 않는 다는 것을 아는 것이 포인트였다.

참고: chanhuiseok.github.io/posts/baek-1/

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

int N, ans;
int map[16];

void dfs(int cnt) {
	int check = 0;
	if (cnt == N) {
		ans++;
		return;
	}
	for (int i = 0; i < N; i++) {
		map[cnt] = i;
		for (int j = 0; j < cnt; j++) {
			if (map[j] == map[cnt] || cnt - j == abs(map[cnt] - map[j])) {
				check = 1;
				break;
			}
		}
		if (check == 0) {
			dfs(cnt + 1);
		}
		else {
			check = 0;
		}
	}

}

int main() {
	cin >> N;
	dfs(0);
	cout << ans;
	return 0;
}

www.acmicpc.net/problem/17070

문제 자체는 DP로 분류되어 있었는데 dfs로 푸니까 간단하게 풀린 문제였다.

처음에 DP로 풀려고 하다가 시간을 많이 사용했는데 이런걸 생각하면 너무 분류에 집중해서 풀지 않아도 될 것 같다!

푸는 방법은 일단 파이프를 가로, 세로, 대각선 3가지 모드가 있다고 생각하고 각 모드에 맞게 모든 경우의 수를 진행해주었다. 크기가 최대 16*16이라 DFS가 터지지 않을 것 같았다.

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

int n, ans;
int map[17][17];

void dfs(int x, int y, int mode) {
	if (x == n && y == n) {
		ans++;
		return;
	}
	if (mode == 0 || mode == 2) {
		if (y + 1 <= n && map[x][y + 1] == 0) {
			dfs(x, y + 1, 0);
		}
	}
	if (mode == 1 || mode == 2) {
		if (x + 1 <= n && map[x + 1][y] == 0) {
			dfs(x + 1, y, 1);
		}
	}
	if (x + 1 <= n && y + 1 <= n && map[x + 1][y + 1] == 0 
		&& map[x][y+1] == 0 && map[x+1][y] == 0) {
		dfs(x + 1, y + 1, 2);
	}
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> map[i][j];
		}
	}
	dfs(1, 2, 0);
	cout << ans;
	return 0;
}

www.acmicpc.net/problem/14716

그냥 전형적인 dfs/bfs문제였다. 섬 갯수 세는 문제와 매우 유사했다.

단, 4방향이 아닌 8방향을 고려하는 것만 조심하면 쉬운 문제였다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

queue<pair<int, int>> q;
int map[1000][250];
int ans, m, n;
int dx[8] = { -1,-1,-1,0,0,1,1,1 };
int dy[8] = { -1,0,1,-1,1,-1,0,1 };

void bfs(int x, int y) {
	q.push({ x, y });
	map[x][y] = 0;
	while (!q.empty()) {
		int a = q.front().first;
		int b = q.front().second;
		q.pop();
		for (int i = 0; i < 8; i++) {
			if (a + dx[i] >= 0 && a + dx[i] < m && b + dy[i] >= 0 && b + dy[i] < n
				&& map[a + dx[i]][b + dy[i]] == 1) {
				map[a + dx[i]][b + dy[i]] = 0;
				q.push({ a + dx[i], b + dy[i] });
			}
		}
	}
	ans++;
	return;
}

int main() {
	cin >> m >> n;
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
		}
	}
	for (int i = 0; i < m; i++) {
		for (int j = 0; j < n; j++) {
			if (map[i][j] == 1) {
				bfs(i, j);
			}
		}
	}
	cout << ans;
	return 0;
}