백준 16234, 연결된 요소를 탐색하는 완전탐색(DFS)

https://www.acmicpc.net/problem/16234

16234번: 인구 이동

해당 문제는 모든 지점에 대해 DFS 탐색을 진행하고, 연결된 요소에 대해서 값을 재할당한 뒤 다시 visited 배열을 초기화하여 처음부터 다시 탐색을 하는 방법을 사용해야 한다. 따라서 무한루프 내에서 DFS가 진행되며, 특정 조건이 되었을 때 빠져나올 수 있는 Flag가 필요하다.

 

1. 기존 방식대로 DFS를 진행하되, 방문처리 이외에 Sum을 갱신하고, Vector에 해당 위치를 추가하는 작업을 해야 한다.
   • 모든 지점에 대한 DFS 탐색이 끝난 뒤, 연합이 최소 한 개라도 존재한다면 방문배열을 초기화하고 DFS를 처음부터 다시한다.
   • 모든 지점에 대한 DFS 탐색이 끝난 뒤, 연합이 단 한개도 존재하지 않을 경우 Flag를 갱신하여 무한루프를 종료한다.
2. 구하는 값은 연합의 개수가 아닌 맵에 대한 모든 탐색이 끝났을 때, 연합의 유무를 통해 카운팅되기 때문에 출력되는 값 cnt는 이중 for문이 종료되었을 때 증가한다.
3. 값이 올바르지 않을 경우, 중간중간 디버깅(cout을 통한 방문위치(y,x) 혹은 갱신된 인구수(이중 for문 - cout) 출력)을 통해 해결한다.

Key Point

1. 기존 연결요소 DFS 문제와는 다르게 이미 방문했던 지점을 제외한 모든 지점을 방문해야 한다. 따라서 무한 루프인 while(true)를 사용하며, 중간에 빠져나올 수 있는 Flag 설정이 필요하다.
2. DFS가 끝나면 연합인 지역의 인구를 다시 갱신해야 하므로, 해당 지역의 좌표 값을 저장해야 한다. 따라서 pair 형태로 Vector에 저장한다.
3. 연합이 있으려면 최소 두 나라가 인구이동을 해야한다. 따라서 한 칸만 이동했을 경우는 연합이 있다고 계산하면 안된다. 즉, 연합이 있는 경우에만 Flag 값을 갱신한다.

문제 코드

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

int n, L, R, arr[54][54], visited[54][54], cnt, sum;
const int dy[] = {-1, 0, 1, 0};
const int dx[] = {0, 1, 0, -1};

vector<pair<int, int>> v;

void DFS(int y, int x){
	visited[y][x] = 1;
	v.push_back({y,x});
	sum += arr[y][x];

	for(int i = 0; i < 4; i++){
		int ny = y + dy[i];
		int nx = x + dx[i];

		if(nx < 0 || ny < 0 || nx >= n || ny >= n || visited[ny][nx]) continue;
		if(abs(arr[ny][nx] - arr[y][x]) >= L && abs(arr[ny][nx] - arr[y][x]) <= R) 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){
		bool flag = false;
		memset(visited, 0, sizeof(visited));

		for(int i = 0; i < n; i++){
			for(int j = 0; j < n; j++){
				if(!visited[i][j]) {
					sum = 0;
					v.clear();

					DFS(i,j);

					if(v.size() == 1) continue;

					for(pair<int, int> _pair : v) {
						arr[_pair.first][_pair.second] = sum / v.size();
						flag = true; // 연합이 있었다는 표시 
					}
				}
			}
		}
		if(!flag) break;
		cnt++;
	}
	cout << cnt << "\n";

	return 0;
}

• while문이 끝날 때마다(모든 지역에 대한 탐색이 끝났을 때) 방문배열과 Flag를 초기화한다. (완전탐색의 원.복)
• 특정 조건에 따라 방문을 진행하고 방문했을 때는 Sum에 합치고, Vector에 좌표를 저장한다.
  • Vector의 경우, 하나의 연결요소에 대한 탐색이 끝났을 때 초기화가 되어야 한다.
  • sum 또한 마찬가지로 하나의 연결요소에 대한 탐색이 끝났을 때 초기화가 되어야 한다.

 

디버깅을 습관화 하기

필자는 값이 올바르게 출력되지 않아 방문이 진행될 때마다 방문 지점의 좌표인 {y, x}를 출력하도록 하였다. 그 결과, 예상했던 지점을 방문하지 않는 것을 확인할 수 있었고, if문에서 abs()를 쓰지 않았음을 확인할 수 있었다. 또한 모든 지점에 대한 DFS가 끝나고, 모든 나라의 인구수를 출력하였을 때, 값이 0으로 나오는 문제를 발견하였다. sum을 0으로 초기화하는 과정에서 sum = 0이 아닌 int sum = 0으로 하여 새로운 지역변수를 할당하였음을 확인할 수 있었다.

 

이처럼 정확한 값이 나오지 않았을 때, 디버깅(편집기에서 디버깅 기능을 활용할 수 있으나 실제 코딩테스트 환경에 대비하기 위해 일일이 출력하여 결과를 확인)을 통해 문제를 해결하는 습관을 기르는 것이 코딩테스트 실력 향상에도 많은 도움이 되는 것 같다. 덕분에 해당 문제 및 DFS 탐색에 대한 이해도도 올라갔다.

 

 

https://www.inflearn.com/course/10%EC%A3%BC%EC%99%84%EC%84%B1-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%ED%81%B0%EB%8F%8C/dashboard

10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트 - 인프런 | 강의