[BOJ] 백준 31782 저체온증 (JAVA)

BFS 응용 + ad-hoc

📑 문제

백준 31782 저체온증

---

🌱 아이디어

낮, 밤 관련 BFS를 각각 구현하고, "영구적인 저체온증 환자"가 생기는 조건을 찾아보자.

 

위 문제의 키포인트는 볼드체로 잘 강조되어 있다. 낮, 밤을 나눠서 생각해 보자

 

- 낮

"체온 회복 과정은 낮 사이 충분히 많이 반복될 수 있다."

이 뜻은 다른 사람이 체온이 회복이 된다면, 그 주변 사람도 연쇄적으로 체온 회복이 가능하다는 뜻이다

즉, 낮 BFS를 통해 단 한 번으로 가능한 모든 사람을 회복시켜야 한다.

 

- 밤

K명만큼 밤에는 저체온증 환자가 발생한다 단 "최악의 경우"로 발생한다.

이 문제에서 최악의 경우란 낮이 되어도 회복이 불가능한 저체온증 환자이다. 그렇다면 어떤 조건에서 정상체온 환자가

영구적인 저체온증으로 변경되는지 캐치해야 한다.

 

가장 먼저, 낮에서 체온을 회복할 때 정상체온사람의 집합은 사각형을 그릴 수밖에 없다.

정상체온이 되려면 상, 하, 좌, 우로 2명의 정상체온사람이 있어야 한다. 이 조건에 맞게 펼치다 보면 사각형의 집합이 만들어진다

 

예제 입력 2 - 낮 결과

위 사진처럼 조건에 맞게 회복을 한다면 이런 모양으로 회복이 된다는 것을 알 수 있다. 그렇다면 어떻게 하면

다시 낮이 되어도 회복되지 않는 영구적인 저체온증 환자를 만들 수 있을까?

 

 

K = 2

K = 2 일 때 K 보다 작거나 같은 사각형의 변을 하나 제거한다면, 그 밤마다 사각형 전체를 없앨 수 있다

즉, 영구적인 저체온증 환자를 만들 수 있다

 

반대로 K 보다 큰 변을 K만큼 없앤다면 , 결국 저체온증 환자 상, 하, 좌, 우로 정상체온 사람이 2명이 있게 되어 낮에 회복을 한다.

이 점을 생각하며 구현해 보자!

---

🌱 코드 및 풀이

주석으로 각 함수마다 설명을 적어놨으니 크게 이해하는데 어려움은 없을 것 같다.

 

단 dayOrNighttimeBFS() 함수는 파라미터를 참, 거짓으로 받는다.

참 -> 낮 경우, 거짓 -> 밤 경우로 나눠서 각각 다른 역할을 수행한다.

BFS 함수를 두 개를 만들까 했지만 중복코드 제거를 위해 파라미터에 따라 역할을 나눴다.

---

🌱 느낀 점

JAVA로 푼사람이 아직 나밖에 없다..

위 문제가 백준에 출제된 지 별로 안되었기 때문에 푼사람 자체가 적어서 이런 것 같다 ㅎㅎ;;

실제로도 새로운 문제 유형이어서 재미있게 풀었다, 한 번쯤 풀어보는 거 추천한다!

이런 경험이 또 처음이라 뿌듯하다, 내 풀이가 최선인지는 모르겠으나 java로 푼사람이

생긴다면 체크를 해봐야겠다,