중급반 5주차 풀이 - DFS, BFS, 백트래킹

1. [1260] DFS와 BFS (Silver II)

DFS와 BFS를 구현하는 문제입니다.

사전순으로 방문해야 하니, 인접 리스트 adj를 정렬해야 합니다.

 

시간복잡도는 \( O(V+E) \)가 됩니다.

+ 인접 행렬을 사용할 경우, DFS와 BFS의 시간복잡도가 \( O(V^2) \)이 됩니다.

int n, m;
vector<int> adj[1020];

bool chk[1020];
void dfs(int now){
	chk[now] = 1; cout << now << ' ';
	for (int nxt : adj[now]){
		if (chk[nxt]){ continue; }
		dfs(nxt);
	}
}

int dis[1020];
void bfs(int st){
	memset(dis, -1, sizeof(dis));
	queue<pi2> q; q.push({st, 0}); dis[st] = 0;
	while (!q.empty()){
		int now = q.front().fr, dst = q.front().sc;
		q.pop();
		cout << now << ' ';
		for (int nxt : adj[now]){
			if (dis[nxt] != -1){ continue; }
			q.push({nxt, dst+1}); dis[nxt] = dst+1;
		}
	}
}

void Main(){
	int n, m, st; cin >> n >> m >> st;
	while (m--){
		int v, w; cin >> v >> w;
		adj[v].push_back(w); adj[w].push_back(v);
	}
	for (int i = 1; i <= n; i++){ sort(all(adj[i])); }
	dfs(st); cout << endl; bfs(st);
}

2. [2178] 미로 탐색 (Silver I)

2차원 배열에서 BFS를 돌려주면 됩니다.

이 때, \( (y, x) \)가 정점이 되고, \( (y, x) \leftrightarrow (y \pm 1, x) \)와 \( (y, x) \leftrightarrow (y, x \pm 1) \)이 간선이 됩니다.

 

입력이 붙어서 들어오는데, char를 사용해서 1글자씩 입력받을 수도 있고

아니면 string 배열로 맵을 저장할 수도 있습니다.

const int dy[4] = {-1, 0, 1, 0}, dx[4] = {0, 1, 0, -1};

int mp[120][120];
int dis[120][120];

void Main(){
	int n, m; cin >> n >> m;
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= m; j++){
			char ch; cin >> ch; mp[i][j] = ch-'0';
		}
	}
	memset(dis, -1, sizeof(dis));
	queue<pi3> q; q.push({ {1, 1}, 1 }); dis[1][1] = 1;
	while (!q.empty()){
		int y = q.front().fr.fr, x = q.front().fr.sc;
		int dst = q.front().sc; q.pop();
		if (y==n && x==m){ cout << dst; return; }
		for (int k = 0; k < 4; k++){
			int yy = y+dy[k], xx = x+dx[k];
			if (0 > yy || yy > n){ continue; }
			if (0 > xx || xx > m){ continue; }
			if (mp[yy][xx] == 0){ continue; }
			if (dis[yy][xx] != -1){ continue; }
			q.push({ {yy, xx}, dst+1 }); dis[yy][xx] = dst+1;
		}
	}
}

3. [9663] N-Queen (Gold V)

가능한 모든 경우의 수를 백트래킹으로 돌려주면 됩니다.

이러면 시간 초과가 뜰 것 같지만, 초반 부분에서 커팅되는 부분이 많아서 시간 내에 돌아갑니다.

TODO: 풀이 더 자세히 작성

 

시간복잡도는 커팅이 동반된 \( O(N!) \)입니다.

TODO: 더 작은 상한을 계산할 수 있을까?

int n;
bool mp[20][20];

bool pos(int y, int x){
	for (int yp = 1; yp <= y; yp++){
		if (mp[yp][x]){ return 0; }
		if (1 <= x-y+yp && mp[yp][x-y+yp]){ return 0; }
		if (x+y-yp <= n && mp[yp][x+y-yp]){ return 0; }
	}
	return 1;
}

int ans;
void btk(int y){
	if (y > n){ ans += 1; return; }
	for (int x = 1; x <= n; x++){
		if (pos(y, x)){
			mp[y][x] = 1; btk(y+1);
			mp[y][x] = 0;
		}
	}
}

void Main(){
	cin >> n;
	btk(1); cout << ans;
}

