문제

입력

입출력 예시

코드

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

int N;
vector<vector<int>> city, visit;

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

void bfs(int x, int y) {
	queue<pair<int, int>> q;
	q.push({x, y});
	visit[x][y] = 1;
	
	while(!q.empty()) {
		int nowx = q.front().first;
		int nowy = q.front().second;
		q.pop();
		
		for(int i = 0; i < 4; i++){
			int nextx = nowx + dx[i];
			int nexty = nowy + dy[i];
			
			if(nextx >= 0 && nextx < N && nexty >= 0 && nexty < N){
				if(city[nextx][nexty] && !visit[nextx][nexty]) {
					q.push({nextx, nexty});
					visit[nextx][nexty] = 1;
				}
			}
		}
	}
}

int bfsAll() {
	int cnt = 0;
	for(int i = 0; i < N; i++){ 
		for(int j = 0; j < N; j++){ 
			if(city[i][j] && !visit[i][j]){
				bfs(i, j);
				cnt++;
			}
		}
	}
	return cnt;
}

int main() {
	cin >> N;
	city = vector<vector<int>> (N, vector<int>(N, 0));
	visit = vector<vector<int>> (N, vector<int>(N, 0));
	for(int i = 0; i < N; i++){
		for(int j = 0; j < N; j++){
			cin >> city[i][j];
		}
	}
	cout<<bfsAll();
	return 0;
}

아주 평범한 bfs로 풀었다. 딱히 고려해야할 것도 없고, 깊이 생각할 필요도 없는 bfs였다.
그러나 짧은 코드를 좋아하는 본인.. 처음에는 dfs로 풀었다. 그랬더니 런타임 에러 발생!!😑

TC 16, 17, 22 런타임 에러 발생

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

int N;
vector<vector<int>> city, visit;

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

void dfs(int x, int y) {
	visit[x][y] = 1;
	
	for(int i = 0; i < 4; i++){
		int nextx = x + dx[i];
		int nexty = y + dy[i];
		
		if(nextx >= 0 && nextx < N && nexty >= 0 && nexty < N){
			if(city[nextx][nexty] && !visit[nextx][nexty]) dfs(nextx, nexty); 
		}
	}
}

int dfsAll() {
	int cnt = 0;
	for(int i = 0; i < N; i++){ 
		for(int j = 0; j < N; j++){ 
			if(city[i][j] && !visit[i][j]){
				dfs(i, j);
				cnt++;
			}
		}
	}
	return cnt;
}

int main() {
	cin >> N;
	city = vector<vector<int>> (N, vector<int>(N, 0));
	visit = vector<vector<int>> (N, vector<int>(N, 0));
	for(int i = 0; i < N; i++){
		for(int j = 0; j < N; j++){
			cin >> city[i][j];
		}
	}
	cout<<dfsAll();
	return 0;
	
}

Q&A를 보니 dfs(재귀)로 푼 사람들이 16, 17, 22번 테스트 케이스에서 통과를 하지 못했다는 글(과 댓글)이 있었고, 그 댓글에 비재귀적으로 푸는 것을 추천한다고 달려있었다. 왜지? 도대체 왜 dfs는 안 됐던건지 원인이 궁금하다🤨