[ALPS Study] DFS(깊이 우선 탐색) - 유기농배추(BOJ 1012)

자 이번엔 바로 풀지 않고 어떻게 풀어야 할 지 생각해보고 풀어야겠다.

사실 난 알고리즘 풀 때 앞 뒤 안가리고 무작정 코드짜는 버릇이 있는데 안 좋은..버릇이다..

 

우선은 테스트 케이스 값을 입력받고 입력받은만큼 함수를 반복해 줄 것이다. 

int main() {
	int T;
	int i;
	scanf("%d", &T);
	
	for (i = 0; i < T; i++) {
		func();
	}
}

대충 뭐 이런식으로!

그런 다음에 이제 모든! 처리는 func() 이라는 함수에서 처리하게 될 것이다.

 

우선 M, N, K를 입력받아야겠지? 그리고 map정보를 저장할 map[50][50]이라는 배열도 선언해야 할 것이다.

그런 다음에 이제 K번만큼 for문을 돌려서 배추의 위치를 map에 저장할 것이다.

void func() {
	int M, N, K;
	int i, tmpx, tmpy;
	int map[50][50] = { 0, };
	scanf("%d %d %d", &N, &M, &K);
	for (i = 0; i < K; i++) {
		scanf("%d %d", &tmpx, &tmpy);
		map[tmpx][tmpy] = 1;
	}
	

}

이로써 이제 맵에 정보를 저장하는 건 끝이 났다. 이제 문제의 핵심포인트. 뭉쳐있는 배추의 무리의 개수를 세야 한다. 

어떻게 구현할 지 생각해봤는데, 먼저 가로로 한 칸씩 이동한다. 예를 들어보자.

 

1 1 0 

1 0 0

0 0 0

 

이 경우를 보자. 먼저 첫 번째 칸에 1이 나왔다. 그러면 가로로 한 칸 이동한다. 또 1이다. 또 한 칸 이동한다. 이번엔 0이 나왔다. 그러면 다시 두 번째 줄로 돌아와서 아래를 검사한다. 0이다. 그러면 다시 첫 번째 줄로 돌아온다. 아래를 검사한다. 1이다. 그렇다면 다시 가로로 한 칸 이동해서 검사한다. 0이다. 그러면 아래를 검사한다. 0이다. 옆과 아래 둘 다 0이 나왔으므로 count를 1 증가시키고 한 사이클이 끝난다. 

 

저 알고리즘은 dfs를 이용해서 짜게 될 것 같다.

 

(0,0) --> (0,1) --> (0,2) 

(0,0) --> (0,1)

(0,0) --> (0,1) --> (1,1)

(0,0) --> (0,1)

(0,0)

 

(0,0) --> (1,0) --> (1,1)

(0,0) --> (1,0) 

(0,0) --> (1,0) --> (2,0) 

(0,0) --> (1,0)

(0,0) 

 

이걸 누가 알아볼까 싶기는 한데.... 저런식으로 쭉 가다 막히면 돌아오고 쭉 가다 막히면 돌아오고 그런식으로?

 

 

문제는 이제 하나만 검사할 게 아니라는 거지. 만약

 

1 1 0 0 1 1

1 0 0 0 0 1

0 0 0 0 0 0

 

이 경우라면.. 첫 번째 배추 무리를 검사한 이후에 어떻게 해야 할까?

첫 번째 알고리즘을 마치고 나면 (0,0)으로 돌아와 있을 것이다. 그렇다면 다음 검사 시작 지점은..? 내가 생각해봤는데 (0,0+i)에서 map(0,0+i)가 0이 나오면 int ok 값을 1로 바꿔주고 다시 1이 나오면 ok값을 0으로 바꾸고 나서 저 행동을 반복하면 되지 않을까..? 

 

아 아니면 저렇게 탐색을 완료한 지점들의 값을 0이나 2로 바꿔준 다음, 그냥 한 점 한 점 전부 검사해가며 1이 나오면 저 알고리즘을 다시 반복하면 될 것 같다.

 

자 이제 뇌피셜로 풀었으니 실제 코딩을 하러 가보도록 하자.

 

---

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h> 

int map[50][50] = { 0, };
int M, N, K;
int cnt = 0;
int end = 0; int baechu = 0;

void func();
void dfs(int x, int y);
void printmap();
int main() {
	int T;
	int i;
	scanf("%d", &T);
	
	for (i = 0; i < T; i++) {
		func();
	}
}

void func() {
	int i, tmpx, tmpy;
	cnt = 0; end = 0; baechu = 0;
	scanf("%d %d %d", &N, &M, &K);
	for (i = 0; i < K; i++) {
		scanf("%d %d", &tmpx, &tmpy);
		map[tmpx][tmpy] = 1;
	}
	dfs(0, 0);
	printf("\n%d\n", cnt);
}

void dfs(int x, int y) {
	printf("dfs(%d, %d)\n", x, y);
	printmap();	printf("\n");
	printf("cnt = %d", cnt);	printf("\n");

	if (x == N - 1 && y == N - 1) {
		end = 1;
		return;
	}

	while (!end) {
		if (map[x][y] == 0) {
			if (baechu == 0) {
				if (x == N - 1)
					dfs(0, y + 1);
				else
					dfs(x + 1, y);
			}
			if (baechu == 1) {
				return;
			}
		}

		if (map[x][y] == 1 && baechu == 0) {
			baechu = 1;	cnt++;
			if (x != N - 1)
				dfs(x + 1, y);
			dfs(x, y + 1);
			map[x][y] = 0;
			baechu = 0;
		}

		if (map[x][y] == 1 && baechu == 1) {
			if (x != N - 1)
				dfs(x + 1, y);
			dfs(x, y + 1);
			map[x][y] = 0;
		}
	}
}

void printmap() {
	int i, j;
	for (i = 0; i < M; i++) {
		for (j = 0; j < N; j++) {
			printf("%d ", map[j][i]);
		}
		printf("\n");
	}
}

와 내가 이걸 풀었어 대박 감격적이야 우와 물론 백준처럼 한 번에 입력받고 답내는게 아니라 모든 케이스가 잘 돌아가는지 아직 확인은 못해봤지만 적어도 테스트케이스 샘플은 잘 돌아간다ㅠㅠㅠㅠㅠ내일 마저 고치고 설명 써야겠군! ! 행복하다!