1번 풀이처럼 지금 설치하는 퀸이 다른 퀸을 보고 있는지 일일이 봐도 되지만,

같은 y / x / x+y / x-y 좌표에만 퀸이 없으면 되기 때문에 이를 따로 체크하면서 풀어도 됩니다.

 

이렇게 하면 속도가 굉장히 빨라집니다. (5592 ms → 1660 ms)

int n;
bool xc[20], d1c[40], d2c[40];

bool pos(int y, int x){
	if (xc[x]){ return 0; }
	if (d1c[x+y]){ return 0; }
	if (d2c[x-y+20]){ return 0; }
	return 1;
}

int ans;
void btk(int y){
	if (y > n){ ans += 1; return; }
	for (int x = 1; x <= n; x++){
		if (pos(y, x)){
			xc[x] = d1c[x+y] = d2c[x-y+20] = 1; btk(y+1);
			xc[x] = d1c[x+y] = d2c[x-y+20] = 0;
		}
	}
}

void Main(){
	cin >> n;
	btk(1); cout << ans;
}

이건 사실 풀이가 아니긴 한데...

 

\( N < 15 \)이기 때문에, 1부터 14까지의 모든 답을 로컬에서 미리 돌린 뒤 전처리해줄 수도 있습니다.

이 풀이는 (로컬에서 돌리는 시간 제외) 0 ms가 나옵니다.

int ans[20] = { 0,
	1, 0, 0, 2, 10,
	4, 40, 92, 352, 724,
	2680, 14200, 73712, 365596
};

void Main(){
	int n; cin >> n;
	cout << ans[n];
}

4. [11724] 연결 요소의 개수 (Silver II)

연결 요소 \( S \)는 아래와 같이 정의됩니다.

• 연결 요소 \( S \) 안의 임의의 두 정점 \( v, w \)에 대해 \( v \Rightarrow w \)의 경로가 존재한다.
• 연결 요소 \( S \) 안의 정점 \( v \)와 밖의 정점 \( w \)에 대해 \( v \Rightarrow w \)의 경로는 존재하지 않는다.

어떤 그래프에서의 연결 요소는 한 정점을 잡은 뒤 DFS를 돌려주면 찾을 수 있고,
연결 요소의 개수는 "모든 정점을 방문하기까지 필요한 DFS의 횟수"입니다.

 

+ 사실 BFS를 돌려도 결과가 동일하긴 합니다.

그런데 보통 DFS가 구현이 편해서 DFS를 사용하는 경우가 많습니다.

vector<int> adj[1020];

bool chk[1020];
void dfs(int now){
	chk[now] = 1;
	for (int nxt : adj[now]){
		if (chk[nxt]){ continue; }
		dfs(nxt);
	}
}

void Main(){
	int n, m; cin >> n >> m;
	while (m--){
		int v, w; cin >> v >> w;
		adj[v].push_back(w); adj[w].push_back(v);
	}
	int ans = 0;
	for (int v = 1; v <= n; v++){
		if (chk[v]){ continue; }
		dfs(v); ans += 1;
	}
	cout << ans;
}

5. [1012] 유기농 배추 (Silver II)

"[2178] 미로 탐색" + "[11724] 연결 요소의 개수"입니다.

연결 요소의 개수를 2차원 맵에서 세주면 됩니다.

 

풀이 역시 둘을 합한 건데, "배추가 있는" (y, x)를 모두 정점으로 변환하고 인접한 칸들을 간선으로 연결시킨 뒤
연결요소의 개수를 세주면 됩니다.

const int dy[4] = {-1, 0, 1, 0}, dx[4] = {0, 1, 0, -1};

int n, m, k;
int mp[60][60];

bool chk[60][60];
void dfs(int y, int x){
	chk[y][x] = 1;
	for (int k = 0; k < 4; k++){
		int yy = y+dy[k], xx = x+dx[k];
		if (0 > yy || yy >= n){ continue; }
		if (0 > xx || xx >= m){ continue; }
		if (mp[yy][xx] == 0){ continue; }
		if (chk[yy][xx]){ continue; }
		dfs(yy, xx);
	}
}

