글 읽기 - 반례 좀 찾아주세요

myju742 6년 전 0

DFS알고리즘으로 풀었는데 9%정도에서 틀렸다고 나옵니다. 예제 입력이나 질문에 있는건 다 넣어 봤는데 모르겠네요

반례 좀 찾아주세요ㅠ

#include "stdio.h"
#include "queue"
#include "algorithm"

using namespace std;

#define MAX_N	100
int n;
char map[MAX_N][MAX_N];
bool visited[MAX_N][MAX_N];

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

bool check(int x, int y) {
	if (0 <= x&&x < n && 0 <= y&&y < n)return true;
	return false;
}

void dfs(int x, int y, char color) {
	visited[x][y] = true;
	for (int i = 0; i < 4; ++i) {
		int nx = x + dx[i], ny = y + dy[i];
		if (check(nx, ny)) {
			if (!visited[nx][ny] && map[nx][ny] == color) {
				dfs(nx, ny, color);
			}
		}
	}
}

int dfsAll() {
	int cnt = 0;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			if (!visited[i][j]) {
				dfs(i, j, map[i][j]);
				++cnt;;
			}
		}
	}
	return cnt;
}



int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) {
		scanf("\n%s", &map[i]);
	}
	int a = dfsAll();
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			visited[i][j] = false;
			if (map[i][j] == 'G')map[i][j] = 'R';
		}
	}
	int b = dfsAll();
	printf("%d %d\n", a, b);
	return 0;
}