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

BFS 응용 + ad-hoc

📑 문제

백준 31782 저체온증

---

🌱 아이디어

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

 

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

 

- 낮

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

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

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

 

- 밤

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

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

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

 

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

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

 

예제 입력 2 - 낮 결과

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

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

 

 

K = 2

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

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

 

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

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

---

🌱 코드 및 풀이

	import java.io.*;
	import java.util.*;
	public class Main {
	public static int N, M, K, answer;
	public static int minX = 2001, minY = 2001, maxX, maxY;
	public static char[][] arr1;
	public static boolean[][] vi;
	public static int[] dx = {0, 0, -1, 1};
	public static int[] dy = {-1, 1, 0, 0};
	public static Queue<node> qu = new LinkedList<>();
	public static class node {
	int x, y;
	public node(int x, int y) {
	this.x = x;
	this.y = y;
	}
	}
	// 저체온증 환자 회복 판별
	public static boolean isCanChange(int x, int y) {
	int cnt = 0;
	for (int i = 0; i < 4; i++) {
	int nx = x + dx[i];
	int ny = y + dy[i];
	if (nx < 0 || ny < 0 || nx >= M || ny >= N) continue;
	if (arr1[ny][nx] == 'O') cnt++;
	}
	return cnt >= 2;
	}
	// 사각형의 범위 구하기.
	public static void calcMinMaxCoordi(int x, int y) {
	maxX = Math.max(maxX, x);
	maxY = Math.max(maxY, y);
	minX = Math.min(minX, x);
	minY = Math.min(minY, y);
	}
	// 낮, 밤에 따라 BFS 탐색
	public static int dayOrNighttimeBFS(boolean dayOrNight) {
	int cnt = 1;
	int[] dx = {0, 0, -1, 1};
	int[] dy = {-1, 1, 0, 0};
	while (!qu.isEmpty()) {
	node nd = qu.poll();
	if (dayOrNight) { // 낮
	// 정상체온으로 변경 가능한지 판단.
	if (arr1[nd.y][nd.x] == 'O') continue;
	if (!isCanChange(nd.x, nd.y)) continue;
	answer++;
	arr1[nd.y][nd.x] = 'O';
	}
	for (int i = 0; i < 4; i++) {
	int nx = nd.x + dx[i];
	int ny = nd.y + dy[i];
	if (nx < 0 || ny < 0 || nx >= M || ny >= N) continue;
	if (dayOrNight) { // 낮
	if (arr1[ny][nx] == '.') {
	// 방금 체온이 회복된 사람 주변에 환자가 있다면 큐에 넣기
	// 낮 사이 회복이 충반히 많이 반복가능하기 때문임.
	qu.offer(new node(nx, ny));
	}
	} else { // 밤
	if (!vi[ny][nx] && arr1[ny][nx] == 'O') {
	// 정상체온 사각형 집합 좌표 범위 구하기, 인원 카운트 하기.
	vi[ny][nx] = true;
	calcMinMaxCoordi(nx, ny);
	cnt++;
	qu.offer(new node(nx, ny));
	}
	}
	}
	}
	return cnt;
	}
	public static void main(String[] args) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringBuilder sb = new StringBuilder();
	StringTokenizer st;
	st = new StringTokenizer(br.readLine(), " ");
	N = Integer.parseInt(st.nextToken());
	M = Integer.parseInt(st.nextToken());
	K = Integer.parseInt(st.nextToken());
	arr1 = new char[N][M];
	vi = new boolean[N][M];
	for (int i = 0; i < N; i++) {
	String str = br.readLine();
	for (int j = 0; j < M; j++) {
	arr1[i][j] = str.charAt(j);
	if (arr1[i][j] == '.') {
	qu.offer(new node(j, i));
	} else {
	// 초기 정상 인원 카운트
	answer++;
	}
	}
	}
	// true -> 낮일때, false -> 밤일때
	dayOrNighttimeBFS(true);
	for (int i = 0; i < N; i++) {
	for (int j = 0; j < M; j++) {
	// 밤일때, 정상체온 집합 사각형 범위 탐색
	if (!vi[i][j] && arr1[i][j] == 'O') {
	minX = minY = 20001;
	maxX = maxY = 0;
	vi[i][j] = true;
	qu.offer(new node(j, i));
	calcMinMaxCoordi(j, i); // 사각형 좌표 범위 구하기.
	int cnt = dayOrNighttimeBFS(false);
	int tmpX = maxX - minX + 1;
	int tmpY = maxY - minY + 1;
	// 사각형의 변 보다 K가 같거나 크다면
	if (K >= tmpX || K >= tmpY) {
	// 영구적으로 사각형 범위를 줄일 수 있음 -> 영구적 환자 발생
	answer -= cnt;
	}
	}
	}
	}
	System.out.println(answer);
	}
	}

view raw 저체온증.java hosted with ❤ by GitHub

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

 

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

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

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

---

🌱 느낀 점

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

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

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

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

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