개요

백준 2468: 안전영역

• 입력
  첫째 줄에는 어떤 지역을 나타내는 2차원 배열의 행과 열의 개수를 나타내는 수 N이 입력된다. N은 2 이상 100 이하의 정수이다. 둘째 줄부터 N개의 각 줄에는 2차원 배열의 첫 번째 행부터 N번째 행까지 순서대로 한 행씩 높이 정보가 입력된다. 각 줄에는 각 행의 첫 번째 열부터 N번째 열까지 N개의 높이 정보를 나타내는 자연수가 빈 칸을 사이에 두고 입력된다. 높이는 1이상 100 이하의 정수이다.

• 출력
  첫째 줄에 장마철에 물에 잠기지 않는 안전한 영역의 최대 개수를 출력한다.

접근 방식

1. 격자칸에서의 dfs방식이 떠올랐다.

2. 높이정보를 hills라는 배열에 저장하였다.

3. 홍수난 물 높이를 0부터 100까지 다 넣어보면서 각 물높이에 잠긴 지역과 안 잠긴 지역에 대한 정보를
   flooded라는 배열에 0과 1 값으로 저장해줬다.

   //잠긴부분 0 아닌부분 1으로 채우기
   void fillFlooded(int floodHeight) {
   	for (int i = 0; i < N; i++) {
   		for (int j = 0; j < N; j++) {
   			//비온 높이보다 언덕 높이가 더 크다면 1로 채우고 나머진 0
   			if (hills[i][j] > floodHeight) Flooded[i][j] = 1;
   			else Flooded[i][j] = 0;
   		}
   	}
   }

4. 저장된 flooded배열에서 dfs함수를 통해 컴퍼넌트 갯수를 구한 후, 최대 컴퍼넌트 갯수를
   출력한다.

   	for (int i = 0; i <= maxHeight; i++) {
   		int component = 0;
   		//flooded배열 채운 후
   		fillFlooded(i);
   		//방문 배열 false로 지정 후
   		fill(&visited[0][0], &visited[100][100],false);
   
   		for (int i = 0; i < N; i++) {
   			for (int j = 0; j < N; j++) {
   				//방문 안했고, 물에 안잠긴 곳이라면 dfs 시작
   				if (!visited[i][j] && Flooded[i][j]) {
   					component++;
   					//dfs시행
   					dfs(i,j);
   				}
   			}
   		}
   		//최대 컴퍼넌트 수 갱신
   		maxComponent = maxComponent > component ? maxComponent : component;
   	}
   	cout << maxComponent;

코드

#include<iostream>
#include<algorithm>

using namespace std;
int N,maxHeight;
int hills[101][101];
int Flooded[101][101];
int visited[101][101];
int dx[4] = { -1,1,0,0 };
int dy[4] = { 0,0,-1,1 };

void input() {
	cin >> N;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> hills[i][j];
			//입력값중 최대 높이 미리 저장. line 55에 사용하기 위함
			maxHeight = maxHeight > hills[i][j] ? maxHeight : hills[i][j];
		}
	}
}

/// <summary>
/// Flooded 배열에서 홍수로 잠긴 부분 0, 안 잠긴 부분 1로 채워주기
/// </summary>
/// <param name="홍수로 잠긴 물의 높이"></param>
void fillFlooded(int floodHeight) {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			//비 온 높이보다 언덕 높이가 더 크다면 1로 채우고 나머진 0
			if (hills[i][j] > floodHeight) Flooded[i][j] = 1;
			else Flooded[i][j] = 0;
		}
	}
}

//flooded의 x,y좌표에서 dfs시행
void dfs(int x,int y) {
	if (visited[x][y]) return;
	visited[x][y] = true;
	for (int i = 0; i < 4; i++) {
		int nextA = x + dx[i];
		int nextB = y + dy[i];
		//범위를 벗어나지 않으며, 물에 안잠긴 곳이면
		if (nextA >= 0 && nextB >= 0 && nextA < N && nextB < N && Flooded[nextA][nextB]) {
			if (!visited[nextA][nextB]) {
				dfs(nextA,nextB);
			}
		}
	}
}

void solution() {
	//최대 컴퍼넌트 수
	int maxComponent = 0;
	//홍수 난 물의 높이 0부터 maxHeight까지 .
	for (int i = 0; i <= maxHeight; i++) {
		int component = 0;
		//flooded배열 채운 후
		fillFlooded(i);
		//방문 배열 false로 지정 후
		fill(&visited[0][0], &visited[100][100],false);

		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				//방문 안했고, 물에 안잠긴 곳이라면 dfs 시작
				if (!visited[i][j] && Flooded[i][j]) {
					component++;
					//dfs시행
					dfs(i,j);
				}
			}
		}
		//최대 컴퍼넌트 수 갱신
		maxComponent = maxComponent > component ? maxComponent : component;
	}
	cout << maxComponent;
}

int main() {
	input();
	solution();
}

문풀후생

이번에도 dfs함수안의 방문여부 체크하는 조건인

if(isvisited[nextA][nextB])

에서

if(isvisited[x][y])

로 표기해서 틀렸었다..

정신차리고 풀자