1012번 유기농 배추

문제 해석

문제는 여러가지 방법으로 풀 수 있습니다.

문제는 간단히 말해 이렇답니다.

그냥 1이 뭉쳐저 있는 곳을 세는 겁니다. 

단, 1은 상하좌우를 통해서 연결되어 집니다. 대각선으로 1은 서로 다른 지역으로 인식하게 되는 겁니다.

위의 예제에서는 1이 뭉쳐져 있는 곳이 총 5부분입니다. 그래서 답이 5가 되는 것입니다.

이런 문제는 조금 흔한 문제라서 딱 보면 그거네~ 하실 거에요.

제약 조건

테스트케이스 T가 주어지고 N과 M은 1이상 50 이하입니다. 배추가 심어져 있는 점은 Y, X로 주어집니다.

최대 50*50이 주어질 수가 있겠군요. 

풀이

이 유기농배추가 있는 지도를 그래프로 생각을 해보도록 하겠습니다. 탐색 방법은 어떤 방향이든 좋습니다. 하지만 상하좌우 네 방향을 전부 탐색해야합니다. 단, 1인 정점만 탐색합니다.

현재 위치를 y,x라고 치고 상하좌우를 탐색합니다. 위쪽 정점은 현재 정점의 y-1, x 아래 정점은 현재 정점의 y+1,x, 왼쪽 정점은 현재 정점의 y, x-1, 오른쪽 정점은 현재 정점의 y, x+1입니다.

하지만 이미 방문되었다면 그 정점은 탐색하지 않습니다.

따라서 dfs가 몇번 호출되었는가가 이 문제의 답이됩니다. 코드를 통해서 살펴보도록 할까요?

#include <cstdio>
#include <string.h>
#define M 51
#define VISITED 0
using namespace std;

int n, m, k;
int map[M][M];

void dfs(int y, int x) {
	
	if ( y<0 || y >= n || x < 0 || x >= m || map[y][x] == VISITED )
		return;

	map[y][x] = VISITED;
	dfs(y + 1, x);	dfs(y, x + 1);
	dfs(y - 1, x);	dfs(y, x - 1);
}

int main() {
	int T;

	scanf("%d",&T);
	for (int t = 0; t < T; t++) {

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

		scanf("%d %d %d", &m, &n, &k);
		for (int i = 0; i < k; i++) {
			int y, x;
			scanf("%d %d", &y, &x);
			map[x][y] = 1;
		}

		int count = 0;
		for (int y = 0; y < n; y++) {
			for (int x = 0; x < m; x++)
				if (map[y][x] == 1) {
					dfs(y, x);
					count++;
				}
		}
	
		printf("%d\n", count);
	}
}

이중 for문을 돌며 1이 등장하면 그 정점부터 dfs를 실행합니다.  dfs는 그 정점이 0이거나 y, x가 범위 밖이면 바로 return 됩니다.

그렇다면 우리는 그냥 0을 방문되었다고 표현하면 더 간단하게 문제를 풀 수 있지 않을까요?

아래 사진처럼 0,0에서 1을 만났다고 치겠습니다. 그렇다면 그 지점 0,0에서 dfs를 수행하면 앞뒤 양옆을 dfs로 순차적으로 돌아 전부 방문됩니다. 그러면 0으로 값이 변하게 되지요. 이 부분이 두번째 사진의 빨간색으로 된 0으로 표현을 했네요.

dfs가 끝났으니 for문을 계속 수행합니다. 하지만 이미 dfs가 돌아 0으로 값이 변했으므로 skip됩니다.

이런 식으로 dfs를 한번 돌게 되면 하나의 덩어리를 구할 수 있습니다. 이 덩어리의 수를 세는 것이 답입니다.

답은 위 코드의 count로 표현됩니다.

시간 복잡도는 N*M이 됩니다. 

이외에도 BFS를 통해서도 문제의 해답을 구할 수도 있습니다. 

마찬가지로 for문 속에서 일일이 루프를 돌면서 아직 방문되지 않는 점이 있으면 bfs를 돌고 count에 1을 더해 주기만 하면 되거든요.

