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

안녕하세요 360님 ㅎㅎ

아마 이부분을 모르시다고 하는거 같은데요.

일단 디버깅코드입니다.

#include <bits/stdc++.h>
using namespace std;
int n,l,r,arr[54][54],visited[54][54],sum,cnt;
int dy[]={-1,0,1,0};
int dx[]={0,1,0,-1};
vector<pair<int,int>>v;
void dfs(int y,int x){
	cout << y << " : " << x << "\n";
	visited[y][x] = 1;
	for(int i=0;i<n;i++){
		int ny=y+dy[i];
		int nx=x+dx[i];
		if(ny<0||ny>=n||nx<0||nx>=n)continue;
		if(visited[ny][nx])continue;
		int d = abs(arr[ny][nx]-arr[y][x]);
		// cout<<y<<" "<<x<<'\n';
		// cout<<ny<<" "<<nx<<'\n';
		// cout<<arr[y][x]<<" "<<arr[ny][nx]<<" "<<d<<'\n';
		if(d>=l && d<=r){
			// cout<<"yes"<<'\n';
			if(v.size()==0){
				v.push_back({y,x});
				sum+=arr[y][x];
			}
			v.push_back({ny,nx});
			sum+=arr[ny][nx];
			dfs(ny,nx);
		}
	}
	return;
}
int main(){
	cin>>n>>l>>r;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			cin>>arr[i][j];
		}
	}
	while(true){
		cnt++;
		int flag = 0;
		sum=0;
		for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(visited[i][j]==0){
				dfs(i,j);
				if(v.size()){
					int p = int(sum/v.size());
					for(auto a:v){
						arr[a.first][a.second]=p;
					}
					flag=1;
				}
				v.clear();
			}
		} 
	}


	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			cout << arr[i][j];
		}
		cout << "\n";
	}
	cout << "CLEAR\n"; 
	if(flag==0){
		cout<<cnt;
		exit(0);
	}
	
	fill(&visited[0][0],&visited[0][0]+54*54,0);
	// for(int i=0;i<54;i++){
	// 	for(int j=0;j<54;j++){
	// 		cout<<visited[i][j]<<" ";
	// 	}
	// 	cout<<'\n';
	// }
	}

	return 0;
}

입력을 하면

202020

202015

402015

여기서

202017

202017

403535

왜 이렇게 되냐는 말씀이시죠?

202020

202015

402015

이 부분이 탐색되어야 하는데 말이죠.

dfs가 좀 이상해서 그렇습니다.

		if(d>=l && d<=r){
			// cout<<"yes"<<'\n';
			if(v.size()==0){
				v.push_back({y,x});
				sum+=arr[y][x];
			}
			v.push_back({ny,nx});
			sum+=arr[ny][nx];
			dfs(ny,nx);
		}

앞의 코드는 탐색을 해야할 때 자신의 노드를 추가하고 sum에 해당 부분을 추가하는 코드인데요.

문제는

		if(d>=l && d<=r){
			// cout<<"yes"<<'\n';
			if(v.size()==0){
				v.push_back({y,x});
				sum+=arr[y][x];
			}

이부분입니다. dfs안에 이부분이 있어요.

예를 들어서 1 -> 2로 가면서

2지점에서 어? v.size() == 0이네 하면서 자신을 추가합니다.

		if(d>=l && d<=r){
			// cout<<"yes"<<'\n';
			if(v.size()==0){
				v.push_back({y,x});
				sum+=arr[y][x];
			}

근데 또 이상태에서 1 -> 2로 가면서 2는 ny,nx에 해당하기 때문에 2를 또 추가해버리는 상황이 생겨버리는 것이죠.

			}
			v.push_back({ny,nx});
			sum+=arr[ny][nx];
			dfs(ny,nx);

dfs안에서 v.size() == 0일 때 자신을 추가한다는 로직을 지우고

dfs가 끝난 이후 v.size()가 있을 때 최종적으로 자신을 추가하는 로직으로 만드셔야 합니다.

그렇게 해서 다시한번 해보시겠어요?

감사합니다.

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

제 코드를 보면, 인접해있는 국가들끼리 인구 이동이 가능하다면 dfs 함수를 호출하여 인구 이동을 하도록 설계되어 있습니다. 그리고, dfs 함수에서는 시작 국가에서 인접한 모든 국가들을 방문하면서 인구 이동 가능 여부를 판단하고, 가능하다면 dfs 함수를 인접한 국가로 이동하면서 인구 이동을 진행합니다.

그러나, 제 코드의 경우 입력값이 주어졌을 때, 이에 해당하는 인접행렬을 다시한번 생성하는데 이때 인접행렬의 정의에 따라 중복된 행과 열이 있을 수 있습니다. 따라서, dfs 함수 내에서 인접한 국가를 판단할 때, 올바르게 판단하지 못해 인구이동이 불가능한 국가들이 생길 수 있습니다.

따라서, 인접행렬 생성과 관련하여 중복된 행과 열이 없도록 구현하여 코드를 수정해보시기 바랍니다.

수정된 코드도 여러 테스트 케이스를 실행해 보시면서 인구 이동이 올바르게 이루어지는지 확인해보시길 바랍니다.

고맙습니다.