[백준 / C언어] 2468번: 안전 영역 (BFS로 풀이)

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

2468번: 안전 영역

 

난이도: solved.ac 실버 1

 

알고리즘 분류

---

BFS, DFS (그래프 탐색)

 

접근 방법

---

각 영역의 높이를 입력 받을 때 해당 높이를 따로 기억하여 높이가 1일 때부터 100일 때까지 중 입력 받은 높이일 때만 전체 영역을 BFS로 탐색한다.

모든 경우에서 안전 영역의 개수가 가장 많을 때를 저장해 출력한다.

 

구현

---

높이 배열 arr_h를 만들어, 각 지역의 높이를 입력받을 때 해당 높이의 index 값을 1씩 증가시켜서 입력 받은 높이인 경우에만(arr_h가 0이 아닐 때만) 탐색할 수 있도록 해주었다.

매 높이마다 전 영역의 탐색이 끝나면 memset으로 visited 배열을 초기화해주었다.

그리고 해당 케이스에서 셌던 영역의 개수가 기존의 ans보다 크면 ans의 값을 갱신시켜줬다.

(참고: 이때 물에 잠기지 않는 영역이 있을 수 있으니 ans의 초기값은 1로 두었다.)

 

코드

---

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#define MAX_H 101

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

Queue q[10000];
int front, rear, N;

int map[100][100];
int visited[100][100];
int dy[4] = { 0,1,0,-1 };
int dx[4] = { 1,0,-1,0 };
int arr_h[MAX_H];	// 높이 저장

void BFS(int height, int y, int x);

int main() {
	int ans = 1, cnt, i, j;
	scanf("%d", &N);
	for (i = 0; i < N; i++) {
		for (j = 0; j < N; j++) {
			scanf("%d", &map[i][j]);
			arr_h[map[i][j]]++;
		}
	}

	for (int height = 1; height < MAX_H; height++) {
		if (arr_h[height] != 0) {
			cnt = 0;
			for (i = 0; i < N; i++) {
				for (j = 0; j < N; j++) {
					if (map[i][j] > height && !visited[i][j]) {
						BFS(height, i, j);
						cnt++;
					}
				}
			}
			if (cnt > ans)
				ans = cnt;
			for (i = 0; i < N; i++)
				memset(visited[i], 0, sizeof(int) * N);
		}
	}
	printf("%d", ans);
	return 0;
}

void BFS(int height, int y, int x) {
	front = -1;
	rear = -1;

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