인프런 커뮤니티 질문&답변

안녕하세요 준석님ㅎㅎ

이부분이 좀 꼬인 것 같습니다.

void dfs(int y, int x){
	horse.push_back(a[y][x]);
	
	
	for(int i=0;i<4;i++){
		int ny = y + dy[i];
		int nx = x + dx[i];
		if(ny<0 || ny>=R || nx<0 || nx>=C || visited[ny][nx]) continue;
		if(find(horse.begin(), horse.end(), a[ny][nx]) == horse.end()){
			visited[ny][nx] = true;
			dfs(ny,nx);
			// 원복 
			visited[ny][nx] = false;
			horse.pop_back();

방문처리 -> push -> 방문처리해제 -> pop_back 이렇게 되어야 하는데 지금 보시면 horse.push_back(a[y][x]);를 할 때는 visited 처리가 처음에 안되는 것을 볼 수 있죠? (물론 ny, nx 까지 가면 하지만요)

이러한 부분을 맞춰주셔야 합니다.

제가 다듬어봤는데요 ㅎㅎ 참고부탁드립니다.

#include<bits/stdc++.h>
using namespace std;

int R, C, mx, dy[4]={-1,1,0,0}, dx[4]={0,0,-1,1};
string s;
char a[24][24];
bool visited[24][24];
vector<char> horse;
void dfs(int y, int x){
    int hSize = horse.size();
    mx = max(mx, hSize); 
	for(int i=0;i<4;i++){
		int ny = y + dy[i];
		int nx = x + dx[i];
		if(ny<0 || ny>=R || nx<0 || nx>=C || visited[ny][nx]) continue;
                char c = a[ny][nx];
		if(find(horse.begin(), horse.end(), a[ny][nx]) == horse.end()){
			visited[ny][nx] = true;
			horse.push_back(c);
			dfs(ny,nx); 
			visited[ny][nx] = false;
			horse.pop_back();
		} 
	}
	return;
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);	cout.tie(NULL);
	
	cin >> R >> C;
	for(int i=0;i<R;i++){
		cin >> s;
		for(int j=0;j<C;j++){
			a[i][j] = s[j];
		}
	}
        visited[0][0] = true;
        horse.push_back(a[0][0]);
	dfs(0,0);
	cout << mx;
	
	
	return 0;
}

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제게 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.

 원복에 대해 덜 개념이 잡혀있던 것 같습니다 감사합니다 :)

안녕하세요, 인프런 AI 인턴입니다. 준석님.

문제를 올바르게 풀었다 생각했지만 반례를 찾는 것은 흔히 어렵습니다. 비슷한 문제를 겪었던 다른 분들의 질문과 답변을 참고하는 것이 많은 도움이 될 수 있습니다. 유사한 주제로 이미 다뤄진 질문들을 확인해 보세요.

참고할 수 있는 유사한 질문

1. 3-L 반례 질문 있습니다.

   • 특정 케이스에서 통과하지 못하는 경우에 대해 자세한 설명과 함께, 코드에서 주의해야 할 부분들이 잘 설명되어 있습니다.
     

2. 3-L 예외 케이스

   • 일반적인 예제는 통과하지만 특정 예외 케이스에서 문제를 겪는 상황에 대한 토론입니다.
     

위의 질문들을 통해 코드가 의도대로 작동하지 않는 부분을 파악하고, 특정 예외 케이스에서 어떻게 동작하는지 점검해보세요. 종종 작은 실수나 조건의 미스가 문제가 될 수 있습니다.

저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.