[백준] 2468번: 안전 영역

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

풀이

1. input을 받으면서 HashSet에 지역의 높이정보를 저장했다. HashSet을 이용한 이유는, 중복저장을 하지 않기 위함과 해당 높이를 활용하여 물높이를 높일 것이기 때문이다. 이게 무슨소리냐면, 

예를들어, 예제 입력1 같은 경우에는 높이 정보가 골고루 되어있어서 2부터 9까지 반복문으로 물의 높이를 올려가면서 안전영역을 계산할 수 있겠지만 만약에,

4

1 1 1 1

100 100 100 100

1 1 1 1

100 100 100 100

이런 경우면은 1부터 100까지 물의 높이를 1씩 증가하는 것은 비효율적이라고 생각해서 Set에 높이정보를 따로 저장한 것이다.

추가로, HashSet은 HashMap기반으로 만들어져 있어서 정렬이 되지 않는다. 그래서 나는 List에 옮겨서 오름차순으로 정렬했다.

 

2. 말했듯이 list에 담겨있는 높이정보를 가지고 물의 높이를 올려가면서 안전영역을 계산한다. BFS로 구하면된다.

비슷한 풀이는 2667번 단지번호붙이기, 1926번 그림 등이 있다.

 

[C++풀이는 여기로👇]

2019/03/03 - [문제풀이(PS)] - [백준] 2468번: 안전 영역

 

코드 https://github.com/ziwonii24/Algorithm/blob/master/Baekjoon/java/2468.java

결과