2468번) 안전 영역

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

무려 초등부 문제!!

힌트를 주자면, 모든 영역의 높이가 동일할 경우도 생각해야 하네요.

2018년 4월 10일 - 다듬지 않은 코드 (소요시간 38분) import java.util.Scanner; public class Q2468 { static int[][] map, newMap; static int size; static int result = 1; public static void main(String[] args) { Scanner sc = new Scanner(System.in); size = sc.nextInt(); map = new int[size][size]; int min = 0, max = 0; for (int i = 0 ; i < size; i++) { for (int j = 0; j < size; j++) { int tempHigh = sc.nextInt(); map[i][j] = tempHigh; if (min == 0 && max == 0) { min = tempHigh; max = tempHigh; } else if (min > tempHigh) { min = tempHigh; } else if (max < tempHigh) { max = tempHigh; } } } for (int i = min; i < max; i++) { searchArea(i); } System.out.println(result); } static void searchArea(int rain) { newMap = new int[size][size]; //안잠기는 지역 파악 for (int i = 0 ; i < size; i++) { for (int j = 0 ; j < size; j++) { int height = map[i][j]; if (height > rain) { newMap[i][j] = 1; } } } //안전한 영역 검색 (플러딩) int areaNum = 1; for (int i = 0 ; i < size; i++) { for (int j = 0 ; j < size; j++) { if (newMap[i][j] == 1) { areaNum += 1; checkMap(i, j); } } } areaNum -= 1; if (result < areaNum) { result = areaNum; } } static void checkMap(int y, int x) { newMap[y][x] = 2; //상 if (0 <= y-1 && newMap[y-1][x] == 1) { checkMap(y-1, x); } //하 if (y+1 < size && newMap[y+1][x] == 1) { checkMap(y+1, x); } //좌 if (0 <= x-1 && newMap[y][x-1] == 1) { checkMap(y, x-1); } //우 if (x+1 < size && newMap[y][x+1] == 1) { checkMap(y, x+1); } } }