[백준 알고리즘] 1012번 - 유기농 배추 (DFS 알고리즘)

1. 문제 및 예시 실행결과

 

 이 글의 소제목이 DFS 알고리즘이지만, 나는 DFS알고리즘을 모르는 상태이다...... 그냥 내가 생각한 방식대로 풀었더니 그것이 DFS 알고리즘이었던 것이다. 다른점이 있다면 나는 자료구조를 queue를 사용하였지만 DFS 알고리즘은 stack을 사용한다고 한다. 이 글은 DFS알고리즘의 설명보다는 1012번을 푸는 방법에 대한 글이라고 생각해줬으면 좋겠다.

 

출처: www.acmicpc.net/problem/1012

1012번: 유기농 배추

---

---

 중요한 점은 이놈의 지렁이는 대각선으로는 이동하지 못하고 영옆과 상하만을 이동할 수 있다는 것이다. 이 부분만 고려해서 주변의 배추들을 하나씩 제거해가면 풀 수 있다.

---

---

2. 풀이과정

 

 앞서 말했듯이 다음과 같이 queue를 사용하면 편하게 풀 수 있다.

---

---

 풀이 과정은 간단하다. 전체적으로 탐색을 진행하다가 1을 만나면 그때부터 알고리즘이 시작된다. 먼저 가장먼저 만난 1의 좌표를 Queue에 push해준다. 그 후 Queue의 front를 조회한 후 그 자리를 0으로 만들어준다. 이유는 나중에 설명하겠다. 0으로 만들어 준 후 상하좌우에 1이 존재한다면 이를 큐에 삽입하고 이 순서를 그대로 반복하면 된다.

 

 그림으로 설명해보면 위의 그림을 기준으로 1을 가장 처음 만나는 곳은 (0,  0) 이다. 이를 큐에 넣어주고 다시 뺀 후 0으로 만들고 상하좌우에 1이 없는지를 찾아보면, (0 , 1)에 1이 존재하는 것을 확인할 수 있다. 이를 0으로 만들고 다시 큐에 넣어주면 다음과 같은 상태가 된다.

---

---

 해야할 일은 위의 과정을 반복하는 것이다. ( 0 , 1 )을 0으로 만들고 다시 Queue에서 뽑아와, 상하좌우에 1이 없는지를 찾아본다. 확인해보니 바로 밑인 ( 1, 1 )이 1인것을 알 수 있다. 그럼 이를 다시 0으로 만들어주고 큐에 넣어준다. 다음과 같은 상태가 될 것이다.

---

---

 자 그럼 ( 1 , 1 )을 뽑아와서 상하좌우를 확인해보면 전부 0인것을 알 수 있다. 그럼 그대로 count를 1 증가시키고 알고리즘을 종료시키면 된다. 정리하면 다음과 같을 것이다.

---

• 상하좌우의 전쳍탐색을 진행
• 1을 만나면 값을 0으로 바꾼 후 상하좌우에 1이 없는지 탐색
• 1이 있다면 그 값을 0으로 먼저 바꾼 후 위치를 큐에 삽입
• 큐에 있는 값 하나를 뽑아온 후 상하좌우를 검색
• 2 - 3번 방법을 반복

---

 0으로 먼저 값을 바꾼다음 큐에 삽입을 하는 이유를 설명해보겠다. "큐에서 뽑은 후 0으로 바꿔도 괜찮지 않을까?" 라는 생각이 드는 것은 당연하다. 하지만 다음과 같은 경우를 생각해보자. 

---

---

 위의 그림을보면 ( 4 , 1 )의 위치에 1이 존재한다. 여기서부터 탐색을 시작하면 왼쪽과 아래의 1이 있으니 다음과 같이 큐에 들어가게 된다. 

---

---

 큐에 집어 넣어도 1인 상태이다. 자 그럼 앞에 있는 (5 , 1)을 뽑아서 탐색을 진행해보자. 뽑자마자 0으로 값을 바꿔주고 상하좌우를 탐색하여 큐에 넣어주면 다음과 같이 큐에 들어가게 된다.