void Main(){
	int t; cin >> t;
	while (t--){
		memset(mp, 0, sizeof(mp)); memset(chk, 0, sizeof(chk));
		cin >> m >> n >> k;
		while (k--){
			int x, y; cin >> x >> y; mp[y][x] = 1;
		}
		int ans = 0;
		for (int y = 0; y < n; y++){
			for (int x = 0; x < m; x++){
				if (mp[y][x] == 0){ continue; }
				if (chk[y][x]){ continue; }
				dfs(y, x); ans += 1;
			}
		}
		cout << ans << endl;
	}
}

6. [2644] 촌수계산 (Silver II)

이런 저런 말이 나와있지만, 사람을 정점으로 보고 부모-자식 관계를 간선으로 보면

두 정점 간의 최단경로를 찾는 문제가 됩니다.

 

+ 사실 부부 관계 = 0촌이긴 한데, 문제 조건에 의해 부부 관계가 나올 수 없어서 무시해도 됩니다.

vector<int> adj[120];
int dis[120];

void Main(){
	memset(dis, -1, sizeof(dis));
	int n; cin >> n;
	int st, ed; cin >> st >> ed;
	int m; cin >> m;
	while (m--){
		int v, w; cin >> v >> w;
		adj[v].push_back(w); adj[w].push_back(v);
	}
	queue<pi2> q; q.push({st, 0}); dis[st] = 0;
	while (!q.empty()){
		int now = q.front().fr, dst = q.front().sc;
		q.pop();
		if (now == ed){ cout << dst; return; }
		for (int nxt : adj[now]){
			if (dis[nxt] != -1){ continue; }
			q.push({nxt, dst+1}); dis[nxt] = dst+1;
		}
	}
	cout << -1;
}

7. [2583] 영역 구하기 (Silver I)

[y, x] = (x, y)에서 시작해서 (x+1, y+1)에서 끝나는 직사각형 으로 두면

각 [y, x] 별로 직사각형으로 덮였다 / 안 덮였다를 체크할 수 있고,

안 덮인 칸들만으로 그래프를 이루면 각 영역은 하나의 연결 요소를 이루게 됩니다.

 

+ 원래 [a, b]는 다른 의미를 가지고 있지만 여기서는 특별히 이렇게 쓰겠습니다.

 

연결 요소의 개수는 "[11724] 연결 요소 구하기"에서 구해봤으니, 각 연결 요소의 크기를 구해봅시다.

어떤 연결 요소의 크기는 "그 연결 요소 안에 있는 정점의 수"가 됩니다.

즉, DFS 탐색을 하면서 방문한 정점의 수를 세주면 됩니다.

 

탐색이 끝난 뒤 연결 요소의 크기들을 정렬해야 함에 주의하세요.

const int dy[4] = {-1, 0, 1, 0}, dx[4] = {0, 1, 0, -1};

int n, m, k;
int mp[120][120];

int cnt = 0; bool chk[120][120];
void dfs(int y, int x){
	chk[y][x] = 1; cnt += 1;
	for (int k = 0; k < 4; k++){
		int yy = y+dy[k], xx = x+dx[k];
		if (0 > yy || yy >= n){ continue; }
		if (0 > xx || xx >= m){ continue; }
		if (mp[yy][xx] == 1){ continue; }
		if (chk[yy][xx]){ continue; }
		dfs(yy, xx);
	}
}

void Main(){
	cin >> n >> m >> k;
	while (k--){
		int y1, y2, x1, x2; cin >> x1 >> y1 >> x2 >> y2;
		for (int x = x1; x < x2; x++){
			for (int y = y1; y < y2; y++){ mp[y][x] = 1; }
		}
	}
	vector<int> ans;
	for (int y = 0; y < n; y++){
		for (int x = 0; x < m; x++){
			if (mp[y][x] == 1){ continue; }
			if (chk[y][x]){ continue; }
			cnt = 0; dfs(y, x); ans.push_back(cnt);
		}
	}
	sort(all(ans));
	cout << ans.size() << endl;
	for (int cnt : ans){ cout << cnt << ' '; }
}

8. [7562] 나이트의 이동 (Silver II)

2차원 맵을 그래프로 바꾸는 건 "[2178] 미로 탐색"에서 이미 해봤습니다.

하지만, 이번에는 간선을 나이트의 움직임으로 바꿔야 합니다.

 

나이트의 움직임을 간단히 표현하면, (y±2, x±1) 또는 (y±1, x±2)로 나타낼 수 있습니다.

그러니, 우리가 정의해줬던 dy, dx 배열을 이에 맞게 고치면 됩니다.

