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

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

728x90

백준 2468 : 안전 영역

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

코드

//c++스터디 1주차(BFS/DFS) 2468 안전 영역 #include #include #include #include #include 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 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 << "

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

설명

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

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

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

결과

고찰

걸린 시간 : 40분

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

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

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

난이도

Silver 1

728x90

from http://se-jung-h.tistory.com/185 by ccl(A) rewrite - 2021-10-22 12:27:15