[백준 / C언어] 1926번: 그림 (DFS로 구현)

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

1926번: 그림

 

난이도: solved.ac 실버 1

 

 

알고리즘 분류

---

그래프 탐색 (DFS, BFS)

 

 

구현 방법

---

나는 DFS로 풀어보았다

 

입력을 다 받은 뒤에는 2중 for 문으로 1인 위치(그림이 있는 위치)를 찾아주고 그 위치를 초기 기점으로 해서 DFS를 돌렸다

 

DFS 함수로 들어가기 전에 그림의 개수를 파악할 용도로 사용한 int형 변수 print를 1 증가시켜 주었다

 

DFS 함수 내에서는 방문할 때마다 그림의 사이즈를 파악할 용도로 사용한 int형 변수 cnt를 1 증가시켜 주었고

 

DFS 함수가 끝나면 지금까지 최대 사이즈인 max보다 cnt가 더 크면 max 값을 경신시켜 주었다

 

(DFS로 풀었더니 역시 메모리를 많이 잡아먹었다..)

 

 

코드

---

#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, i, j, cnt;

void DFS(int** map, int** visited, int y, int x);

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

	for (i = 0; i < N; i++)
		for (j = 0; j < M; j++)
			scanf("%d", &map[i][j]);

	int max = 0, print = 0;

	for (i = 0; i < N; i++) {
		for (j = 0; j < M; j++) {
			if (map[i][j] && !visited[i][j]) {
				print++;
				cnt = 0;
				DFS(map, visited, i, j);
				if (cnt > max)
					max = cnt;
			}
		}
	}
	printf("%d\n%d\n", print, max);

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

void DFS(int** map, int** visited, int y, int x) {
	visited[y][x] = 1;
	cnt++;
	for (int dir = 0; dir < 4; dir++) {
		int ny = y + dy[dir];
		int nx = x + dx[dir];
		if (ny < 0 || nx < 0 || ny >= N || nx >= M)
			continue;
		else if (map[ny][nx] && !visited[ny][nx])
				DFS(map, visited, ny, nx);
	}
}