백준 1012

백준 1012 : 유기농 배추

1. 전형적인 dfs 문제

코드

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int t, n, m, k;
int bat[51][51], visited[51][51];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
queue<pair<int, int>> q;

void dfs(int y, int x) {
	visited[y][x]=1;
	for(int i=0; i<4; i++) {
		int ny = y+dy[i];
		int nx = x+dx[i];
		
		if(ny<0 || nx<0 || ny>=n || nx>=m) {
			continue;
		}
		if(bat[ny][nx] && !visited[ny][nx]) {
			dfs(ny, nx);
		}
	}
	
	return;
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin>>t;
	while(t--) {
		for(int i=0; i<51; i++) {
			fill(visited[i], visited[i]+51, 0);
		}
		cin>>m>>n>>k;
		for(int i=0; i<k; i++) {
			int x, y;
			cin>>x>>y;
			bat[y][x]=1;
		}
		
		int ans=0;
		for(int i=0; i<n; i++) {
			for(int j=0; j<m; j++) {
				if(bat[i][j]==1 && !visited[i][j]) {
					ans++;
					dfs(i, j);	
				}
			}
		}
		
		cout<<ans<<'\n';		
	}
	
	
	
	return 0;
}

왜 틀렸지????
-> visited배열과 bat 배열 둘 다 초기화를 해줘야 한다!!!!!!!!

정답 코드

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

int t, n, m, k;
int bat[51][51], visited[51][51];
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
queue<pair<int, int>> q;

void dfs(int y, int x) {
	visited[y][x]=1;
	for(int i=0; i<4; i++) {
		int ny = y+dy[i];
		int nx = x+dx[i];
		
		if(ny<0 || nx<0 || ny>=n || nx>=m) {
			continue;
		}
		if(bat[ny][nx] && !visited[ny][nx]) {
			dfs(ny, nx);
		}
	}
	
	return;
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin>>t;
	while(t--) {
		for(int i=0; i<n; i++) {
			fill(visited[i], visited[i]+m, 0);
			fill(bat[i], bat[i]+m, 0);			
		}
		cin>>m>>n>>k;
		for(int i=0; i<k; i++) {
			int x, y;
			cin>>x>>y;
			bat[y][x]=1;
		}
		
		int ans=0;
		for(int i=0; i<n; i++) {
			for(int j=0; j<m; j++) {
				if(bat[i][j]==1 && !visited[i][j]) {
					ans++;
					dfs(i, j);	
				}
			}
		}
		
		cout<<ans<<'\n';		
	}
	
	
	
	return 0;
}