백준 1012, DFS 연결된 요소 찾기(+ 테스트 케이스 : 배열 초기화하기)

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

1012번: 유기농 배추

해당 문제는 1로 연결된 연결 요소의 개수를 찾는 문제이다. 따라서 DFS 알고리즘을 통해 탐색한다.

(물론 BFS도 가능하다. 필자는 DFS 재귀 로직을 통해 작성하는 것이 더 간편하다고 생각해서 DFS를 사용하였다.)

Key Point

1. 맵이 주어져 있다. -> 2차원 배열을 통해 맵을 구현하고, ny[] / nx[]를 사용한다.
2. DFS 혹은 BFS를 통해 연결되어 있는 노드들을 방문처리 한다.
3. 맵을 방문하면서 방문되지 않았고, 값이 1인 노드에 대해 탐색을 진행한다. (연결 요소 문제의 핵심부분)

배열을 초기화하는 방법, fill() 과 memeset()

매개변수는 배열(포인터) 이름으로 시작한다.

1. fill(시작 값, 끝 값 + 1, 초기화 값) : fill은 모든 값으로 초기화가 가능하다.
   • 부분 초기화할 시 오류가 발생할 수 있기 때문에 전체 초기화할 때 사용해야 한다.
   • 이차원 배열의 경우 반드시 배열의 인덱스로 작성해야 한다.
   • fill(&a[0][0], &a[0][0] + 51 * 51, 0); 
     • 배열 a의 크기가 51 * 51인 상태이고 모두 0으로 초기화하기 위한 코드이다. 실제 a의 끝 요소는 a[0][0] + 50*50이지만, 전부 초기화 하기 위해서는 각각 +1을 해야 한다.
     • 따라서 두 번째 매개변수에 들어가는 + 값은 배열의 크기와 같다.
2. memset(배열 이름, 초기화 값, 배열의 크기) : memeset은 0 또는 -1 혹은 char형 문자 한 글자로 초기화가 가능하다.
   • 0 또는 -1로 초기화할 때는 fill 보다 속도가 더 빠르다.
   • 2차원 배열의 경우, fill보다 더 간편하게 초기화할 수 있다.

문제 코드

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

int dy[] = {-1,0,1,0};
int dx[] = {0,1,0,-1};
int T, M, N, K, y, x, ny, nx, ret;
int arr[50][50];
int visited[50][50];

void DFS(int y, int x){
	if(visited[y][x]) return;
	
	visited[y][x] = 1;
	
	for(int i = 0; i < 4; i++){
		ny = y + dy[i];
		nx = x + dx[i];
		
		if(ny < 0 || ny >= N || nx < 0 || nx >= M || visited[ny][nx]) continue;
		if(!arr[ny][nx]) continue;
		DFS(ny,nx);
	}
	
	return ;
}

int main(){
	
	cin >> T;
	
	for(int i = 0; i < T; i++){
		cin >> M >> N >> K;
		for(int i = 0; i < K; i++){
			cin >> x >> y;
			arr[y][x] = 1;
		}
		
		for(int i = 0; i < N; i++){
			for(int j = 0; j < M; j++){
				if(arr[i][j] && !visited[i][j]) {
					DFS(i, j);
					ret += 1;
				}
			}
		}
		
		cout << ret << "\n";
		ret = 0;
				
        memset(arr, 0, sizeof(arr));
        memset(visited, 0, sizeof(visited));
	}

	return 0;
}

DFS가 시작되는 조건이 값이 1이며 방문되지 않았을 때라는 것이 연결 요소 문제의 핵심이다.

강의 답안 코드

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

int dy[] = {-1,0,1,0};
int dx[] = {0,1,0,-1};
int m, n, k, y, x, ret, ny, nx, t;
int a[51][51];
bool visited[51][51];
void DFS(int y, int x){
	visited[y][x] = 1;
	for(int i = 0; i < 4; i++){
		ny = y + dy[i];
		nx = x + dx[i];
		if(ny < 0 || ny >= n || nx < 0 || nx >= m) continue;
		if(a[ny][nx] = 1 && !visited[ny][nx]) DFS(ny,nx); // 특정 조건에서만 DFS를 호출하기 때문에 따로 첫 줄에 초기조건을 작성하지 않아도 된다. 
	}
	return ;
}

int main(){
	
	cin >> t;
	
	while(t--){
		fill(&a[0][0], &a[0][0] + 51 * 51, 0);
		fill(&visited[0][0], &visited[0][0] + 51 * 51, 0);
		ret = 0;
		cin >> m >> n >> k;
		for(int i = 0; i < k; i++){
			cin >> x >> y;
			a[y][x] = 1;
		}
		for(int i = 0; i < n; i++){
			for(int j = 0; j < m; j++){
				if(a[i][j] == 1 && !visited[i][j]){
					DFS(i,j);
					ret++;
				}
			}
		}
		cout << ret << "\n";
	}
	return 0;
}

필자의 코드와 강의의 코드 모두 DFS 재귀호출이 특정 조건에서만 일어나고 있다. 따라서 초기 조건을 작성하지 않아도 정상적으로 수행된다. 하지만 만약에 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++ 코딩테스트 | 알고리즘 코딩테스트 - 인프런 | 강의