---

---

 좌, 하에 있는 (6 , 1)과 (5, 2)가 Queue에 삽입되었다. 그리고 이들의 값은 아직 1이다. 자 그럼 계속 진행해보자. (4, 2)를 꺼내 상하좌우를 검색해보니 왼쪽과 아래쪽에 1이 있으니 삽입해준다. 다음과 같은 그림이 될 것이다.

 

* 지금까지의 설명에서 좌표가 행과 열이 바뀌었습니다. 정말 죄송합니다 ㅠㅠ 이휴에는 정상적인 좌표로 설명하였습니다...

---

---

 이렇게 보면 같은 좌표인 ( 2 , 5 ) 가 두개가 들어있다는 것을 알 수 있다. 만약 상하좌우가 전부 1이라면? 값들이 더 겹쳐 메모리 초과가 발생할 수 있다. (필자가 직접 겪었다...) 따라서 이를 방지하기 위해서는 먼저 값을 0으로 만들어야 한다. 

 

3. 소스코드

 

 다음은 내가 작성한 소스코드이다.

 

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>

#define SIZE 50

using namespace std;

typedef struct Point {
	int row;
	int col;
} Point;

bool checkRange(int row, int col) {
	if ((row > -1 && row < 50) && (col > -1 && col < 50))
		return true;
	else
		return false;
}

void checkField(int field[SIZE][SIZE], int row, int col) {
	queue<Point> locate;
	//stack<Point> locate;
	Point loc;
	loc.row = row;
	loc.col = col;
	locate.push(loc);
	field[row][col] = false;

	while (!locate.empty()) {

		Point current = locate.front();
		locate.pop();

		if (checkRange(current.row - 1, current.col) == true && field[current.row - 1][current.col] == 1) {
			Point buff;
			buff.row = current.row - 1;
			buff.col = current.col;
			field[current.row - 1][current.col] = 0;
			locate.push(buff);
		}

		if (checkRange(current.row + 1, current.col) == true && field[current.row + 1][current.col] == 1) {
			Point buff;
			buff.row = current.row + 1;
			buff.col = current.col;
			field[current.row + 1][current.col] = 0;
			locate.push(buff);
		}

		if (checkRange(current.row, current.col + 1) == true && field[current.row][current.col + 1] == 1) {
			Point buff;
			buff.row = current.row;
			buff.col = current.col + 1;
			field[current.row][current.col + 1] = 0;
			locate.push(buff);
		}

		if (checkRange(current.row , current.col - 1) == true && field[current.row][current.col - 1] == 1) {
			Point buff;
			buff.row = current.row;
			buff.col = current.col - 1;
			field[current.row][current.col - 1] = 0;
			locate.push(buff);
		}
	}
}

void printArr(int arr[SIZE][SIZE], int row, int col) {
	
	cout << endl;

	for (int i = 0; i < row; i++) {
		for (int j = 0; j < col; j++) {
			//cout << dec << arr[i][j] << " ";
			printf("%d ", arr[i][j]);
		}
		cout << endl;
	}

	cout << endl;
}

int main(void) {
	int T;
	int field[SIZE][SIZE];
	

	cin >> T;

	for (int i = 0; i < T; i++) {
		int row, col, num;
		int count = 0;
		cin >> row >> col >> num;

		for (int j = 0; j < row; j++) {
			for (int k = 0; k < col; k++)
				field[j][k] = -1;
		}

		for (int j = 0; j < num; j++) {
			int buffRow, buffCol;
			cin >> buffRow >> buffCol;
			field[buffRow][buffCol] = 1;
		}

		//printArr(field, row, col);

		for (int j = 0; j < row; j++) {
			for (int k = 0; k < col; k++) {
				if (field[j][k] == 1) {
					checkField(field, j, k);
					count++;
					//printArr(field, row, col);
				}
			}

		}

		cout << count << endl;

	}

	return 0;
}