글 읽기 - (문제잘못이해)DFS로 풀어봤는데 맞게 푼거같은데, 반례찾아주실분이 계실까요

gyoo21w 6년 전 0

조건도 다시 확인 했는데 제가 놓친부분이 있는건지 싶네요

문제에서 제시하지 않은 예제 넣어봐도 잘 되는거 같은데 뭐가 문제인지 모르겠어요

예제2

3 6
HFDFFB
AJHGDH
DGAGEH

//18.03.12
//DFS로 풀어봄
#include <iostream>
using namespace std;

int r, c;
char alp_box[21][21];
bool visit[21][21];
int alp[26];
int dir[4][2] = { { 1,0 },{ -1,0 },{ 0,1 },{ 0,-1 } };

bool IsInside(int x, int y) {
	return (x >= 0 && x < r && y >= 0 && y < c);
}

void dfs_alp(int p, int q) {
	int cur_alp = alp_box[p][q];
	alp[cur_alp - 65] = 1;

	for (int i = 0; i < 4; i++) {
		int next_x = p + dir[i][0];
		int next_y = q + dir[i][1];
		int next_alp = alp_box[next_x][next_y];

		if (IsInside(next_x, next_y) && !alp[next_alp-65]) {
			visit[next_x][next_y] = true; //갯수 세는 용도
			dfs_alp(next_x, next_y);
			alp[next_alp - 65] = 0; //돌아오면서 다시 방문하지 않은걸로 바꿔줌
		}
	}
}

int main()
{
	
	cin >> r >> c;
	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++)
			cin >> alp_box[i][j];
	}
	dfs_alp(0,0);
	int num = 0;

	for (int i = 0; i < r; i++) {
		for (int j = 0; j < c; j++) {
			if (visit[i][j]) num++;
		}
	}
	cout << num << endl;
}