/* Knight's Move

 8 1
7   2
  *
6   3
 5 4

*/

const int dy[8] = {-2, -1, 1, 2, 2, 1, -1, -2}, dx[8] = {1, 2, 2, 1, -1, -2, -2, -1};

int dis[320][320];

void Main(){
	int t; cin >> t;
	while (t--){
		memset(dis, -1, sizeof(dis));
		int n; cin >> n;
		pi2 st, ed; cin >> st.fr >> st.sc >> ed.fr >> ed.sc;
		queue<pi3> q; q.push({st, 0}); dis[st.fr][st.sc] = 0;
		while (!q.empty()){
			int y = q.front().fr.fr, x = q.front().fr.sc;
			int dst = q.front().sc; q.pop();
			if (make_pair(y, x) == ed){ cout << dst << endl; break; }
			for (int k = 0; k < 8; k++){
				int yy = y+dy[k], xx = x+dx[k];
				if (0 > yy || yy >= n){ continue; }
				if (0 > xx || xx >= n){ continue; }
				if (dis[yy][xx] != -1){ continue; }
				q.push({ {yy, xx}, dst+1 }); dis[yy][xx] = dst+1;
			}
		}
	}
}

9. [7576] 토마토 (Gold V)

각 토마토별로 익은 토마토와의 최단경로를 찾아주면 됩니다.

이는 익은 토마토에서 출발하는 BFS를 여러 번 돌려서 해결할 수 있지만, 이 문제에서 그렇게 했다가는 TLE가 뜨게 됩니다.

그래서, "익은 토마토들"에서 출발하는 BFS를 한 번에 돌려주면 됩니다.

 

+ 이런 형식의 BFS를 Multisource BFS라고 합니다.

const int dy[4] = {-1, 0, 1, 0}, dx[4] = {0, 1, 0, -1};

int dis[1020][1020];

void Main(){
	queue<pi3> q;
	int n, m; cin >> m >> n;
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= m; j++){
			cin >> dis[i][j];
			if (dis[i][j] == 1){ q.push({ {i, j}, 1 }); }
		}
	}
	while (!q.empty()){
		int y = q.front().fr.fr, x = q.front().fr.sc;
		int dst = q.front().sc; q.pop();
		for (int k = 0; k < 4; k++){
			int yy = y+dy[k], xx = x+dx[k];
			if (1 > yy || yy > n){ continue; }
			if (1 > xx || xx > m){ continue; }
			if (dis[yy][xx] != 0){ continue; }
			q.push({ {yy, xx}, dst+1 }); dis[yy][xx] = dst+1;
		}
	}
	int ans = 1;
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= m; j++){
			if (dis[i][j] == -1){ continue; }
			if (dis[i][j] == 0){ cout << -1; return; }
			ans = max(ans, dis[i][j]);
		}
	}
	cout << ans-1;
}

10. [17129] 윌리암슨수액빨이딱따구리가 정보섬에 올라온 이유 (Gold V)

정신나간 문제처럼 보이지만, 사실 "[2178] 미로 탐색"에서 약간만 더 추가하면 됩니다.

• 시작점이 (1, 1)이 아니라 2의 위치입니다.
• 도착점은 (N, M)이 아니라 3, 4, 5의 위치입니다.

그러니까 그냥 2에서 BFS 돌리고 3, 4, 5 중 가장 가까운 걸 찾으면 됩니다.

const int dy[4] = {-1, 0, 1, 0}, dx[4] = {0, 1, 0, -1};

int mp[3020][3020], dis[3020][3020];

void Main(){
	memset(dis, -1, sizeof(dis));
	queue<pi3> q;
	int n, m; cin >> m >> n;
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= m; j++){
			char ch; cin >> ch; mp[i][j] = ch-'0';
			if (mp[i][j] == 2){ q.push({ {i, j}, 0 }); dis[i][j] = 0; }
		}
	}
	while (!q.empty()){
		int y = q.front().fr.fr, x = q.front().fr.sc;
		int dst = q.front().sc; q.pop();
		if (mp[y][x] >= 3){
			cout << "TAK" << endl << dst; return;
		}
		for (int k = 0; k < 4; k++){
			int yy = y+dy[k], xx = x+dx[k];
			if (1 > yy || yy > n){ continue; }
			if (1 > xx || xx > m){ continue; }
			if (mp[yy][xx] == 1){ continue; }
			if (dis[yy][xx] != -1){ continue; }
			q.push({ {yy, xx}, dst+1 }); dis[yy][xx] = dst+1;
		}
	}
	cout << "NIE";
}

