C++ [Algorithm] - 백준 1012 유기농 배추

문제

 

간단하게 설명하자면 상하좌우 네 방향에 다른 배추가 위치한 경우 서로 인접하다. 즉 1덩어리로 본다.

위 그림을 보면 총 5덩어리다.

 

코드

#include <iostream>
#include <cstring>

using namespace std;

int testCase, M, N, K;
int x, y;
int answer = 0;
int dx[4] = { -1, 0, 1, 0 };
int dy[4] = { 0, 1, 0 ,-1 };
bool visited[50][50];
int map[50][50];

void dfs(int x, int y) {
	visited[x][y] = true;

	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx >= 0 && ny >= 0 && nx < M && ny < N) {
			if (map[nx][ny] == 1 && !visited[nx][ny]) {
				dfs(nx, ny);
			}
		}
	}
}


int main() {
	cin >> testCase;

	for (int i = 0; i < testCase; i++) {
		cin >> M >> N >> K;
		answer = 0;

		memset(map, 0, sizeof(map));
		memset(visited, false, sizeof(visited));

		for (int i = 0; i < K; i++) {
			cin >> x >> y;
			map[x][y] = 1;
		}

		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] == 1 && !visited[i][j]) {
					dfs(i, j);
					answer++;
				}
			}
		}
		cout << answer << endl;
	}
}

 

설명

우선 main 함수 안의 이중 반복문을 살펴보자

		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] == 1 && !visited[i][j]) {
					dfs(i, j);
					answer++;
				}
			}
		}

현재 좌표 위치 값이 1 이거나 방문하지 않았을 경우 dfs를 진행한다.

 

void dfs(int x, int y) {
	visited[x][y] = true;

	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx >= 0 && ny >= 0 && nx < M && ny < N) {
			if (map[nx][ny] == 1 && !visited[nx][ny]) {
				dfs(nx, ny);
			}
		}
	}
}

 

dfs로 진입시 현재 좌표를 방문했다 true로 남겨놓고

상, 우, 하, 좌 순서대로 탐색을 한다. 탐색 방법은 현재 위치에서 미리 이동값들을 더해준다.

움직일 곳이 범위 안에 있는지 확인 후, 움직일 곳의 좌표 위치 값이 1이거나, 방문하지 않았을 경우 다시 dfs 탐색

 

 

그림으로 이해해보자

1. 우선 [0,0]부터 탐색이므로 [0,0]의 위치 값이 1이고 방문하지 않았기에 [0,0]을 방문한다.

2. dfs 함수를 통해 "상"으로 이동할 시 범위에 벗어나므로 "우"로 이동한다.

3. "우"로 이동 [0,1]이 지도 범위 안에 있고, 좌표 위치 값이 1이고, 방문하지 않았기에 [0,1]에 대해 dfs 실시

 

 

4. [0,1]도 위와 같은 방법으로 수행

5. 여기선 상, 우 이동이 안되므로 하로 이동한다.

 

 

6. 최종적으로 [1,1]까지 이동 후 더 이상 이동할 곳이 없으므로 dfs 재귀 함수를 종료한다.

 

 

7. 그러면 visited 배열은 [0,0], [0,1], [1,1]에만 true가 설정이 되어 있을 것이다.

		for (int i = 0; i < M; i++) {
			for (int j = 0; j < N; j++) {
				if (map[i][j] == 1 && !visited[i][j]) {
					dfs(i, j);
					answer++;
				}
			}
		}

 

8. 다시 main의 이중반복문을 들어가 [0,1] 좌표 위치 값이 1이기 때문에 dfs를 수행해야 하지만 visited가 true이기 때문에 넘어간다.

 

9. 이중 반복문을 계속 돌리다보면 동그라미 친 부분에 걸리게 되고 여기서 dfs가 실행된다.

 

10. 위와 같은 방법을 반복하다 보면 좌표 위치 값이 1이고, 방문하지 않았던 위치들을 방문할 것이다.

 

11. 총 5개로 끝!

 

발그림 지송

 

 

알고리즘 문제들은 java로 많이 풀어봤지만 c++로 언어를 변경하면서 알고리즘을 다시 시작하니 어렵게 느껴진다,,