BFS나 DFS나 둘 중 하나만 알아도 이 문제는 풀 수 있습니다.

또 어떤 방법으로 풀 수 있을까요??

배열과 포인터

배열과 포인터는 아주 유사한 성격을 갖고 있습니다. 배열은 뭘까요?

우선 배열에 대해서 알아봅시다. 배열은 같은 자료형이 연속된 공간으로 나열되있는 것을 뜻합니다. 배열에 대해서 조금 더 쉽게 접근하기 위해서 index를 갖는데요. index를 통해 빠르게 배열 원소에 접근하게 됩니다.

int a[5]={5, 3, 1, 2, 4};

이와 같은 배열이 있다면 메모리의 구조는 바로 이렇게 구성될겁니다.

왜 이런식으로 배열이 구성이 될까요??

왜 배열의 원소는 4바이트나 되는 걸까요.

그 이유는 int가 4바이트이기 때문입니다. 따라서 4바이트씩 주소가 증가하고 있는 겁니다.

그렇다면 char형의 배열은 한 원소의 크기가 1바이트이고, long long배열의 한 원소 크기는 8바이트가 되는 겁니다. got it?

사실 a라는 변수는 a[0]의 주소값을 갖고 있습니다. 배열의 시작주소를 가지고 있다는 거지요.

따라서 a는 &a[0]와 같은 값을 나타냅니다. a는 a[0]의 주소를 가리키고 있다는 겁니다. 

a가 주소값을 가지고 있다고??

그렇다면 a가 가지고 있는 주소를 참조한다면 *a로 a가 참조하는 값을 구할 수 있겠네요. 그러면 정말 a[0]의 값을 참조할까요? 

코드로 확인해보세요.

이제부터는 다른 배열의 다른 연산법을 알아보겠습니다. a는 a[0]을 가리키고 있는 포인터라고 했습니다. a[0]은 5의 값을 가지고 있습니다. 

헌데, a가 a[0]를 가리키고 있으니, *a는 a[0]의 값을 나타내게 되는 것이지요.

그렇다면 이렇게 변형해볼까요?

*(a+0) 는 *a와 같은 뜻이 될까요? 아마 그렇겠죠?

그렇다면 *(a+1)은 어떤 값을 나타나게 될까요?? 결론부터 말씀드리면 a[1]의 값을 갖게 됩니다. 어떤 포인터의 +1은 그것이 참조하고 있는 자료형의 크기만큼 주소를 더하라는 의미가 됩니다. 

그렇다면 *(a+i)는 a[i]가 되겠네요!! 와우!!

이제껏 지껄인 말이 확실한지 코드로 확인해보도록 하겠습니다.

#include <stdio.h>

int main() {
	int i;
	int a[5] = { 5,3,1,2,4 };
	
	
	
	printf("a의 주소 &a[0] = %p, a = %p \n", &a[0],a);
	printf("a의 값: %d\n", *a);
	for (i = 0; i < 5; i++)
		printf("\t 주소 %p  a[%d] : %d, *(a+%d) : %d\n",(a+i),i,a[i],i,*(a+i));

}

다음 사진은 결과를 보여줍니다.

제가 설명한 내용이 맞나요??

a의 값은 a[0]의 주소와 같네요!! 주소 값은 역시 4바이트씩 증가합니다. 

아까 포인터 연산 역시 제가 설명한 대로 나오고 있습니다.

포인터로 배열을 참조할 수 있습니다.

방금 전 배열 a를 포인터 ptr로 참조해보도록 하지요.

int *ptr = a;

로 간단하게 a라는 배열을 포인터로 참조할 수 있습니다.

a 역시 배열의 주소를 가지고 있고 ptr 역시 배열 a를 가리키고 있습니다. 그래서 a와 ptr은 같은 곳을 바라보게 되는 거죠.

그러면 ptr 역시 a가 가지는 특성을 그대로 가지고 있을까요?

코드로 확인해봅시다. 컴퓨터는 거짓말을 하지 않으니까

#include <stdio.h>

