안전영역

---

title: “2468 - 안전영역”
date: “2019-02-14”

category: “algorithm”

문제요약

1. 지역의 넓이와 지역의 높낮이 정보가 입력으로 주어진다.
2. 높이가 n (지역의 가장 낮은 높이 <= n <= 지역의 가장 높은 높이)이하인 지역은 전부 물에 잠긴다고 한다.
3. 물에 잠기지 않은 지역들을 안전영역이라고 한다.
4. n을 변경하며 최대 몇개의 안전영역이 생기는지 출력해라.

접근법

이번 문제는 기존과는 달리 BFS를 여러번 실행시켜야 풀 수 있는 문제다. 다행히도 (정말 다행인지는 모르겠지만…) 높이가 같은 지역이 인접해 있지는 않기 때문에 물이 올라가는 것은 BFS를 쓰지 않고 2중 loop를 돌면서 일일이 변경해주면 된다.

다만 기존의 침수 높이가 달라지게 되면 안전 영역을 구하기 위해서는 침수지역이 변경되고 난뒤에 다시한번 BFS를 해주어야 한다. 높이가 낮은 곳부터 침수되도록 하고, 침수된 지역의 값을 0으로 변경해주면 단지번호붙이기(2667) 과 같은 BFS를 사용할 수 있다. 예제 TC를 살펴보자.

6	8	2	6	2
3	2	3	4	6
6	7	3	3	2
7	2	5	3	6
8	9	5	2	7

아무지역도 침수되지 않았다면 안전영역의 수는 1개가 된다. 이제 지역에서 가장 낮은 곳부터 침수시켜보도록 하겠다.

높이가 2 이하인 지역 침수

6	8	0	6	0
3	0	3	4	6
6	7	3	3	0
7	0	5	3	6
8	9	5	0	7

이러한 상태에서 안전영역의 수를 구하는 방법은 단지 번호 붙이기 문제처럼 0이 아닌 지역을 BFS로 탐색하며 찾아보면 된다. 위 상태에서 안전영역의 수는 아직 1개이다.

높이가 3 이하인 지역 침수

6	8	0	6	0
0	0	0	4	6
6	7	0	0	0
7	0	5	0	6
8	9	5	0	7

위 상태에서 안전영역의 수는 4개가 된다.

높이가 4 이하인 지역 침수

6	8	0	6	0
0	0	0	0	6
6	7	0	0	0
7	0	5	0	6
8	9	5	0	7

위 상태에서 안전영역의 수는 5개가 된다.

. . .

높이가 9 이하인 지역 침수

0	0	0	0	0
0	0	0	0	0
0	0	0	0	0
0	0	0	0	0
0	0	0	0	0

위 상태에서 안전영역의 수는 0개가 된다.

따라서 예제 TC에서 안전영역이 최대가 될 때는 4이하 지역이 침수됬을 때의 5개가 된다.

Source Code

소스코드 보러가기

• 아직 주석이 달려있지 않습니다.
• pseudocode 보다는 python 코드를 올릴 예정입니다.
• Code Review는 언제나 환영합니다 (코드를 더 깔끔하게, 효율적으로 만드는걸 도와주세요!)