BOJ(C++) / 백준 2468 : 안전 영역

백준 2468 : 안전 영역

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

2468번: 안전 영역

 

코드

//c++스터디 1주차(BFS/DFS) 2468 안전 영역
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <cstring>

using namespace std;

int N = 0;
int board[101][101] = { 0, };
int visited[101][101] = { 0, };
int next_i[4] = { 1,0,-1,0 }, next_j[4] = { 0,1,0,-1 };
int depth = 0;

void DFS(int c_i, int c_j) {
	visited[c_i][c_j] = 1;
	
	for (int k = 0; k < 4; k++) {
		int n_i = next_i[k] + c_i;
		int n_j = next_j[k] + c_j;

		//지역 벗어남
		if (n_i < 0 || n_j < 0 || n_i >= N || n_j >= N)
			continue; 
		if (visited[n_i][n_j] == 0 && board[n_i][n_j] > depth)
			DFS(n_i, n_j);

	}
}

int main() {
	//입출력 속도 향상
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> N;

	map<int, int> m;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			cin >> board[i][j];
			m[board[i][j]] = 1;
		}
	}

	int answer = 1; //아무 지역도 물에 잠기지 않을수 있으므로 1로 초기화
	for (auto dep : m) {
		memset(visited, 0, sizeof(visited)); //0으로 초기화, 헤더 cstring 선언
		int area = 0;
		depth = dep.first; //잠기는 높이
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				if (visited[i][j] == 0 && board[i][j] > depth) {
					DFS(i, j);
					area++; //지역 + 
				}
			}
		}
		//모두 물에 잠겼을 때
		if (area == 0)
			break;
		answer = max(answer, area); // 최대 안전 영역
	}

	cout << answer << "\n";

	return 0;
} // 걸린 시간 : 40분

 

설명

DFS(깊이 우선 탐색)를 사용하여 안전한 영역의 구할 수 있다. DFS는 인접해있는 지역들을 한 번에 방문할 수 있으므로 안전한 영역을 구하였다. 현재 노드에서 다음 노드로 넘어갈 때는 board 범위를 벗어나지 않고, 전에 방문되지 않았고, 높이가 depth보다 큰 지역을 방문한다.

map에 지역들의 높이를 저장한 후 가장 낮은 지역부터 높은 지역까지 차례대로 잠기게 하여 어느 높이 일 때 안전한 영역이 최대인지 구한다. 

아무 지역도 물에 잠기지 않을 가능성이 있다. 그때는 최대 안전 영역이 1개이므로 출력값의 초기값을 1로 설정해주어야 한다. 

결과

 

고찰

걸린 시간 : 40분

기본적인 DFS문제였지만 여러번 실패했다. (나는 보통 BFS보다는 DFS가 더 편하기 때문에 DFS를 더 자주 사용한다.)

아무 지역도 물에 잠기지 않을 가능성이 있다. 이 부분을 생각하지 못하여서 틀리게 되었다. 다시 한번 조건을 파악하고 오류를 줄여나가야 한다. 또한 조건, 작은 부분들을 놓치지 않고 풀어서 테스트 케이스가 없는 경우를 다 맞을 수 있도록 해야 할 거 같다. 

memset을 사용할 때는 #include <cstring> 헤더를 선언해주어야 한다. 항상 이걸 까먹어서 컴파일에러가 난다... 이런 오류를 더 줄여보도록 해야겠다. 

 

 

난이도

Silver 1