[백준 / C언어] 1012번: 유기농 배추

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

1012번: 유기농 배추

 

난이도: solved.ac 실버 2

 

 

알고리즘 분류

---

DFS, BFS

 

 

구현

---

나는 BFS를 이용해 구현하였다

 

입력받은 size만큼의 크기인 map과 visited라는 2차원 배열을 만들었는데, 모두 calloc으로 만들어 모든 원소가 0이 되도록 해주었다

 

map은 배추의 위치를 표시하는 용도, visited는 방문한 배추의 위치를 표시하는 용도로 사용하였다

 

그리고 이중 for문을 이용해 배추의 위치를 찾아 BFS를 돌려주었다

 

BFS에서는 큐(Queue)를 사용해야 하는데 큐에 넣을 좌표는 2차원이므로 x, y 좌표가 있는 struct를 만들어서 구조체 배열 동적 할당을 통해 큐를 만들어주었다

 

 

덧붙이는 말

---

아무래도 input이 000100100... 처럼 배추의 위치가 한눈에 보이도록 되어 있지 않고

 

위치 좌표만 주어지기 때문에 예제 입력 2를 직접 확인해보는데 약간 번거로웠다

 

나처럼 또 직접 표를 그려서 확인하는 수고를 덜어주기 위해 map에 표시되는 모습을 나타내보았다 (생색...ㅋ)

코드

---

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>

int dy[4] = { 0,1,0,-1 };
int dx[4] = { 1,0,-1,0 };
int N, M, K;
void BFS(int** map, int** visited, int i, int j);

typedef struct _Queue {
	int y;
	int x;
} Queue;

int main() {
	int T, cnt, i, j;	// cnt: 지렁이의 마리 수
	scanf("%d", &T);

	while (T) {
		scanf("%d %d %d", &M, &N, &K);
		int** map = (int**)calloc(N + 1, sizeof(int*));
		int** visited = (int**)calloc(N + 1, sizeof(int*));
		for (i = 0; i < N; i++) {
			map[i] = (int*)calloc(M + 1, sizeof(int*));
			visited[i] = (int*)calloc(M + 1, sizeof(int*));
		}

		int Y, X;
		for (i = 0; i < K; i++) {
			scanf("%d %d", &X, &Y);
			map[Y][X] = 1;
		}
		cnt = 0;
		for (i = 0; i < N; i++) {
			for (j = 0; j < M; j++) {
				if (map[i][j] && !visited[i][j]) {
					BFS(map, visited, i, j);
					cnt++;
				}
			}
		}

		printf("%d\n", cnt);

		for (i = 0; i < N; i++) {
			free(map[i]);
			free(visited[i]);
		}
		free(map);
		free(visited);
		T--;
	}
	return 0;
}

void BFS(int** map, int** visited, int i, int j) {
	Queue* q = (Queue*)calloc(K, sizeof(Queue));
	q[0].y = i, q[0].x = j;

	int front = -1, rear = 0;
	int dir, ny, nx;

	while (front < rear) {
		front++;
		for (dir = 0; dir < 4; dir++) {
			ny = q[front].y + dy[dir];
			nx = q[front].x + dx[dir];
			if (ny < 0 || nx < 0 || ny >= N || nx >= M)
				continue;
			if (map[ny][nx] && !visited[ny][nx]) {
				rear++;
				q[rear].y = ny;
				q[rear].x = nx;
				visited[ny][nx] = 1;
			}
		}
	}
	free(q);
}