int main() {
	int i;
	int a[5] = { 5,3,1,2,4 };
	int *ptr = a;
	
	
	
	printf("a의 주소 &a[0] = %p, a = %p \n", &a[0],a);
	printf("a의 값: %d\n", *a);
	
	for (i = 0; i < 5; i++)
		printf("\t 주소 %p  a[%d] : %d, *(a+%d) : %d\n",(a+i),i,a[i],i,*(a+i));

	printf("\n");

	printf("ptr이 가리키는 주소 : %p\n", ptr);
	for (i = 0; i < 5; i++)
		printf("\t 주소 %p  p[%d] : %d, *(p+%d) : %d\n"
			,(ptr+i),i,ptr[i],i,*(ptr+i));
	
	
}

 

정확히 똑같은 성질을 갖고 있다는 것을 알 수 있습니다.

그러면 둘의 차이는 없을까요??

이 둘의 차이는 크기에서 차이가 납니다.

sizeof연산을 한 번 해보도록 하지요.

#include <stdio.h>
int main() {
	int i;
	int a[5] = { 5,3,1,2,4 };
	int *ptr = a;

	printf("a의 사이즈 :%d, ptr의 사이즈 :%d\n", sizeof(a), sizeof(ptr));
}

결과

음.....

a의 사이즈는 20이고, ptr의 사이즈는 4바이트네요.

a는 배열의 크기를 갖고 있습니다.

a는 int형(4바이트) 배열로 5개가 할당되어있으니 20바이트이지요.

하지만 ptr은 단순히 그 배열을 참조해야하기 때문에 주소값만 저장할 수 있는 공간이면 충분합니다. 따라서 4바이트면 충분합니다.

그리고 배열은 상수화가 된다는 것이 특징입니다. 배열의 원소는 변경가능합니다. 하지만 배열 변수를 다른 값으로 변경할 수는 없습니다.

int a[5];

int b[5] = {5, 3, 1, 2, 4} ;

a=b;

a는 b와 크기가 같고 자료형이 같음에도 불구하고 이와 같은 코드는 컴파일 에러를 불러일으키게 되는 겁니다.

a는 a[0]의 주소입니다. b 역시 b[0]의 주소입니다.

주소는 read-only입니다. 즉, 값을 대입할 수가 없습니다 절대로!

위의 코드는 이것과 같은 얘기가 됩니다. 

&a[0] = &b[0] 이라는 거죠.

이제까지 이야기한 내용을 이해하셨다고 한다면 이해가 갈겁니다.

주소는 포인터만이 참조할 수 있는 포인터만의 특성입니다.

그러니까 위의 코드는 이렇게 바뀌어야합니다.

int *a;

int b[5] = {5, 3, 1, 2, 4} ;

a=b; //a=&b[0]과 같음.

배열과 포인터의 관계 이해하셨는지요??

이것으로 배열과 포인터의 관계를 마치겠습니다~~~

BFS(Breadth First Search, 너비우선탐색)

그래프 이론 DFS와 BFS 중 BFS는 그래프를 가까운 정점부터 순서대로 탐색하는 그래프 탐색 알고리즘이랍니다. 그래프에서 탐색 시 아주 많이 사용되는 탐색기법이지요. 우선 다음과 같은 무향그래프가 있다고 가정해보겠습니다. 

우선 그래프 탐색을 하기 전에 조건이 있습니다.

1. 처음 정점 0부터 시작한다고 칩시다.

2. 정점을 방문한 적이 있다면 다시 방문하지 않는다.

3. 방문해야 할 정점이 여러 개일 경우 가장 번호가 낮은 정점부터 방문한다.

BFS로 위 그래프를 탐색하는 과정을 보겠습니다 

1. 0을 방문한다.

2. 0과 가장 가까운 정점을 찾는다 ( 1, 5, 6).

3. 1이 방문되지 않았으므로 1을 방문한다.

4. 5가 방문되지 않았으므로 5를 방문한다.

5. 6이 방문되지 않았으므로 6을 방문한다.

6. 1에서 가장 가까운 정점을 찾는다 (0, 2, 3).

7. 0은 이미 방문했으므로 skip한다.

8. 2는 방문되지 않았으므로 2를 방문한다.

9. 3이 방문되지 않았으므로 3을 방문한다.

