[1012] 유기농 배추

순수 BFS DFS 문제로 그래프 연결요소 세는 문제라고 생각한다!

코딩테스트 사이트 만들때 예시로 항상 들고 오던 문제였는데 이제푸네

 

틀렸습니다 두번 나온게 초기화 안해줘서 그런거였다.

암튼 오늘 문제푸는 꼬라지 봤을때 발닦고 잠이나 자러가는게 낫다 알고리즘은 잘짜는데 자꾸 이상한데서 실수한다...

 

#pragma warning(disable:4996)
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>

using namespace std;

int a[101][101];
bool is_visited[101][101];

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

void dfs(int y, int x) {

	is_visited[y][x] = true;

	for (int i = 0; i < 4; i++) {
		int ny = y + dy[i];
		int nx = x + dx[i];
		if (0 <= ny && ny < n && 0 <= nx && nx < m) {
			if (a[ny][nx] == 1 && !is_visited[ny][nx]) {
				dfs(ny, nx);
			}
		}
	}
}

void bfs(int y, int x) {	
	queue<pair<int, int>> q;
	q.push(make_pair(y, x));

	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;

		q.pop();

		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];

			if (a[ny][nx] == 1 && !is_visited[ny][nx]) {
            	// bfs는 큐에 넣을 때 방문체크를 해야 중복방문이 일어나지 않습니다 
                is_visited[ny][nx] = true; 
				q.push(make_pair(ny, nx));
			}
		}
	}	
}


int main() {

	int t;
	scanf("%d", &t);
	queue<pair<int, int>> q;

	while (t--) {
		int k, res = 0;
		scanf("%d %d %d", &m, &n, &k);

		for (int i = 0; i < k; i++) {
			int x, y;
			scanf("%d %d", &x, &y);
			a[y][x] = 1;

			q.push(make_pair(y, x));
		}

		while (!q.empty()) {
			int y = q.front().first;
			int x = q.front().second;
			q.pop();

			if (!is_visited[y][x]) {
				dfs(y, x);
                // bfs(y, x);
				res++;
			}
		}

		memset(is_visited, false, sizeof(is_visited));
		memset(a, 0, sizeof(a));

		printf("%d\n", res);
	}

}

 

와중에 질문글중

나도 아까 미로찾다가 다 부숴버리고 싶었는데

^^...