11. [2206] 벽 부수고 이동하기 (Gold IV)

\( (y, x) \)만으로 BFS를 돌리기에는 어려워 보이는 문제입니다.

아무리 생각해봐도 '벽을 부순 횟수'가 저장되어야 할 것 같으니 이를 저장해봅시다.

즉, \( DIS_{y, x, c} := \) \( (1, 1) \Rightarrow (y, x) \)로 \( c \)개의 벽을 부숴서 갈 수 있는 최단경로 라고 정의해봅시다.

 

이제 이러면 문제는 간단해집니다.

최단경로니까 BFS를 써주면 되고, 간선은 인접한 칸들끼리 연결하되 도착점이 벽이라면 \( (y, x, c) \rightarrow (y', x', c+1) \)로 연결해주면 됩니다.

const int dy[4] = {-1, 0, 1, 0}, dx[4] = {0, 1, 0, -1};

int mp[1020][1020], dis[1020][1020][2];

void Main(){
	memset(dis, -1, sizeof(dis));
	queue<pi4> q;
	int n, m; cin >> n >> m;
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= m; j++){
			char ch; cin >> ch; mp[i][j] = ch-'0';
		}
	}
	q.push({ {1, 1}, {0, 1} }); dis[1][1][0] = 1;
	while (!q.empty()){
		int y = q.front().fr.fr, x = q.front().fr.sc;
		int c = q.front().sc.fr, dst = q.front().sc.sc; q.pop();
		if (y==n && x==m){ cout << dst; return; }
		for (int k = 0; k < 4; k++){
			int yy = y+dy[k], xx = x+dx[k];
			if (1 > yy || yy > n){ continue; }
			if (1 > xx || xx > m){ continue; }
			int cc = c + mp[yy][xx];
			if (cc >= 2){ continue; }
			if (dis[yy][xx][cc] != -1){ continue; }
			q.push({ {yy, xx}, {cc, dst+1} }); dis[yy][xx][cc] = dst+1;
		}
	}
	cout << -1;
}

12. [1987] 알파벳 (Gold IV)

(1, 1)에서 시작해서 갈 수 있는 방향을 하나하나 보면서 그 칸에 적힌 알파벳이 지금까지 등장한 적 없으면 가본다 를 백트래킹으로 돌려주면 됩니다.

 

시간복잡도는 \( O(4^26) \)이지만, 커팅이 굉장히 많이 됩니다.

TODO: 풀이가 왜 시간 안에 도는지 보이기

const int dy[4] = {-1, 0, 1, 0}, dx[4] = {0, 1, 0, -1};
int n, m;
char mp[22][22];

int ans = 0; bool chk[30];
void btk(int y, int x, int cnt){
	//cout << "BTK " << y << ' ' << x << ' ' << cnt << endl;
	//cout << "CHK "; for (int i = 0; i < 26; i++){ cout << chk[i] << ' '; } cout << endl << flush;
	ans = max(ans, cnt);
	for (int k = 0; k < 4; k++){
		int yy = y+dy[k], xx = x+dx[k];
		//cout << "NXT " << yy << ' ' << xx << endl;
		if (1 > yy || yy > n){ continue; }
		if (1 > xx || xx > m){ continue; }
		if (chk[ mp[yy][xx]-'A' ]){ continue; }
		chk[ mp[yy][xx]-'A' ] = 1; btk(yy, xx, cnt+1);
		chk[ mp[yy][xx]-'A' ] = 0;
	}
}

void Main(){
	cin >> n >> m;
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= m; j++){ cin >> mp[i][j]; }
	}
	chk[ mp[1][1]-'A' ] = 1; btk(1, 1, 1);
	chk[ mp[1][1]-'A' ] = 0;
	cout << ans;
}

13. [2239] 스도쿠 (Gold IV)

입력 제한이 굉장히 친절합니다.

12095번 문제의 코드를 요약하면 "비어있는 칸에 대해 1부터 9까지 넣어보면서 백트래킹하기"이고,

이 코드로 풀리는 입력만이 들어오니 그렇게 짜주면 됩니다.

const int N = 9;
int mp[12][12], res[12][12];

