글 읽기 - 1987 제가 문제를 잘못 이해하고 있는건지

qocn9029 3년 전 0

각 좌표를 인자로 상하좌우 탐색하면서 더이상 진행될 수 없을때 리턴을하고 그외에는 알파벳 개수만큼의 check배열을 둬서

해당 check[알파벳-'A']=false로 초기화 시킨이후 방문할때마다 true값으로 바꾸는식으로 해서 탐색을 진행하였으나 자꾸 오답이 나오네요..

base조건 밑에 각 4개의 좌표를 재귀호출해서 백트레킹이 된다고 생각하고 있는데 제가 문제를 잘못이해하고 있는건가요 아니면 코드 로직이 잘못되었나요

도와주세요 ~~

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <string>
#include <string.h>
#include <sstream>
using namespace std;

struct pa {
	int x;
	int y;
};

char Map[25][25];
bool check[26];
int n, m;
int cnt = 0;
int MaxValue = -1;

void dfs(pa k) {
	int X = k.x;
	int Y = k.y;

	//유효범위 체크
	if (X < 0 || X >= n || Y < 0 || Y >= m)
		return;

	char c = Map[X][Y];//A~Z

	//이미 한번 나온 알파벳일 경우
	if (check[c - 'A'] == true) {
		if (cnt > MaxValue) {
			MaxValue = cnt;
		}
		return;
	}

	check[c - 'A'] = true;
	cnt++;
	
	dfs(pa{ X - 1,Y });
	dfs(pa{ X + 1,Y });
	dfs(pa{ X,Y - 1 });
	dfs(pa{ X,Y + 1 });
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> Map[i][j];
		}
	}
	memset(check, false, sizeof(check));
	dfs(pa{ 0,0 });
	cout << MaxValue << endl;
	return 0;
}

seico75 3년 전 0

cnt 변수가 증가했다가 재귀를 나오면 다시 적절히... 감소해야하는데 그 부분이 없네요.

cnt 를 전역이 아니라 인자로 받는 형태로 하는 것이 좋을 것 같습니다.

다시 보니 check 도 탐색에서 나올 떄 false 로 바꿔줘야 다음 탐색이 가능해지겠네요.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

1987 제가 문제를 잘못 이해하고 있는건지

qocn9029 3년 전 0

seico75 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말