10. 5에서 가장 가까운 정점을 찾는다 (0, 6).

11. 0과 6은 방문됐으므로 skip한다.

12. 6과 가장 가까운 정점을 찾는다 (0, 5).

13. 0과 5는 이미 방문됐으므로 skip한다.

14. 2와 가장 가까운 정점을 찾는다 (1, 4). 

15. 1은 이미 방문됐으므로 skip한다.

16. 4는 방문되지 않았으므로 4를 방문한다.

17. 모든 정점을 지나쳤으므로 종료한다.

이제 방문된 점을 차례대로 나열해본다면  0 - 1 - 5 - 6 - 2 - 3 - 4 로 방문이 되는 것을 확인 할 수 있습니다. 코드로 표현하면 어떻게 될까요? 아래 C++ 소스코드로 BFS를 구현해보았습니다.

#include <cstdio>
#include <vector>
#include <queue>
#define V 7
using namespace std;

int g[V][V] = {
	{0,1,0,0,0,1,1},
	{1,0,1,1,0,0,0},
	{0,1,0,0,1,0,0},
	{0,1,0,0,0,0,0},
	{0,0,1,0,0,0,0},
	{1,0,0,0,0,0,1},
	{1,0,0,0,0,1,0}
};

vector
 bfs(int start) {
	vector discovered(V, false);
	queue next;

	vector order;

	visited[start] = true;

	next.push(start);
	while (!next.empty()) {
		int from = next.front();
		next.pop();

		order.push_back(from);

		for (int to = 0; to < V; to++) {
			if (g[from][to] == 1 && !visited[to]) {
				next.push(to);
				visited[to] = true;
			}
		}
	}
	return order;
}
int main() {

	vector bfsOrder = bfs(0);
	for (int i = 0; i < V; i++)
		printf("%d ", bfsOrder[i]);
}

이 후 0은 방문될때 큐에서 꺼내어 집니다. 그 다음에 0에서 가장 가까운 정점 중에 방문되지 않은 정점을 큐에 저장합니다. 이렇게 말입니다.

0을 방문합니다. 0은 큐에서 꺼내어 지고 0과 가장 가까운 정점 1 5 6이 큐에 저장됐습니다. 그 후에는 다시 1을 큐에서 꺼내오고 1과 가장 가까운 정점을 큐에 집어 넣습니다.

단, 방문되지 않은 녀석들로요.

1은 방문이 되어 큐에서 나오고 2와 3이 추가 돼었군요. 역시 과정은 계속 반복됩니다. 다음 5가 방문될 차례입니다. 5를 꺼내고 5와 가장 가까운 정점을 추가합니다.

5와 가장 가까운 정점 0과 6이 있는데, 6은 아직 큐에 존재하니까 방문하지 않은 걸로 간주합니다. 그래서 6을 다시 큐에 집어 넣습니다. 다음 6을 방문합니다. 

6과 가장 가까운 정점 0과 5는 이미 방문된 상태랍니다. 그래서 큐에 집어 넣지 않습니다. 다음 2를 방문합니다. 

2과 가장 가까운 정점은 1, 4로 1은 이미 방문된 상태로 넘어가고 4는 큐에 들어갑니다. 왜냐면 방문될 정점으로 큐에 아직 존재하니까요. 다음 3을 방문합니다.

3과 가장 가까운 정점 1은 이미 방문된 상태라 넘어갑니다. 다음 4를 방문합니다.

4와 가장 가까운 정점 2는 이미 큐에서 나와 방문이 되었습니다. 어느 정점하나 큐에 들어가지 않습니다. 이제 큐에 남아있는 방문될 정점 6과 4는 이미 방문이 되었으므로 큐에서 그냥 빠져나옵니다. 방문되지 않는 다는 뜻입니다. 버립니다.

이로써 큐는 모두 비워졌습니다. 큐가 비워졌으니 더 이상 방문할 정점이 없으니 BFS과정은 끝나게 됩니다. 이로써 BFS가 어떻게 동작하는 지 살펴보았습니다. BFS는 그럼 도대체 언제 사용하게 될까요? 그건 다음에 알아보도록 하겠습니다.