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

안녕하세요 360님 ㅎㅎ

이 dfs가 하는 역할은 해당 영역이 같은지 안같은지만 확인하면 되는거 아닌가요?

void dfs(int y,int x,int n){
	visited[y][x]=1;
	flag =0;
	for(int i=0;i<n;i++){
		int ny= n+dy[i];
		int nx= n+dx[i];
		if(ny<y||ny>=y+n||nx<x||nx>=x+n)continue;
		if(visited[ny][nx])continue;
		//제가 생각했던것은
		//다른값을 마주하였을때 전역변수에 flag가 1이 되고
		//그 flag가 go함수까지 영향을 끼치는것이었습니다
		if(arr[y][x]!=arr[ny][nx]){
			flag = 1;
			return;
		}
		dfs(ny,nx,n);
	}
	return;
}

먼저 이부분은 2중 for문으로 해도 되는데 굳이 dfs로 재귀적으로 구현할 필요는 없습니다.

함수호출은 cost다 라고 꼭 생각하셔야됩니다.

그러나!

however!

nevertheless!

dfs로 구현해야 한다면.

4각영역을 정하고 해당 4각영역안에서 재귀적으로 호출되며 모든 영역들을 탐색해가며 같은 것을 탐색해야 하는 로직이 필요한데요. 그리고 같지 않다면 flag를 1로 바꿔야 하구요.

이렇게 구축을 하시면 됩니다.

#include <bits/stdc++.h>
using namespace std;
 
int dy[]={-1,0,1,0}, dx[]={0,1,0,-1};  
int a[4][4], visited[70][70], flag;
void dfs(int y,int x,int sy, int sx, int ey, int ex){ 
	visited[y][x]=1;
	int s = a[y][x];  
	for(int i=0; i < 4;i++){
		int ny= y + dy[i];
		int nx= x + dx[i];
		if(ny < sy || ny >= ey) continue;
		if(nx < sx || nx >= ex) continue; 
		if(visited[ny][nx])continue; 
		if(s != a[ny][nx]){
			flag = 1;
			return;
		}
		dfs(ny,nx,sy, sx, ey, ex);
	}
	return;
}  
int main(){
	a[1][2] = 1;
	dfs(0, 0, 0, 0, 4, 4); 
	cout << flag << "\n";
	return 0;
}

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

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

감사합니다.

강사 큰돌 올림.