[BaekJoon] 백준 2468번 안전영역

 

[BaekJoon] 백준 2468번 안전영역

 

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

 

 

내코드

 

- bfs, dfs 로 풀수 있는 문젠데 bfs로 문제를 많이 풀어서 이번에는 dfs로 풀어보았다.

- DFS : Stack을 이용, 깊이 우선

function dfs(Node root){
	root.visited = true;
    for each( root 노드에 인접한 모든 노드들에 대해){
    	if(n.visited == false) dfs(n);
    }

- 물에 잠기는 높이가 주어지지 않았기 때문에 높이 = 0 ~ 최대 높이 - 1 까지 전부 돌려봐야 하지 않을까 생각.

- 주어진 입력을 받아서 높이가 가장 높은 영역의 높이를 구해줬다.

- 새로운 array에 물에 잠긴 부분은 1, 물에 잠기지 않은 부분은 0으로 초기화 시켜주었다.

- 바로 윗줄을 물에 잠기는 부분의 높이가 1 이하인 경우부터 물이 잠기는 부분의 높이가 (최대 높이 - 1) 이하인 경우까지 총 최대높이 -2번 반복해주었다.

- dfs는 일반적인 dfs풀이

-주의할점: 아무지역도 물에 잠기지 않는 경우가 존재한다. 따라서 최댓값을 처음에 초기화 해줄때 1로 초기화를 해줘야한다.

 

 

#include <iostream>
#include <string>

using namespace std;

int n;
int num[100] = {0, };
int arr[100][100];
int dfsArr[100][100];
int visited[100][100] = { false, };
int dx[] = { 0, 1, 0, -1 };
int dy[] = { -1, 0, 1, 0 };

void dfs(int a, int b) {
	visited[a][b] = true;
	for (int i = 0; i < 4; i++) {
		int x = a + dx[i];
		int y = b + dy[i];
		if (x < 0 || y < 0 || x >= n || y >= n) continue;
		if (visited[x][y] == false && dfsArr[x][y] == 0) dfs(x, y);
	}

}

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n;
	int max = -1;
	//initialize and find the highest area
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
			max = max < arr[i][j] ? arr[i][j] : max;
		}
	}
	for (int i = 1; i <= max; i++) {
		for (int p = 0; p < n; p++) {
			for (int q = 0; q < n; q++) {
				if (arr[p][q] <= i) dfsArr[p][q] = 1; //물에 잠긴부분
				else dfsArr[p][q] = 0; //물에 잠기지 않은 부분
				visited[p][q] = false;
			}
		}
		for (int p = 0; p < n; p++) {
			for (int q = 0; q < n; q++) {
				if (visited[p][q] || dfsArr[p][q] == 1) continue;
				dfs(p, q);
				num[i]++;
			}
		}
	}
	
	int maxArea = 1;
	for (int i = 1; i < max; i++) {
		maxArea = maxArea < num[i] ? num[i] : maxArea;
	}
	cout << maxArea;
	return 0;
}

 

참고