bool row[12][12], col[12][12], box[12][12];
inline int bxi(int y, int x){ return (y-1)/3*3 + (x-1)/3 + 1; }
void btk(int y, int x){
	if (x > N){ y += 1; x = 1; }
	if (y > N){
		for (int i = 1; i <= N; i++){
			for (int j = 1; j <= N; j++){ cout << res[i][j]; }
			cout << endl;
		}
		exit(0);
	}
	if (mp[y][x] != 0){ return btk(y, x+1); }
	for (int d = 1; d <= 9; d++){
		if (row[y][d]){ continue; }
		if (col[x][d]){ continue; }
		if (box[bxi(y,x)][d]){ continue; }
		row[y][d] = col[x][d] = box[bxi(y,x)][d] = 1; res[y][x] = d; btk(y, x+1);
		row[y][d] = col[x][d] = box[bxi(y,x)][d] = 0; res[y][x] = 0;
	}
}

void Main(){
	for (int i = 1; i <= N; i++){
		for (int j = 1; j <= N; j++){
			char ch; cin >> ch;
			mp[i][j] = ch-'0';
			if (mp[i][j] != 0){ int d = mp[i][j];
				row[i][d] = col[j][d] = box[bxi(i,j)][d] = 1;
				res[i][j] = d;
			}
		}
	}
	btk(1, 1);
}

14. [1759] 암호 만들기 (Gold V)

\( {}_{L}C_{C} \)개의 조합을 아래 주의 사항에 맞춰서 출력하면 됩니다.

아래는 주의할 사항들입니다.

• 정렬된 문자열이어야 합니다. 그러니, 입력받은 문자를 정렬해줘야 합니다.
• 모음은 1개 이상, 자음은 2개 이상입니다. 하지만 모음만 세도 자음은 (전체 - 모음)으로 셀 수 있습니다.
• 모음 판별에서 오타 내지 맙시다. 모음은 'a', 'e', 'i', 'o', 'u'입니다.

int n, m;
char arr[20];

inline int vwl(char ch){
	return ch=='a' || ch=='e' || ch=='i' || ch=='o' || ch=='u';
}

char res[20];
void btk(int idx, int cnt, int vc){
	if (idx > n){ int cc = cnt-vc;
		if (cnt != m){ return; }
		if (vc < 1 || cc < 2){ return; }
		for (int i = 1; i <= m; i++){ cout << res[i]; }
		cout << endl; return;
	}
	cnt += 1; res[cnt] = arr[idx]; btk(idx+1, cnt, vc + vwl(arr[idx]));
	cnt -= 1; btk(idx+1, cnt, vc);
}

void Main(){
	cin >> m >> n;
	for (int i = 1; i <= n; i++){ cin >> arr[i]; }
	sort(arr+1, arr+n+1);
	btk(1, 0, 0);
}

15. [1799] 비숍 (Gold I)

\( (y, x) \) 좌표로 생각하면 대각선을 2개나 생각해야 하고, 이는 복잡합니다.

하지만, 가로/세로를 생각하지 않고 대각선만 생각한다면, 입력받은 좌표를 45도 돌린 뒤 룩을 배치하는 문제로 바꿀 수 있습니다.

 

좌표를 45도 돌리는 방법은 N-Queen에서 사용한 방식처럼 해줄 수 있습니다.

즉, 대각선이 \( y-x = k_1; y+x = k_2 \)임을 이미 알고 있으니, \( (y, x) \rightarrow (k_1, k_2) = (y-x, y+x) \)로 사용해주면 됩니다.

이 때 중간에 들어오는 빈 칸이 생길 수 있는데, 어차피 1이 아니면 못 놓으니 0으로 초기화해주면 됩니다.

int n;
bool mp[22][22];

bool chk[22]; int ans = 0;
void btk(int y, int cnt){
	if (cnt + n-y+1 < ans){ return; }
	ans = max(ans, cnt);
	if (y > n){ return; }
	for (int x = 1; x <= n; x++){
		if (!mp[y][x]){ continue; }
		if (chk[x]){ continue; }
		chk[x] = 1; btk(y+1, cnt+1);
		chk[x] = 0;
	}
	return btk(y+1, cnt);
}

void Main(){
	cin >> n;
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= n; j++){
			cin >> mp[n-i+j][i+j-1];
		}
	}
	n = 2*n - 1;
	btk(1, 0); cout << ans;
}